首页 > 代码库 > poj3252（Round Numbers）
poj3252（Round Numbers）
题目地址：Round Numbers
题目大意：
“Round Numbers” 是一个十进制的数转化为二进制，如果在二进制中 “0”的个数不小于“1”的个数，就称为“Round Numbers” 。本题求出n到m区间（闭区间）的“Round Numbers” 有多少个。
解题思路：
排列组合的公式：C（n，m）=C（n-1，m-1）+C（n，m-1）。
（转） 比如： 22 = 10110b 如果要求 <=22的Round Numbers，也就是找出1-22有多少个二进制的0不少于1的数的个数。
22的二进制长度是5.
首先找长度比5小的Round Numbers（长度比5小的数肯定小于22啦）
长度为4的话，第一位必须是1，后面三位的话，可以有2个0，3个0
所以就是C(3,2)+C(3,3);
长度为3的Round Numbers，同理有 C(2,2);//注意不要把第一位1忘记了
长度为2的Round Numbers，有 C(1,1)
长度为1的Round Numbers，有 0个。
下面是找长度和22相同的Round Numbers：
查找第二个是1的位置，则是逐渐把1变为0，去求后面的，就可以保证比n小了。
代码：
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <string> 6 #include <cstring> 7 using namespace std; 8 int C[35][35]; 9 void zuhe()10 {11 C[0][0]=1;12 C[1][0]=1;C[1][1]=1;13 for(int i=2;i<35;i++)14 {15 C[i][0]=1;16 for(int j=1;j<i;j++)17 C[i][j]=C[i-1][j-1]+C[i-1][j]; //排列组合的公式！18 C[i][i]=1;19 }20 }21 int judge(int f)22 {23 int s=f;24 int sum=0,sum1=1,d=0,sum2=1;25 int a[1000];26 memset(a,0,sizeof(a));27 while(s)28 {29 int ce=s%2;30 a[d++]=ce;31 s/=2;32 }33 int i,j,k;34 int ccc1=0,ccc0=0;35 for(i=0; i<d; i++)36 {37 if (a[i]==1)38 ccc1++;39 else40 ccc0++;41 }42 if (ccc0>=ccc1)43 sum++;44 int cnt0=0,cntt=0,cnt1=0;45 int c=0,c1=0;46 for(i=d-1; i>=0; i--)47 {48 if (a[i]==1)49 {50 cnt1++;51 if (cnt1>1)52 {53 int cee=cnt0-(cnt1-2)+1;54 c=d-cnt1-cnt0-cee;55 if (c<0)56 c=0;57 else58 c=c/2+1;59 c1=d-cnt1-cnt0;60 for(j=c; j<=c1; j++)61 {62 sum+=C[c1][j];63 }64 }65 }66 else67 cnt0++;68 }69 for(i=1; i<=d-1; i++)70 {71 for(j=(i-1)/2+1; j<=i-1; j++)72 {73 sum+=C[i-1][j];74 }75 }76 return sum;77 }78 int main()79 {80 int n,m;81 zuhe();82 while(scanf("%d%d",&n,&m)!=EOF)83 {84 int len1;85 if (n==1)86 len1=0;87 else88 len1=judge(n-1);89 int len2=judge(m);90 printf("%d\n",len2-len1);91 }92 return 0;93 }
poj3252（Round Numbers）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。