首页 > 代码库 > poj 3252 Round Numbers
poj 3252 Round Numbers
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 }
poj 3252 Round Numbers
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。