| Time Limit: 2 second(s) | Memory Limit: 32 MB |
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 |
题意：求0~n之间数位化成二进制后相邻为均为1的个数。
思路：设dp[pos][cnt]为当前考虑pos位，之前已经有cnt个11且前一位数位为1时，（pos+1）个数位与之前的数位组成的11的个数。详见代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=50;
typedef long long ll;
int n;
int bit[MAXN];
ll dp[MAXN][MAXN];
ll dfs(int pos,int pre,int cnt,int flag)
{
if(pos == -1) return cnt;
if(flag && dp[pos][cnt]!=-1 && pre) return dp[pos][cnt];
int x=flag ? 1: bit[pos];
ll ans=0;
for(int i=0;i<=x;i++){
ans+=dfs(pos-1,i==1,cnt+(i==1 && pre),flag || i<x);
}
if(flag &&pre) dp[pos][cnt]=ans;
return ans;
}
ll solve(int x)
{
int len=0;
while(x)
{
bit[len++]=x%2;
x/=2;
}
return dfs(len-1,0,0,0);
}
int main()
{
//freopen("text.txt","r",stdin);
int T,kase=0;
scanf("%d",&T);
memset(dp,-1,sizeof(dp));
while(T--){
kase++;
scanf("%d",&n);
printf("Case %d: %lld\n",kase,solve(n));
}
return 0;
}