给你一个区间，求区间内的round number的个数，如果一个数字的二进制表示中，0的个数大于等于1的个数，则这个数字叫做round number。 把数字用二进制表示出来，然后数位dp一发就好。这个题前导0会影响到结果，所以要考虑前导0。我做的时候就没想前导0，看了题解才想到还有前导0呢。 参考：http://blog.csdn.net/wust_zzwh/article/details/52100392 dp[pos][num]是dp的数组，pos表示枚举到第pos位，num表示0的个数和1的个数的差。因为差可能会小于0，所以要加上个数，让他大于0。
#include <stdio.h> #include <string.h> const int der = 32; int dp[36][66]; int digit[36]; int len; void calc(int num) { len = 0; while(num) { digit[len++] = num&1; num >>= 1; } } //s表示0的数量减掉1的数量 //多了一个lead表示有无前导0 //在这里前导0对数字有影响 int dfs(int i, int s, bool lead,bool e) { if(i == -1) return s>=der; if(!e && !lead && ~dp[i][s]) return dp[i][s]; int res = 0; int u = e?digit[i]:1; for(int d = 0; d <= u; ++d) { //如果存在前导0，则不计数 if(lead && d == 0) res += dfs(i-1, s, lead, e&&d==u); else res += dfs(i-1, s+(d==0?1:-1), lead&&d==0, e&&d==u); } if(!e && !lead) dp[i][s] = res; return res; } int solve(int num) { calc(num); return dfs(len-1,der,true,true); } int main() { memset(dp,-1,sizeof(dp)); int s,e; scanf("%d %d",&s,&e); printf("%d\n",solve(e)-solve(s-1)); return 0; }