青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(343) 評論(0)  編輯 收藏 引用


只有注冊用戶登錄后才能發表評論。
網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲欧美国产高清| 午夜精品久久久久久| 欧美理论电影在线播放| 欧美激情亚洲另类| 欧美三级电影大全| 国产精品欧美一区二区三区奶水 | 国产视频一区二区在线观看| 国产精品永久免费| 国产一区美女| 亚洲国产一区二区三区高清| 亚洲每日在线| 欧美一区观看| 欧美激情一区三区| 一区二区三区波多野结衣在线观看| 这里只有视频精品| 久久免费视频在线观看| 欧美日本韩国| 一色屋精品视频免费看| 欧美喷水视频| 亚洲福利专区| 亚洲最新视频在线播放| 午夜日韩av| 欧美精品久久久久久久久老牛影院| 欧美日韩在线高清| 尤物在线精品| 欧美尤物巨大精品爽| 亚洲日本电影| 久色婷婷小香蕉久久| 国产精品美女主播| 亚洲精品一区久久久久久| 香蕉久久国产| 亚洲美女电影在线| 麻豆91精品| 国产一区二区三区四区老人| 一卡二卡3卡四卡高清精品视频| 欧美亚洲在线观看| 亚洲国产精品欧美一二99| 小嫩嫩精品导航| 欧美三级在线视频| 日韩视频在线播放| 欧美电影专区| 久久riav二区三区| 国产欧美日韩在线播放| 亚洲影视在线播放| 日韩视频永久免费观看| 嫩草成人www欧美| 一区二区三区在线看| 久久精品一区二区国产| 亚洲图片欧洲图片av| 欧美三区在线视频| 一本大道久久a久久精品综合| 欧美大片在线看| 麻豆成人在线| 亚洲精品乱码久久久久| 欧美成人69av| 蜜臀a∨国产成人精品| 樱桃成人精品视频在线播放| 久久久久久综合| 久久久午夜精品| 在线成人av.com| 欧美大片免费观看| 欧美国产极速在线| 99re66热这里只有精品3直播| 亚洲国产精品久久久久秋霞蜜臀 | 亚洲欧美综合精品久久成人| 亚洲精品视频一区| 欧美日韩免费观看一区| 中国亚洲黄色| 亚洲午夜精品视频| 国产亚洲在线| 欧美激情一区二区| 欧美另类视频在线| 亚洲香蕉伊综合在人在线视看| av成人免费在线| 日韩一级大片| 国产一区二区精品久久91| 日韩亚洲欧美一区二区三区| 亚洲免费黄色| 国产精品亚洲产品| 久久全国免费视频| 麻豆国产va免费精品高清在线| 亚洲青涩在线| 亚洲免费在线观看视频| 亚洲高清视频一区| 亚洲先锋成人| 亚洲高清自拍| 一区二区三区精品| 韩日欧美一区| 日韩视频欧美视频| 韩国av一区二区三区| 亚洲电影免费观看高清完整版在线| 欧美人与禽猛交乱配| 欧美一级大片在线免费观看| 久久精品一二三区| 亚洲网友自拍| 免费成人美女女| 久久aⅴ国产欧美74aaa| 欧美韩国日本综合| 久久精品国产亚洲5555| 欧美多人爱爱视频网站| 久久国产婷婷国产香蕉| 欧美精品久久久久久久免费观看| 久久精品国产欧美亚洲人人爽| 欧美精品一区三区| 免费黄网站欧美| 国产精品视频免费观看www| 欧美福利视频在线观看| 国产精品中文字幕欧美| 亚洲精品乱码久久久久久黑人 | 国产精品一卡二卡| 最新高清无码专区| 激情小说另类小说亚洲欧美 | 欧美国产视频在线观看| 久久全国免费视频| 国产伦精品一区二区三区高清| 亚洲区欧美区| 亚洲人精品午夜| 久久女同精品一区二区| 欧美一区中文字幕| 国产精品久久久久毛片大屁完整版| 亚洲电影免费观看高清完整版在线观看 | 国产日韩欧美不卡| 亚洲特黄一级片| 一区二区三区日韩精品| 欧美成人伊人久久综合网| 欧美不卡三区| 亚洲大片av| 老司机67194精品线观看| 久久五月天婷婷| 国产亚洲欧美一区| 欧美一区二区三区四区高清| 欧美在线视频免费观看| 国产精品一级久久久| 亚洲女人天堂成人av在线| 亚洲免费视频成人| 99精品国产99久久久久久福利| 国产精品久久久久秋霞鲁丝| 99精品欧美一区二区蜜桃免费| 亚洲巨乳在线| 欧美国产日韩二区| 亚洲欧洲视频| 亚洲一区bb| 国产精品亚洲激情| 久久丁香综合五月国产三级网站| 久久久久亚洲综合| 在线观看中文字幕不卡| 免费永久网站黄欧美| 亚洲精品无人区| 亚洲自拍偷拍视频| 国产欧美一区二区精品秋霞影院 | 亚洲精品久久久久久久久久久久久 | 欧美人与禽猛交乱配| 一本色道久久加勒比精品| 亚洲综合视频网| 国产一区二区三区不卡在线观看| 久久精品亚洲一区二区三区浴池 | 欧美制服丝袜第一页| 欧美777四色影视在线| 亚洲人精品午夜在线观看| 欧美日韩亚洲不卡| 午夜精品视频在线观看| 欧美国产三级| 亚洲欧美国产制服动漫| 一区二区三区中文在线观看| 欧美激情黄色片| 亚洲综合国产精品| 欧美成人免费播放| 亚洲一区国产一区| 尤物视频一区二区| 欧美色综合天天久久综合精品| 午夜综合激情| 亚洲精品少妇| 久久亚洲精品一区二区| 在线视频精品一区| 在线播放不卡| 国产精品久久久久久久久久妞妞| 久久免费视频网站| 亚洲一区欧美二区| 亚洲激情小视频| 久久久久久久久久看片| 亚洲一区久久久| 亚洲国产精品一区二区第一页| 国产精品美女xx| 欧美裸体一区二区三区| 久久久99国产精品免费| 亚洲午夜在线观看| 亚洲另类视频| 亚洲福利在线观看| 麻豆成人综合网| 欧美亚洲视频| 亚洲免费一在线| 一区二区三区国产精华| 亚洲国产精品久久久久| 国产自产精品| 国产日韩欧美一区二区三区在线观看 | 蜜乳av另类精品一区二区| 午夜视频一区二区| 亚洲少妇最新在线视频| 亚洲精品日本| 亚洲欧洲在线播放|