首页 > 代码库 > POJ 3252 Round Numbers 数位dp

POJ 3252 Round Numbers 数位dp

2024-07-20 01:08:15   214人阅读

http://poj.org/problem?id=3252

题意：问从a到b有多少个round number。如果某数的二进制表示中0的个数不少于1的个数，那么它就是一个round number。

分析：数位dp。就我目前碰到的几道数位dp来说，其实所谓数位dp，就是和组合数有联系的递推罢了。还是转换为从0到a，我们先考虑二进制下长度小于a的数，即随便填0和1，那么就是用组合数算一下就可以了。然后考虑长度相等的，我们从高位往下走，已经枚举的就默认是a对应位的数。如果当前位是0，我们累计0的个数然后继续，如果是1，那么就可以变成0来考虑，之后的数又可以随便填，也是组合数算一下。这里会漏掉0和这个数本身，再单独算一下就行。

 

 1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4  5 int a, b; 6 int c[40][40]; 7 int d[40]; 8 void init() 9 {10     for (int i = 0; i <= 32; i++){11         c[i][0] = 1;12         for (int j = 1; j <= i; j++)13             c[i][j] = c[i][j-1] * (i-j+1) / j;14     }15 }16 int cal(int x)17 {18     if (x == -1) return 0;19     int ret = 1, len = 0;    //初始值为1，即0这个数20     while(x){21         d[len++] = x & 1;22         x >>= 1;23     }24     for (int i = 1; i < len; i++)            //长度为i(小于x的长度)25         for (int j = 0; j+1 <= i/2; j++)    //第一位为1，枚举之后有j个126             ret += c[i-1][j];27     int zero = 0, one = 1;28     for (int i = len-2; i >= 0; i--){29         if (d[i]){30             zero++;31             for (int j = 0; j <= i && j+one <= zero+(i-j); j++)32                 ret += c[i][j];33             zero--;34             one++;35         }36         else zero ++;37     }38     if (zero >= one) ret++;        //单独算x本身39     return ret;40 }41 int main()42 {43     init();44     while(scanf("%d %d", &a, &b) != EOF)45     {46         printf("%d\n", cal(b) - cal(a-1));47     }48     return 0;49 }

 

POJ 3252 Round Numbers 数位dp


联系
我们