POJ 3252 - Round Numbers

算法

原创

发布日期: 2011-12-24

更新日期: 2026-11-06

文章字数: 2.5k

阅读时长: 10 分

阅读次数:

POJ 3252 - Round Numbers
Time: 2000MS
Memory: 65536K
难度: 初级
分类: 排列组合

0x00 POJ 原题

Description

The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone’ (also known as ‘Rock, Paper, Scissors’, ‘Ro, Sham, Bo’, and a host of other names) in order to make arbitrary decisions such as who gets to be milked first. They can’t even flip a coin because it’s so hard to toss using hooves.

They have thus resorted to “round number” matching. The first cow picks an integer less than two billion. The second cow does the same. If the numbers are both “round numbers”, the first cow wins,

otherwise the second cow wins.

A positive integer N is said to be a “round number” if the binary representation of N has as many or more zeroes than it has ones. For example, the integer 9, when written in binary form, is 1001. 1001 has two zeroes and two ones; thus, 9 is a round number. The integer 26 is 11010 in binary; since it has two zeroes and three ones, it is not a round number.

Obviously, it takes cows a while to convert numbers to binary, so the winner takes a while to determine. Bessie wants to cheat and thinks she can do that if she knows how many “round numbers” are in a given range.

Help her by writing a program that tells how many round numbers appear in the inclusive range given by the input (1 ≤ Start < Finish ≤ 2,000,000,000).

Input

Line 1: Two space-separated integers, respectively Start and Finish.

Output

Line 1: A single integer that is the count of round numbers in the inclusive range Start..Finish

Sample Input

2 12

Sample Output

Source

USACO 2006 November Silver

0x10 题目概述

输入两个十进制正整数 a 和 b，求闭区间 [a ,b] 内有多少个 Round number

所谓的 Round Number 就是把一个十进制数转换为一个无符号二进制数，若该二进制数中 0 的个数大于等于 1 的个数，则它就是一个 Round Number

注意：

转换所得的二进制数，最高位必然是 1，最高位的前面不允许有 0
-规定输入范围： 1 <= a < b <= 2E

0x20 解题思路

很猥琐的题，我首先说说猥琐的地方，再说说解题思路，有四点很猥琐：

（1）规定输入范围：1 <= a < b <= 2E

输入的数是一个接近大数的非大数, int 可以存储。网上看很多同学都说要用到精度，其实完全没必要，int 能表示 21E+的整数，精确的 int 极限能表示的正整数为 2147483647，但是即使这样，面对这题也不能松懈啊！ bin[] 边界的最小值为 35！！
（2）bin[] 数组若果定义为局部数组，等着 WA 吧！

我找不到任何原因为什么会这样，bin 不管是全局定义还是局部定义，本地是完全 AC 的，上传就出问题了，局部 WA，全局 AC。

我被迫把传参 del 掉，把 bin 改为全局，郁闷！
（3）组合数打表，同(1)的猥琐，c[][] 边界的最小值为 33，就是说如果定义组合表的大小比 c[33][33] 小的，就等着 RE 吧!

还有就是这个算法有一个违背常识的处理，要把 c[0][0]=1，不然某些最终结果会少 1
（4）输入不能用循环输入 while(cin>>…)，不然你就等着 OLE (就是 Output Limit Excessed，很少见吧！)。不知道数据库是怎么回事，输入竟然不会根据读取数据结束而结束，而是无限输出最后一次输入所得的结果……老老实实一次输出就 end file 吧！

组合数学题，（也属 递推数学，是因为杨辉三角和组合数之间的关系）

我根据我写的程序讲解好了。

要知道闭区间 [a ,b] 内有多少个 Round number，只需要分别求出：

闭区间 [0, a] 内有 T 个 RN
闭区间 [0, b+1] 内有 S 个 RN
再用 S – T 就是闭区间 [a, b] 内的 RN 数了

至于为什么是 b+1，因为对于闭区间 [0, k]，我下面要说的算法求出的是比 k 小的 RN 数，就是说不管 k 是不是 RN, 都没有被计算在内，所以若要把闭区间 [a, b] 的边界 a 和 b 都计算在内，就要用上述的处理方法。

现在问题的关键就是如何求 [0, k] 内的 RN 数了：

首先要把 k 转化为二进制数 bin-k，并记录其位数（长度）len

那么首先计算长度小于 len 的 RN 数有多少（由于这些数长度小于 len，那么他们的值一定小于 k，因此在进行组合时就无需考虑组合所得的数与 k 之间的大小了）

for(i=1;i<bin[0]-1;i++)         //bin[0]记录的是二进制数的长度len
      for(j=i/2+1;j<=i;j++)
            sum+=c[i][j];

可以看到，i<len-1，之所以减 1，是因为这些长度比 len 小的数，最高位一定是 1，那么剩下可供放入数字的位数就要再减少一个了。

这条程序得到的 sum 为

1 表示当前处理的二进制数的最高位，X 表示该二进制数待放入数字的位。

显然这段程序把二进制数 0 排除在外了，这个是最终结果没有影响的，因为最后要把区间 [a, b] 首尾相减，0 存不存在都一样了。

然后计算长度等于 len 的 RN 数有多少（由于这些数长度等于 len，那么他们的值可能小于 k，可能大于 k，因此在进行组合时就要考虑组合所得的数与 k 之间的大小了）

int zero=0;  //从高位向低位搜索过程中出现0的位的个数
for(i=bin[0]-1;i>=1;i--)
    if(bin[i])   //当前位为1
        for(j=(bin[0]+1)/2-(zero+1);j<=i-1;j++)
        sum+=c[i-1][j];
    else
        zero++;

之所以初始化 i=bin[0]-1，是因为 bin[] 是逆向存放 k 的二进制的，因此要从高位向低位搜索，就要从 bin[] 后面开始，而要 bin[0]-1，是因为默认以后组合的数长度为 len，且最高位为 1，因此最高位不再搜索了。

现在问题的关键就是怎样使得以后组合的数小于 k 了

这个很简单：

从高位到低位搜索过程中，遇到当前位为 0，则不处理，但要用计数器 zero 累计当前 0 出现的次数

遇到当前位为 1，则先把它看做为 0，zero+1，那么此时当前位后面的所有低位任意组合都会比 k 小，找出这些组合中 RN 的个数，统计完毕后把当前位恢复为原来的 1，然后 zero-1，继续向低位搜索。

剩下的问题就是当当前位为 1 时，把它看做 0 之后，怎样去组合后面的数了

此时组合要考虑 2 个方面：

（1）当前位置 i 后面允许组合的低位有多少个，我的程序由于 bin 是从 bin[1] 开始存储二进制数的，因此当前位置 i 后面允许组合的低位有 i-1 个
（2）组合前必须要除去前面已出现的 0 的个数 zero

我的程序中初始化 j=(bin[0]+1)/2-(zero+1)， j 本来初始化为 (bin[0]+1)/2 就可以了，表示对于长度为 bin[0] 的二进制数，当其长度为偶数时，至少其长度一半的位数为 0，它才是 RN，当其长度为奇数时，至少其长度一半+1 的位数为 0，它才是 RN。

但是现在还必须考虑前面出现了多少个 0，根据前面出现的 0 的个数，j 的至少取值会相应地减少。 -(zero+1)，之所以 +1，是因为要把当前位 bin[i] 看做 0

然后到了最后，剩下一个问题就是怎样得到每一个的值，这个我发现很多同学都是利用打表做的，利用的就是组合数与杨辉三角的关系（建立一个二维数组 C[n]，就能看到他们之间关系密切啊！区别就是顶点的值，杨辉三角为 1，组合数为 0）

其实这个“关系”是有数学公式的：

好好体会一下吧！

其实组合数也可以直接用计算方法做(n 的规模可以至少扩展到 1000)，不过这里 n 的规模只有 26，打表应该是更快的，有兴趣学习用计算方法做组合数的同学可以联系我，这个要用另外的数学方法处理。

0x30 AC 源码

//Memory Time 
//224K   16MS  

#include<iostream>
using namespace std;

int c[33][33]={0};
int bin[35];  //十进制n的二进制数

/*打表，计算nCm*/

void play_table(void)
{
    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];
//    c[0][0]=0;
    return;
}

/*十进制n转换二进制，逆序存放到bin[]*/

void dec_to_bin(int n)
{
    bin[0]=0;   //b[0]是二进制数的长度
    while(n)
    {
        bin[++bin[0]]=n%2;
        n/=2;
    }
    return;
}

/*计算比十进制数n小的所有RN数*/

int round(int n)
{
    int i,j;
    int sum=0;  //比十进制数n小的所有RN数
    dec_to_bin(n);

    /*计算长度小于bin[0]的所有二进制数中RN的个数*/

    for(i=1;i<bin[0]-1;i++)
        for(j=i/2+1;j<=i;j++)
            sum+=c[i][j];

    /*计算长度等于bin[0]的所有二进制数中RN的个数*/

    int zero=0;  //从高位向低位搜索过程中出现0的位的个数
    for(i=bin[0]-1;i>=1;i--)
        if(bin[i])   //当前位为1
            for(j=(bin[0]+1)/2-(zero+1);j<=i-1;j++)
                sum+=c[i-1][j];
        else
            zero++;

    return sum;
}

int main(void)
{
    play_table();

    int a,b;
    cin>>a>>b;
    cout<<round(b+1)-round(a)<<endl;

    return 0;
}