首页 > 代码库 > poj3252 Round Numbers
poj3252 Round Numbers
Round Numbers
POJ - 3252
题目大意：
输入两个十进制正整数a和b，求闭区间[a,b]内有多少个Round Number?
所谓的Round Number就是一个把十进制数转换成一个无符号二进制数，若该二进制数中0的个数大于等于1的个数，则它就是一个Round Number。
注意 转换所得的二进制数，最高位必然是1，最高位前不允许有0
【问题分析】
用前缀和思想：求出[0,a]和[0,b+1]内的答案，然后[0,b+1]-[0,a]
所以问题转向如何求[0,k]内有多少个Round Number。
首先把k转化成二进制数，并记录长度len。
计算分两步，第一步求出二进制长度小于len的情况，这种情况下得到的数一定在要求的范围内，所以直接按round number的性质组合就行
第二步求出二进制长度等于len的情况，这种情况下要保证得到的数在要求范围内的话，就只能依次把每位上的1变成0来讨论round number了
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int c[33][33]={0};int bin[35];void play_table(){ for(int i=0;i<=32;i++) for(int j=0;j<=i;j++) if(!j||i==j)c[i][j]=1; else c[i][j]=c[i-1][j-1]+c[i-1][j];}void Bin(int n){ memset(bin,0,sizeof(bin)); while(n){ bin[++bin[0]]=n&1; n>>=1; }}int round(int n){ int sum=0; Bin(n); //计算长度小于bin[0]的所有二进制数中RN的个数 for(int i=1;i<bin[0]-1;i++) for(int j=i/2+1;j<=i;j++) sum+=c[i][j]; //计算长度等于bin[0]的所有二进制数中RN的个数 int zero=0; for(int i=bin[0]-1;i>=1;i--){ if(bin[i]) for(int j=(bin[0]+1)/2-(zero+1);j<=i-1;j++) sum+=c[i-1][j]; else zero++; } return sum;}int main(){ play_table(); int a,b; while(scanf("%d%d",&a,&b)!=EOF) printf("%d\n",round(b+1)-round(a));}
poj3252 Round Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。