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

题意:每一个数的二进制形态下,如果每一个1后面还有有个1,那个这个数的价值就可以+1,对于有个n,问0~n所有的数的价值和。

思路:数位dp,见注释
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;
}

相关文章

发表新评论