uva11645 - Bits 统计 巧妙的大数
|
Problem J Output: StandardOutput ? A bit is a binary digit,taking a logical value of either "1" or "0" (also referredto as "true" or "false" respectively).? And every decimalnumber has a binary representation which is actually a series of bits. If a bitof a number is “1” and it's next bit is also “1” then we can say that thenumber has a 1 adjacent bit. And you have to find out how many times thisscenario occurs for all numbers up to N. ? Examples: ??????????? Number?????????? Binary ??????????????????????? AdjacentBits ??????????? 12??????????????????? 1100??????????????????????????? 1 ??????????? 15??????????????????? 1111??????????????????????????? 3 ??????????? 27??????????????????? 11011????????????????????????? 2 ? InputFor each test case,you are givenan integer number (0 <= N <= ((2^63)-2)),as described in the statement.The last test case is followed by a negative integer in a line by itself,denoting the end of input file. ? OutputFor every test case,print a lineof the form “Case X: Y”,where X is the serial of output (starting from 1) andY is the cumulative summation of all adjacent bits from 0 to N. ?SampleInput???????????????????????????? Output for Sample Input
? ??比如二进制100110，从低位往高位看，若最后两位是11，前面四位可以从0000到1000，这样就有个二进制的1001个。若倒数2，3位为1，前面三位可以从000到011，此时最后一位可以任取，这样就有二进制100*2个，并且因为N的倒数2，3都为1，所以前三位可以为100且最后一位为0，这样还要多加1个。若倒数3，4位为1，前两位可以为00到01，最后两位任取，这样有二进制的10*2^2个。。。以此类推。 ??要注意的地方就是N连续两位为1的时候的情况不要漏了。 ??在网上看了个巧妙的方法，因为数不是特别大，可以用两个long long表示了大数。。 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<cmath>
#define INF 0x3f3f3f3f
#define MAXN 50
#define MAXM 20010
#define MAXNODE 4*MAXN
#define MOD 1000000000
#define eps 1e-9
using namespace std;
const long long MAX=1e13;
long long N,a,b;
void add(long long n){
b+=n;
a+=b/MAX;
b%=MAX;
}
int main(){
//freopen("in.txt","r",stdin);
int cas=0;
while(scanf("%lld",&N),N>=0){
a=b=0;
long long d=1,t=N;
while(N){
add((N>>2)*d);
if((N&3)==3) add((t&(d-1))+1);
d<<=1;
N>>=1;
}
printf("Case %d: ",++cas);
if(a) printf("%lld%013lldn",b);
else printf("%lldn",b);
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |