| Time Limit: 2000MS | Memory Limit: 32768KB | 64bit IO Format: %lld & %llu |
Description
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
7
0
6
15
20
21
22
2147483647
Sample Output
Case 1: 0
Case 2: 2
Case 3: 12
Case 4: 13
Case 5: 13
Case 6: 14
Case 7: 16106127360
Source
题意：给出一个整数n，求从0到n所有数字之中二进制连续两个1的个数。
首先分解成二进制序列，然后数位dp
/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-7 21:57:20
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
ll dp[40][3][40],num[40];
ll dfs(ll pos,ll pre,ll cnt,bool flag){
if(pos==0)return cnt;
if(flag&&dp[pos][pre][cnt]!=-1)return dp[pos][pre][cnt];
ll u=flag?1:num[pos];
ll ans=0;
for(ll d=0;d<=u;d++)
ans+=dfs(pos-1,d,cnt+(pre==d&&d==1),flag||d<u);
if(flag)dp[pos][pre][cnt]=ans;
return ans;
}
ll solve(ll x){
memset(dp,-1,sizeof(dp));
ll len=0;
while(x){
num[++len]=x%2;
x/=2;
}
return dfs(len,-1,0,0);
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
ll T,t,n;
cin>>T;
for(t=1;t<=T;t++){
cin>>n;
cout<<"Case "<<t<<": ";
cout<<solve(n)<<endl;
}
return 0;
}
原文：http://blog.csdn.net/xianxingwuguan1/article/details/18971143