题目链接：http://poj.org/PRoblem?id=3252 题意：假设将一个数字转换为二进制，其中二进制中的0的个数大于等于二进制中1的个数，那么这个数字称为Round Numbers。问[l,r]（1<=l<=r<=2e9）内存在多少个Round Numbers。 想法：很简答的数位DP，开一个dp[i][one][zero]，i表示第i位，one表示最高位到此位1的个数，zero表示最高位到此位0的个数。只需将数字转化为二进制，然后套入数位DP模板即可。
#include<stdio.h>#include<string.h>int dp[35][35][35],a[35];int dfs(int pos,int zero,int one,int last){ if(!pos) return zero-one>=0&&zero; if(!last&&dp[pos][zero][one]!=-1) return dp[pos][zero][one]; int num,i,ans=0; num=last?a[pos]:1; for(i=0; i<=num; i++) ans+=i?dfs(pos-1,zero,one+1,last&&i==num):dfs(pos-1,one?zero+1:0,one,last&&i==num); if(!last) dp[pos][zero][one]=ans; return ans;}int cal(int n){ int sizes=0,i,ans=0; while(n) a[++sizes]=n&1,n>>=1; return dfs(sizes,0,0,1);}int main(){ int l,r; memset(dp,-1,sizeof(dp)); while(scanf("%d%d",&l,&r)!=EOF) printf("%d/n",cal(r)-cal(l-1)); return 0;}新闻热点
疑难解答
