本文主要是介绍Round Numbers POJ - 3252,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
http://poj.org/problem?id=3252
注意前导零 比如0010要从2^1才开始算
只有当枚举了一个非零数之后才开始算0和1的个数
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100;int dp[maxn][maxn];
int bit[maxn];
int l,r;int dfs(int pos,int sta,int lead,int limit)
{int res,up,i;if(pos==-1) return sta>=32;if(!limit&&!lead&&dp[pos][sta]!=-1) return dp[pos][sta];if(limit) up=bit[pos];else up=1;res=0;for(i=0;i<=up;i++){if(lead&&i==0){res+=dfs(pos-1,sta,1,limit&&(i==bit[pos]));}else{res+=dfs(pos-1,sta+(i==1?-1:1),0,limit&&(i==bit[pos]));}}if(!limit&&!lead) dp[pos][sta]=res;return res;
}int solve(int val)
{int n;n=0;while(val>0){bit[n++]=val%2;val/=2;}return dfs(n-1,32,1,1);
}int main()
{memset(dp,-1,sizeof(dp));while(scanf("%d%d",&l,&r)!=EOF){printf("%d\n",solve(r)-solve(l-1));}return 0;
}
这篇关于Round Numbers POJ - 3252的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!