首页 > 代码库 > poj 3252 Round Numbers

poj 3252 Round Numbers

2024-07-28 02:13:21   220人阅读

http://poj.org/problem?id=3252

题意：求一个区间内的数化为二进制后0的个数大于1的个数的数的个数。 用组合数求出小于一个数的长度的所有情况，然后再单独处理这个长度这种情况。然后右端点求的个数减去左端点求的个数就是答案。

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define ll __int64 5 using namespace std; 6  7 ll s,t; 8 int a[100]; 9 ll c[110][110];10 void inti()11 {12     for(int i=0; i<=32; i++)13     {14         c[i][0]=1;15         for(int j=1; j<=i; j++)16         {17             c[i][j]=(c[i-1][j-1]+c[i-1][j]);18         }19     }20 }21 22 ll Get_NUM(int n)23 {24     if(n<=1) return 0;25     memset(a,0,sizeof(a));26     int cnt=0;27     while(n)28     {29         a[cnt++]=n%2;30         n>>=1;31     }32     ll ans=0;33     for(int i=2; i<cnt; i++)34     {35         for(int j=(i+1)>>1; j<i; j++)36         {37             ans+=c[i-1][j];38         }39     }40     int t1=1,t2=0;41     for(int i=cnt-1; i>=0; i--)42     {43         if(a[i-1])44         {45           for(int j=i-1; ;  j--)46           {47               int num1=i-1-j+t1;48               int num2=j+t2+1;49               if(num1>num2) break;50               ans+=c[i-1][j];51           }52           t1++;53         }54         else55         {56             t2++;57         }58     }59     if(t1<=t2)60     {61         ans++;62     }63     return ans;64 }65 int main()66 {67     inti();68     while(scanf("%I64d%I64d",&s,&t)!=EOF)69     {70          printf("%I64d\n",Get_NUM(t)-Get_NUM(s-1));71     }72     return 0;73 }
View Code

 

poj 3252 Round Numbers


联系
我们