POJ 3252 Round Numbers 组合数学 QAQ
题意：输入两个十进制正整数a和b，求闭区间 [a ,b] 内有多少个Round number。 Round Number：把一个十进制数转换为一个无符号二进制数，该二进制数中0的个数大于等于1的个数。
思路：
1.求闭区间 [a ,b] 内的个数，只需要求出 [0, b+1] 的个数 减去 [0, a] 的个数就行了。
2.接下来 关键在于求 [0, k] 内的 Round number。 求 [0, k] 内的 Round number 又可以分为 2 部分分开求。
我们首先需要把 k 转化为 二进制。长度为 len。
(1). 求长度小于 len 的数的 Round number。
易知，长度小于它的数一定比它小。 0 的个数大于 1 的个数 -> 保证 0 的大于 1 的个数后 自由排列 0 在二进制数中的位置。
另外，在 len-1 的位置一定是 1， 不是0， 因为：如果是 0， 那么就不会 len-1 位二进制了， 而是 len-2 位。len-2 会在后面再处理。
核心代码：
// cnt = len; for(int i = cnt-2; i >= 1; i --) for(int j = i/2+1; j <= i; j ++) sum+= C[i][j];(2). 求长度等于 len 但 比k小 的数 的 Round number。 在长度相同时，如果想要当前的数比 k 小，那就需要从高位到低位遍历k，当遇到1时，将它 变为 0，这样就能保证变为零后整个的数一定比 k 小。
核心代码：
// zero 为遇到 1 后前面经过了几个 0， 显然后面用得到。 int zero = 0; for(int i = cnt-1; i >= 1; i --) if(bin[i]) for(int j = (len+1)/2-zero-1; j <= i-1; j ++) sum += C[i-1][j]; else zero ++;另外一个很好的有助于理解的例子。
以下例子引用自ACM博客_kaungbin！！！！
比如： 22 = 10110(2) 如果要求 <=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. 22的第二位是0，所以第二位不能为1，必须是0 第三位为0的话，（前面有了2个0，1个1），后面两位可以有1个0，2个0 C（2，1）+C（2，2） 接下来把第三位恢复为1，看第四位。假如第四位是0，（前面有2个0，2个1），后面一位必须是0 C（1，1）
完整AC代码：
#include <iostream> #include <queue> #include <cstdio> #include <cstring> using namespace std; int cnt; int bin[35]; int C[35][35]; void calc() { for(int i = 0; i < 35; i ++) C[i][0] = 1; for(int i = 1; i < 35; i ++) for(int j = 1; j < 35; j ++) C[i][j] = C[i-1][j] + C[i-1][j-1]; } void Get_bin(int x) { cnt = 0; while(x) { bin[++cnt] = x%2; x >>= 1; } } int Get_Rn(int x)// Rn -> 0 > 1; { int sum = 0; Get_bin(x); int len = cnt; //长度小于 cnt for(int i = cnt-2; i >= 1; i --) for(int j = i/2+1; j <= i; j ++) sum += C[i][j]; //长度等于 cnt int zero = 0; for(int i = cnt-1; i >= 1; i --) if(bin[i]) for(int j = (len+1)/2-zero-1; j <= i-1; j ++) sum += C[i-1][j]; else zero ++; return sum; } int main() { int a, b; calc(); cin >> a >> b; calc(); int ans = Get_Rn(b+1) - Get_Rn(a); printf("%d\n",ans); return 0; }我学习此题于： 1.ζёСяêτ - 小優YoU 2.ACM博客_kaungbin 两位大神的博客非常好，然后方的此文。
