lightoj 1032 数位dp简单题 - c++编程基础

Fast Bit Calculations

Time Limit: 2000MS

Memory Limit: 32768KB

64bit IO Format: %lld & %llu

[Submit] [Go Back] [Status]

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 < 2³¹).

Output

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

Sample Input

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

Problem Setter: Mohiul Alam Prince Special Thanks: Jane Alam Jan (Modified Description, Dataset)

题意：给出一个整数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 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
                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
                
                 >T; for(t=1;t<=T;t++){ cin>>n; cout<<"Case "<