本文主要是介绍POJ 3252 Round Numbers（组合数学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=3252
这个题目比较容易想，但是写代码要注意的细节异常多，整体思想是组合数学
求两个数到1有多少Round Numbers，然后相减
求的时候分两种情况：
1.位数相等的小于而且符合条件的（二进制位数）
先化为二进制
先从左向右（第二位开始）依次将1变成0，这样肯定比原来数小，后面多少位随机，利用前面已知0和1的个数计算后面的组合
2.位数小的第一位肯定是1，后面处理方法直接排列组合
C[i][j]先预处理下！
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 50;
int C[maxn][maxn];
int bit[maxn];
int num;
int a,b;
int init(){memset(C,0,sizeof(C));int i,j,k;C[1][0]=C[1][1]=C[0][0]=1;for(i=0;i<=50;i++) C[i][0]=C[i][i]=1;for(i=2;i<=50;i++)for(j=1;j<=50;j++){C[i][j]=C[i-1][j-1]+C[i-1][j];}return 0;
}
int cal_num(int a){num=0;while(a!=0){if(a&1) bit[num++]=1;else bit[num++]=0;a>>=1;}return 0;
}
int same(int num){int ans=0,zero=0,one=1,now=num-2,then;num--,num--;while(num>=0){if(bit[num]){zero++;for(then=0;then<=now;then++){if(zero+then >= now-then+one)ans+=C[now][then];}zero--;one++;}else{zero++;}num--;now--;}if(zero >= one) ans++;return ans;
}
int cal_ans(int value){int ans=0,zero=0,one=1,now,then,i;cal_num(value);ans+=same(num);num--;while(num>=1){now=num-1;for(then=now;then>=(num+1)/2;then--){ans+=C[now][then];}num--;}return ans;
}
int main(){int i,j,k;init();while(scanf("%d%d",&a,&b)!=EOF){if(a>b) swap(a,b);printf("%d\n",cal_ans(b)-cal_ans(a-1));}return 0;
}
这篇关于POJ 3252 Round Numbers（组合数学）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
