• <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>
            

    
            

            




            







												


        
			
			


			
            
				
					
	
            
		
            
			pku 3252
		
            
		
            2009年10月29日 星期四

            題目鏈接：PKU 3252 Round Numbers

            分類：排列組合+區(qū)間計(jì)數(shù)

            題目分析與算法原型
                     這道題目總的來說不是太難，但是實(shí)現(xiàn)起來細(xì)節(jié)比較多，所以WA了好多次，大致思路是，給你的兩個(gè)數(shù)，start和end ，分別求出1到start，以及1到end之間（包括start和end自身）的round number 的個(gè)數(shù)，然后兩個(gè)相減一下，就差不多是要求的數(shù)，當(dāng)然了還需判斷一下start是不是也是round number是的話剛才減的結(jié)果還要加1。假設(shè)現(xiàn)在給你的數(shù)是a,那么求1到a之間的round number可以分兩步來進(jìn)行，先求出a在二進(jìn)制下的位數(shù)m，然后求出1到m-1位的二進(jìn)制數(shù)的round number的和（這個(gè)不難，只是排列組合的計(jì)算），第二步就是要加上，二進(jìn)制位數(shù)為m但《=a的所有二進(jìn)制數(shù)中round number的個(gè)數(shù)。其實(shí)可以這樣考慮，設(shè)一個(gè)二進(jìn)制數(shù)為101001100，那么從100000000到其之間的round number的數(shù)的個(gè)數(shù)可以這樣考慮，從第二位開始左往右掃描，碰到為1的時(shí)候?qū)⑵渥優(yōu)?，然后此位后的位數(shù)任意組合的數(shù)都肯定小于原來的數(shù)，枚舉這個(gè)情況下（先記下當(dāng)前0和1的個(gè)數(shù)，方便計(jì)算剩下的位數(shù)組合中round number的數(shù)目）的round number數(shù)目，然后繼續(xù)掃描一直到最后。
                    PS：此題代碼實(shí)現(xiàn)的有些繁瑣，有待改進(jìn)..........

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


	


            
	    
    




            



            


            

	
            
		
		
            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            
		
            
		
				
		
		
		
            
		
            			
		
		
		
		
            
		
            
			
		
            
		
            
			
		
            
		
            
			
            網(wǎng)站導(dǎo)航:
			博客園  
			IT新聞  
			BlogJava  			
			博問  
			Chat2DB  
			管理
			
            		
		
            
		
            
			
				

            


            

            		
		
            
	
            	

            



            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年9月>
            
	
            日一二三四五六
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789
            

            

					

            導(dǎo)航
            

					

            統(tǒng)計(jì)
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評(píng)論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評(píng)論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



一本色道久久88综合日韩精品
|
久久精品欧美日韩精品|
狠狠色伊人久久精品综合网
|
国产精品久久久久9999|
久久精品国产亚洲AV不卡|
久久99久久成人免费播放|
女人香蕉久久**毛片精品|
精品久久久久中文字幕日本|
一本久久a久久精品vr综合|
久久久久久免费视频|
国产精品久久久久久久久软件|
无码乱码观看精品久久|
久久夜色精品国产|
欧美成人免费观看久久|
久久久久久国产a免费观看黄色大片|
精品99久久aaa一级毛片|
久久国产成人精品国产成人亚洲|
91精品日韩人妻无码久久不卡|
久久国产精品99久久久久久老狼|
97久久香蕉国产线看观看|
91精品国产综合久久婷婷|
欧美日韩中文字幕久久伊人|
亚洲国产精品久久久久|
久久99热这里只有精品国产|
欧美激情精品久久久久久|
波多野结衣久久精品|
精品国产一区二区三区久久久狼|
91精品国产综合久久精品|
国内精品伊人久久久久影院对白|
香蕉aa三级久久毛片|
人妻无码αv中文字幕久久琪琪布|
国内精品伊人久久久久av一坑|
97精品伊人久久大香线蕉app
|
国产精品熟女福利久久AV|
亚洲国产精品无码久久九九|
一本久久知道综合久久|
国产精品久久久久久一区二区三区|
国产成人精品久久亚洲|
久久只这里是精品66|
99久久免费国产精品热|
久久久精品久久久久久|