pku 3252

2009年10月29日 星期四

题目链接：PKU 3252 Round Numbers

分类：排列组合+区间计数

题目分析与算法原型
         这道题目总的来说不是太难，但是实现起来细节比较多，所以WA了好多次，大致思路是，给你的两个数，start和end ，分别求出1到start，以及1到end之间（包括start和end自身）的round number 的个数，然后两个相减一下，就差不多是要求的数，当然了还需判断一下start是不是也是round number是的话刚才减的结果还要加1。假设现在给你的数是a,那么求1到a之间的round number可以分两步来进行，先求出a在二进制下的位数m，然后求出1到m-1位的二进制数的round number的和（这个不难，只是排列组合的计算），第二步就是要加上，二进制位数为m但《=a的所有二进制数中round number的个数。其实可以这样考虑，设一个二进制数为101001100，那么从100000000到其之间的round number的数的个数可以这样考虑，从第二位开始左往右扫描，碰到为1的时候将其变为0，然后此位后的位数任意组合的数都肯定小于原来的数，枚举这个情况下（先记下当前0和1的个数，方便计算剩下的位数组合中round number的数目）的round number数目，然后继续扫描一直到最后。
        PS：此题代码实现的有些繁琐，有待改进..........

Code：


  1#include<stdio.h>
  2int x[35];
  3int cal(int m,int a)
  4{
  5    int i,j=1,res=1;
  6    for(i=m-1;i>=m-a;i--)
  7    {
  8        res*=i;
  9        res/=j;
 10        j++;
 11    }
 12    return res;
 13}
 14int num(int m)
 15{
 16    int k,i,res=0;
 17    if(m%2==0)k=m/2;
 18    else k=m/2+1;
 19
 20    for(i=k;i<m;i++)res+=cal(m,i);
 21    return res;
 22}
 23int check(int n)
 24{
 25    int res=0,i,num=0,y[35];
 26    int nn=n;
 27    while(nn)
 28    {
 29        y[res++]=nn%2;
 30        nn/=2;
 31    }
 32    for(i=0;i<res;i++)
 33        if(y[i]==0)num++;
 34        else num--;
 35    
 36    if(num>=0)return 1;
 37    else return 0;
 38}
 39int weishu(int n)
 40{
 41    int res=0,y[35];
 42
 43    int nn=n;
 44    while(nn)
 45    {
 46        y[res++]=nn%2;
 47        nn/=2;
 48    }
 49    return res;
 50}
 51int jisuan(int n)
 52{
 53    int k,i,j,y[35],num=0;
 54
 55    int nn=n;
 56    while(nn)
 57    {
 58        y[num++]=nn%2;
 59        nn/=2;
 60    }
 61    k=num/2-1;
 62    for(i=0;i<=k;i++)
 63    {
 64        int t=y[i];
 65        y[i]=y[num-1-i];
 66        y[num-1-i]=t;
 67    }
 68    int num1=1,num0=0,ss,kk,res=0;
 69    for(i=1;i<num;i++)
 70    {
 71        if(y[i]==1)
 72        {
 73            num0++;
 74            ss=num-i-1;
 75
 76            if(ss+num1-num0<0)kk=0;
 77            else
 78            {
 79                if((ss+num1-num0)%2==0)kk=(ss+num1-num0)/2;
 80                else kk=(ss+num1-num0)/2+1;
 81            }
 82            if(kk<ss)
 83            {
 84                int mm,q,ii;
 85                for(ii=kk;ii<=ss;ii++)
 86                {
 87                    mm=1;
 88                    if(ii==0)res+=1;
 89                    else
 90                    {
 91                        q=1;
 92                        for(j=ss;j>ii;j--)
 93                        {
 94                            mm*=j;
 95                            mm/=q;
 96                            q++;
 97                        }
 98                        res+=mm;
 99                    }    
100                }    
101            }
102            else if(kk==ss)
103            {
104                res+=1;
105            }
106
107            num0--;
108            num1++;
109        }
110        else num0++;
111        
112        if(i==num-1&&num0>=num1)res++;
113    }
114    return res;
115}
116int main()
117{
118    int i,s,f;
119    x[1]=0;
120    for(i=2;i<=33;i++)x[i]=x[i-1]+num(i);
121    while(scanf("%d%d",&s,&f)!=EOF)
122    {
123        int a=weishu(s),b=weishu(f),ans=0,c,d;
124        c=jisuan(s);
125        c+=x[a-1];
126        d=jisuan(f);
127        d+=x[b-1];
128        ans=d-c;
129        if(check(s))ans++;
130        printf("%d\n",ans);
131    }
132    return 0;
133}
134

posted on 2009-10-29 16:06 蜗牛也Coding 阅读(312) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜