lightoj 1032 - Fast Bit Calculations - dblank

# lightoj 1032 - Fast Bit Calculations

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 its 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
Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains an integer N (0 ≤ N < 231).

Output
For each test case, print the case number and the summation of all adjacent bits from 0 to N.

Sample Input
Output for Sample Input
7
0
6
15
20
21
22
2147483647
Case 1: 0
Case 2: 2
Case 3: 12
Case 4: 13
Case 5: 13
Case 6: 14
Case 7: 16106127360

AC代码：

#include<bits/stdc++.h>

using namespace std;
const int  N = 100 + 10, inf = 0x3f3f3f3f;
const double eps = 1e-10;
typedef long long ll;
typedef pair<int, int> P;
int digit[40], cnt;
ll dp[40][40][2];
ll dfs(int pos, int pre,int sum, int lim)
{
if(pos<=0) return sum;
if(!lim && dp[pos][sum][pre]!=-1) return dp[pos][sum][pre];
int End = lim ? digit[pos] : 1;
ll res = 0;
for(int i = 0; i<=End; i++)
{
if(pre)                   //搜索到前去前驱是1的时候这个时候是1的话价值就会增加
res += dfs(pos-1, i, sum+(i==1),lim && (i==End));
else res += dfs(pos-1, i, sum, lim && (i==End));
}
if(!lim) dp[pos][sum][pre] = res;
return res;
}
ll solve(ll x)
{
cnt = 0;
while(x)
{
digit[++cnt] = x%2;
x/=2;
}
return dfs(cnt, 0, 0, 1);
}
int main()
{
memset(dp, -1, sizeof(dp));
int t;
ll n;
scanf("%d", &t);
for(int cas = 1; cas<=t; cas++)
{
scanf("%lld", &n);
printf("Case %d: ",cas);
printf("%lld\n",solve(n));
}
return 0;
}