POJ 3252 Round Numbers 数字统计

本文主要是介绍POJ 3252 Round Numbers 数字统计，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：若一个数的二进制形式中0的个数不少于1的个数，那么就称这个数为round number，现在输入两个整数start,finish求在这两个数之间有多少个round number。

#include<cstdio>
#include<algorithm>
#define lint __int64
using namespace std;
lint C ( int m, int n )
{
if ( m < n ) return 0;
lint ret = 1;
for ( int i = 1, j = m; i <= n; i++, j-- )
ret = ret * j / i;
return ret;
}
lint cal ( int x )
{
lint count = 0;
int i, j, len = 0;
if ( x == 0 || x == 1 ) return 0;
while ( ((lint)1<<len) <= x ) len++; //先求出二进制的长度
for ( i = 2; i < len; i++ ) //长度小于len的可以用排列组合公式先求出来
{
j = i / 2;
if ( i & 1 ) j++;
for ( ; j < i; j++ )
count += C(i-1,j);
}
//对于长度等于len的，二进制中的所以1有两种情况，
//第一种是保持不变，第二种是将0该成1，然后再统计.
//0不作处理，因为如0变成1,那么同时一定有一个更高位的1变成了0.
//这样才能使数不超出[start,finish]的范围.
int zero = 0, limit = len / 2; //zero统计0的个数
if ( len & 1 ) limit++; //;limit表示至少需要的0的个数
for ( i = len - 2; i >= 0; i-- )
{
if ( ((1<<i) & x) )  
{
for ( j = max(limit-zero-1,0); j <= i; j++ )
count += C(i,j);
}
else zero++;
}
if ( zero >= limit ) count++;
return count;
}
int main()
{
int start, finish;
scanf("%d%d",&start,&finish);
printf("%I64d\n",cal(finish)-cal(start-1));
return 0;
}

这篇关于POJ 3252 Round Numbers 数字统计的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---