poj 3252 Round Numbers （杨辉三角求组合数）

题目链接：poj 3252

题意：给出范围为 [a , b] 的区间，问在这区间内的每个数字，假如它的二进制位0的个数大于1的个数，就说明它是Round Numbers，问你有多少个Round Numbers数？

题解：首先杨辉三角求组合数学，见代码。

///此题就是个组合数学题，二项式和为2^n，
///但这题卡我的是求组合数那里，我刚想的是按一般方法求，
///但因为最多有32位，会爆，网上说用杨辉三角，一想是哦，
///做完这题又学会了用杨辉三角求组合数#include
#include
#includeusing namespace std;typedef long long LL;LL C[35][35];
int bits[35];void init() ///杨辉三角求组合数
{C[0][0]=C[1][0]=C[1][1]=1;for(int i=2;i<33;i++){C[i][0]=1;for(int j=1;j>=1;}LL ans=0;///当i为偶数时，说明在i-1位中，可以取C[i-1][i/2]+C[i-1][i/2+1]+...+C[i-1][i]///当i为奇数时，说明在i-1位中，可以取C[i-1][i/2]+C[i-1][i/2+1]+...+C[i-1][i],比偶数多一个最中间的for(int i=len-1;i>=2;i--){if(i%2==0) ans+=((1<<(i-1)))/2; ///二项式和的一半else ans+=((1<<(i-1))-C[i-1][(i-1)/2])/2;}int cnt1=0,cnt0=0;for(int i=1;i<=len;i++){if(bits[i]==0) cnt0++;else cnt1++;}if(cnt0>=cnt1) ans++; ///本身就是cnt0=0;cnt1=1; ///计数0 1 的个数for(int i=len-1;i>=1;i--){if(bits[i]==1){ ///后面有i-1位，我们把第i为看做0for(int j=i-1;j>=0&&j+cnt0+1>=(i-1)-j+cnt1;j--) ///在i-1位中取j个0ans+=C[i-1][j];cnt1++;}elsecnt0++;}return ans;}int main()
{int a,b;init();while(~scanf("%d%d",&a,&b)){printf("%lld\n",solve(b)-solve(a-1));}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！