首页 > 代码库 > uva 11645
uva 11645
Problem J
Bits
Input: Standard Input
Output: Standard Output
A bit is a binary digit, taking a logical value of either "1" or "0" (also referred to as "true" or "false" respectively). And every decimal number has a binary representation which is actually a series of bits. If a bit of a number is “1” and it‘s next bit is also “1” then we can say that the number has a 1 adjacent bit. And you have to find out how many times this scenario occurs for all numbers up to N.
Examples:
Number Binary Adjacent Bits
12 1100 1
15 1111 3
27 11011 2
Input
For each test case, you are given an 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.
Output
For every test case, print a line of the form “Case X: Y”, where X is the serial of output (starting from 1) and Y is the cumulative summation of all adjacent bits from 0 to N.
题意:
给出定义 A(x) 为 x 的二进制表示中 11 的个数.
请你求出 A(x) 的前缀和 S(x)
思路:
如果真正理解了 uva 11038, 那么这道题应该差不多...
分段考虑的话,就是当第 i 与 i-1 位 为1 的时候,
左边 有.... 右边有......
根据乘法原理, 直接乘起来就ok.
再根据加法原理,直接加起来就是答案.
由于答案比较大.所以采用两个数字压位的做法..(学到的好方法.)
我的程序写得非常啰嗦.....不如再去看看别人的.
1 #include<cstdlib> 2 #include<cstdio> 3 #include<iostream> 4 #include<cstring> 5 using namespace std; 6 const long long lim = (long long)1e13; 7 typedef long long BIG[2]; 8 BIG ans; 9 long long n,x1,x2,x3,L;10 int kase;11 void add(BIG &a,long long b){12 a[1] += b; a[0] += a[1] / lim; a[1] %= lim;13 }14 int digit(long long x,int pos){ return (x & (1LL << pos)) != 0; }15 long long ext(long long n,long long st,long long ed){16 if(st > ed) return 0;17 n >>= st;18 return n & ((1LL << (ed - st + 1)) - 1);19 }20 int main()21 {22 freopen("bits.in","r",stdin);23 freopen("bits.out","w",stdout);24 while(scanf("%lld",&n), n >= 0){25 ans[0] = ans[1] = 0;26 for(L = 63; L > 0 && !digit(n,L); L--);27 int a = digit(n,L), b = digit(n,L-1);28 if(a == b && a == 1 && n != 3) add(ans, ext(n,0,L-2) + 1);29 a = digit(n,1), b = digit(n,0);30 add(ans, ext(n,2,L) + (a && b));31 for(int i = L-1; i >= 2; --i){32 a = digit(n,i), b = digit(n,i-1);33 x1 = ext(n,i+1,L), x2 = ext(n,0,i-2) + 1, x3 = (1LL << (i-1));34 add(ans,(x1 && a && b ? 1 : 0) * x2 + x1 * x3);35 }36 add(ans,0);37 printf("Case %d: ",++kase);38 if(ans[0]){39 printf("%lld",ans[0]); 40 printf("%013lld\n",ans[1]);41 } 42 else printf("%lld\n",ans[1]);43 }44 return 0;45 }
uva 11645