Lightoj1032——Fast Bit Calculations（数位dp）-白红宇

Lightoj1032——Fast Bit Calculations（数位dp）

阅读量：2343 次

发布时间：2019-05-10

本文共 2049 字，大约阅读时间需要 6 分钟。

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

2147483647

Output for Sample Input

Case 1: 0

Case 2: 2

Case 3: 12

Case 4: 13

Case 5: 13

Case 6: 14

Case 7: 16106127360

转换成二进制dp

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #define INF 0x3f3f3f3f#define MAXN 10000005#define Mod 10001using namespace std;int dight[40];long long dp[40][2][40];long long dfs(int pos,int s,bool limit,int sum){ if(pos==0) return sum; if(!limit&&dp[pos][s][sum]!=-1) return dp[pos][s][sum]; int end; long long ret=0; if(limit) end=dight[pos]; else end=1; for(int d=0; d<=end; ++d) { if(s) { if(d==1) ret+=dfs(pos-1,1,limit&&d==end,sum+1); else ret+=dfs(pos-1,0,limit&&d==end,sum); } else { if(d==1) ret+=dfs(pos-1,1,limit&&d==end,sum); else ret+=dfs(pos-1,0,limit&&d==end,sum); } } if(!limit) dp[pos][s][sum]=ret; return ret;}long long solve(long long a){ memset(dight,0,sizeof(dight)); int cnt=1; while(a!=0) { dight[cnt++]=a%2; a/=2; } return dfs(cnt-1,0,1,0);}int main(){ memset(dp,-1,sizeof(dp)); int t,cnt=1; scanf("%d",&t); while(t--) { long long x; scanf("%lld",&x); printf("Case %d: %lld\n",cnt++,solve(x)); } return 0;}

转载地址：http://bvcvb.baihongyu.com/

你可能感兴趣的文章