首页 > 代码库 > [ACM] POJ 3252 Round Numbers (一个区间内二进制中0的个数大于等于1的个数有多少个，组合）

[ACM] POJ 3252 Round Numbers (一个区间内二进制中0的个数大于等于1的个数有多少个，组合）

2024-07-13 10:01:07   222人阅读

Round Numbers
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 8590 Accepted: 3003

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

6

Source

USACO 2006 November Silver


解题思路：

题意为在一个闭区间内，有多少个数它的二进制中0的个数大于等于1的个数。

总体思路为： 比如求 [2,12],  我们就求 （0,12] -（0,1]。这样问题就转化为了 求（0,n]之间有多少个符合题意的数。

以下转载为：http://hi.baidu.com/ycdoit/item/6f64473c54a88f607d034b7f

[2,12]区间的RoundNumbers（简称RN）个数:Rn[2,12]=Rn[0,12]-Rn[0,1]
 即：Rn[start,finish]=Rn[0,finish]-Rn[0,start-1]
 所以关键是给定一个X，求出Rn[0,X]
 现在假设X=10100100 
 这个X的二进制总共是8位，任何一个小于8位的二进制都小于X
 第一部分，求出长度为[0,7]区间内的二进制是RoundNumber的个数
  对于一个长度为Len的二进制(最高位为1)，如何求出他的RoundNumbers呢（假设为用R(len)来表达），分为奇数和偶数两种情况
  1、奇数情况：在Len=2k+1的情况下，最高位为1，剩下2k位，至少需要k+1为0
   用C(m,n)表示排列组合数：从m个位置选出n个位置的方法
   R(len)=C(2k,k+1)+C(2k,k+2)+...+C(2k,2k).
   由于 A：C(2k,0)+C(2k,1)+...+C(2k,2k)=2^（2k）
     B:C(2k,0)=C(2k,2k), C(2k,1)=C(2k,2k-1) ,,C(2k,i)=C(2k,2k-i)
   于是  C(2k,0)+C(2k,1)+...+C(2k,2k)
    = C(2k,0)+C(2k,1)+...+C(2k,k)+C(2k,k+1)+C(2k,K+2)+...+C(2k,2k)
    = 2*R(len)+C(2k,k)
    =2^(2k)
    所以R(len)=1/2*{2^(2k)-C(2k,k)};
  2. 偶数情况 len=2*k，类似可以推到 R(len)=1/2*(2^(2k-1));
 第二部分，对于上面这个长度为8的例子:即X=10100100，首先如果本身是RoundNumbers，第二部分的结果总数+1
  第一部分已经将长度小于8的部分求出。现在要求长度=8的RoundNumber数目
  长度为8，所以第一个1不可改变
  现在到第二个1，如果Y是前缀如100*****的二进制，这个前缀下，后面取0和1必然小于X，已经有2个0，一个1，剩下的5个数字中至少需要2个0，
   所以把第二个1改为0：可以有C(5,2)+C(5,3)+C(5,4)+C(5,5)
  现在第三个1，也就是前最为101000**，同样求出，至少需要0个0就可，所以有C(2,0)+C(2,1)+C(2,2)个RoundNumbers
  。。。
  将所有除了第一个1以外的1全部变为0，如上算出有多少个RoundNumbers，结果相加（由于前缀不一样，所以后面不管怎么组合都是唯一的）

 将第一部分和第二部分的结果相加，就是最后的结果了。
 精度要求方面，用int就可以了：two billion=20亿<2*1024*1024*1024=2^31，需用31位来表示数组，由于第一位总是1，所以求组合数的时候最多求30，C(30,k),k取值区间是[0,30],因为C(k,i)<2^k，所以结果用int表示就可以


参考：http://www.cnblogs.com/kuangbin/archive/2012/08/22/2651730.html


代码：

#include <iostream>
#include <string.h>
using namespace std;
int c[32][32];
int b[32];

void getCom()
{
    memset(c,0,sizeof(c));
    c[0][0]=c[1][0]=c[1][1]=1;
    for(int i=2;i<=30;i++)
    {
        c[i][i]=c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
}

int cal(int n)
{
    if(n<=1)//注意正整数，0不是round number
        return 0;
    int bit=0;
    int temp=n;
    int ans=0;

    while(temp)//b[]保存每一位二进制数，一共bit位
    {
        b[bit++]=temp%2;
        temp/=2;
    }

    for(int i=bit-1;i>=1;i--)//位数比当前数少一位的round number
    {
        if(i%2==0)
            ans+=(1<<(i-1))/2;
        else
            ans+=((1<<(i-1))-c[i-1][(i-1)/2])/2;
    }

    int num0=0,num1=0;
    for(int i=0;i<bit;i++)//判断自身
        if(b[i])
            num1++;
        else
            num0++;
    if(num0>=num1)
        ans++;

    num0=0;num1=1;
    for(int i=bit-2;i>=0;i--)
    {
        if(b[i]==0)
            num0++;
        else
        {
            num1++;
            for(int k=i;k>=0&&k+num0+1>=i-k+num1-1;k--)//k是选择0的个数，总共0的个数要大于等于1的个数
                ans+=c[i][k];
        }
    }
    return ans;
}

int main()
{
    getCom();
    int a,b;
    cin>>a>>b;
    cout<<cal(b)-cal(a-1)<<endl;
    return 0;
}


[ACM] POJ 3252 Round Numbers (一个区间内二进制中0的个数大于等于1的个数有多少个，组合）


联系
我们