NOIP初賽試題分類匯總_完善程序部分

1、NOIP初賽試題匯總完善程序'20041.Joseph題目描述：原始的Joseph問題的描述如下：有n人圍坐在一個(gè)圓桌周圍，把這n個(gè)人依次編號(hào)為1,，no從編號(hào)是1的人開始報(bào)數(shù)，數(shù)到第mt人出列，然后從出列的下一個(gè)人重新開始報(bào)數(shù)，數(shù)到第m個(gè)人又出列，如此反復(fù)直到所有的人全部出列為止。比如當(dāng)n=6,m=5勺時(shí)候，出列的順序依次是5,4,6,2,3,1?，F(xiàn)在的問題是：假設(shè)有k個(gè)好人和k個(gè)壞人。好人的編號(hào)的1到k,壞人的編號(hào)是k+1到2k。我們希望求出m勺最小值，使得最先出列的k個(gè)人都是壞人。輸入：僅有的一個(gè)數(shù)字是k(0<k<14)。輸出：使得最先出列的k個(gè)人都是壞人的m勺最小值

2、。輸入樣例：4輸出樣例：30程序：#include<>longk,m,begin;intcheck(longremain)longresult=()remain;if(|):begin=result;return1;elsereturn0;intmain()longi,find=0;scanf("%ld",&k);for(m=k;；m+)find=1;begin=0;for(i=0;i<k;i+)if(!check()find=0;break;printf（"%ldn",|）;return0;2.邏輯游戲題目描述：一個(gè)同學(xué)給了我

3、一個(gè)邏輯游戲。他給了我圖1,在這個(gè)圖上，每一段邊界都已經(jīng)進(jìn)行了編號(hào)。我的任務(wù)是在圖中畫一條連續(xù)的曲線，使得這條曲線穿過每一個(gè)邊界一次且僅穿過一次，而且曲線的起點(diǎn)和終點(diǎn)都在這整個(gè)區(qū)域的外面。這條曲線是容許自交的。對(duì)于圖1,我的同學(xué)告訴我畫出這樣的一條曲線（圖2）是不可能的，但是對(duì)于有的圖形（比如圖3）,畫出這樣一條曲線是可行的。對(duì)于給定的一個(gè)圖，我想知道是否可以畫出滿足要求的曲線。圖1圖2圖3圖4輸入：輸入的圖形用一個(gè)nxn的矩陣表示的。矩陣的每一個(gè)單元里有一個(gè)0到255之間（包括0和255）的整數(shù)。處于同一個(gè)區(qū)域的單元里的數(shù)相同，相鄰區(qū)域的數(shù)不同（但是不相鄰的區(qū)域里的數(shù)可能相同）。輸入的第一行

4、是n（0<n<100）。以下的n行每行包括n個(gè)整數(shù)，分別給出對(duì)應(yīng)的單元里的整數(shù)（這n4整數(shù)之間用空格分開）。圖4給出了輸入樣例對(duì)應(yīng)的圖形。輸出：當(dāng)可以畫出滿足題意的曲線的時(shí)候，輸出“YES;否則，輸出“NO。輸入樣例：3112122112輸出樣例：YES程序：#include<>#include<>intorig,n,ns,a102102,bun;intd=1,0,-1,0,0,1,voidplimba(intx,inty)inti,x1,y1;axy=-axy;if(abs(ax-1y)!=orig&&(!=ax-1y|abs(axy-1)

5、!=orig)ns+;if(abs(ax+1y)!=orig&&(ax+1y-1!=ax+1y|abs(axy-1)!=orig)ns+;if(abs(axy-1)!=orig&&(!=axy-1|abs(ax-1y)!=orig)ns+;if(abs(axy+1)!=orig&&(ax-1y+1!=axy+1|abs(ax-1y)!=orig)ns+;for(i=0;i<4;i+)x1=x+d2*i;y1=y+;if(x1>=1&&x1<=n&&y1>=1&&y1<=

6、n&&)plimba(x1,y1);)intmain()inti,j;bun=1;scanf("%d",&n);for(i=0;i<=n+1;i+)for(j=0;j<=n+1;j+)aij=0;a00=-1;an+10=-1;a0n+1=-1;an+1n+1=-1;for(i=1;i<=n;i+)for(j=1;j<=n;j+)scanf("%d",&(aij);for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(aij>-1)ns=0;；plimba(i,j)

7、;if(ns%2=1)bun=0;)if(bun)printf("YESn");elseprintf("NOn");return0;'20051木材加工題目描述:木材廠有一些原木，現(xiàn)在想把這些木頭切割成一些長度相同的小段木頭(木頭有可能有剩余)，需要得到的小段的數(shù)目是給定了的。當(dāng)然，我們希望得到的小段越長越好，你的任務(wù)是計(jì)算能夠得到的小段木頭的最大長度。木頭長度的單位是cm。原木的長度都是正整數(shù)，我們要求切割得到的小段木頭的長度也是正整數(shù)。輸入:第一行是兩個(gè)正整數(shù)N和K(1&N&10000,1&K<10000),N是

8、原木的數(shù)目,K是需要得到的小段的數(shù)目。接下來的N行，每行有一個(gè)1到10000之間的正整數(shù)，表示一根原木的長度。輸出:輸出能夠切割得到的小段的最大長度。如果連1cm長的小段都切不出來，輸出“0”。輸入樣例:37232124456輸出樣例:114程序：#include<>intn,k,len10000;intisok(intt)intnum=0,i;for(i=0;i<n;i+)if(num>=k)break;num=;if()return1;elsereturn0;intmain()inti,left,right,mid;scanf("%d%d",&a

9、mp;n,&k);right=0;for(i=0;i<n;i+)scanf("%d",&(leni);if(right<leni)right=leni;right+;while(<right)mid=(left+right)/2;if()right=mid;elseleft=mid;printf("%dn",left);return0;2N叉樹題目描述:我們都了解二叉樹的先根遍歷，中根遍歷和后根遍歷。當(dāng)知道先根遍歷的結(jié)果和中根遍歷結(jié)果的時(shí)候，我們可以唯一的確定二叉樹；同樣的，如果知道了后根遍歷的結(jié)果和中根遍歷結(jié)果，二叉樹

10、也是唯一確定的。但是如果只知道先根遍歷和后根遍歷的結(jié)果，二叉樹就不是唯一的了。但是我們可以計(jì)算滿足條件的不同二叉樹的一共有多少個(gè)。這不是一個(gè)很困難的問題，稍微復(fù)雜一點(diǎn)，我們把這個(gè)問題推廣到N叉樹。我們用小寫英文字母來表示N叉樹的結(jié)點(diǎn)，不同的結(jié)點(diǎn)用不同的字母表示。比如，對(duì)于4叉樹，如果先根遍歷的結(jié)果是abdefgc，后根遍歷的結(jié)果是defgbca，那么我們可以得到6個(gè)不同的4叉樹(如下圖)。輸入:輸入數(shù)據(jù)包括3行。第一行是一個(gè)正整數(shù)N(1<NW20),表示我們要考慮N叉樹。第二行和第三行分別是兩個(gè)字符串序列，分別表示先根遍歷和后根遍歷的結(jié)果。輸出:輸出不同的N叉樹的數(shù)目。題目中給的數(shù)據(jù)保證

11、得到的結(jié)果小于231輸入樣例:4abdefgcdefgbca輸出樣例:6程序：#include<>#include<>charstr1100,str2100;intN;longcom100100;longgetcom(intx,inty)if(y=0|x=y);elseif(comxy!=0)returncomxy;elsecomxy=getcom(x-1,y)+returncomxy;longcount(inta,intb,intc)longsum=1;intk=0;ints=a+1,t=c,p;if(a=b)return1;while(s<=b)p=t;whi

12、le(str1s!=str2t)t+;sum=sum*count(s,s+t-p,p);s=;k+;return*getcom(N,k);intmain()intlen;scanf("%d",&N);scanf("%s%s",str1,str2);len=strlen(str1);n",count();return0;'20061 (選排列)下面程序的功能是利用遞歸方法生成從1到n(n<10)的n個(gè)數(shù)中取k(1<=k<=n)個(gè)數(shù)的全部可能的排列(不一定按升序輸出)。例如，當(dāng)n=3，k=2時(shí)，應(yīng)該輸出(每行輸出5

13、個(gè)排列)：121321233231程序：#include<>intn,k,a10;longcount=0;voidperm2(intj)inti,p,t;if()for(i=k;i<=n;i+)count+;t=ak;ak=ai;ai=t;for()printf("%1d",ap);/*"%1d"中是數(shù)字1，不是字母l*/printf("");t=ak;ak=ai;ai=t;if(count%5=0)printf("n");return;for(i=j;i<=n;i+)t=aj;aj=ai;

14、ai=t;t=aj;main()inti;printf("nEntryn,k(k<=n):n");scanf("%d%d",&n,&k);for(i=1;i<=n;i+)ai=i;2. (TSP問題的交叉算子)TSP問題(TravelingSalesmanProblem)描述如下：給定n個(gè)城市，構(gòu)成一個(gè)完全圖，任何兩城市之間都有一個(gè)代價(jià)(例如路程、旅費(fèi)等)，現(xiàn)要構(gòu)造遍歷所有城市的環(huán)路，每個(gè)城市恰好經(jīng)過一次，求使總代價(jià)達(dá)到最小的一條環(huán)路。遺傳算法是求解該問題的一個(gè)很有效的近似算法。在該算法中，一個(gè)個(gè)體為一條環(huán)路，其編碼方法之一是

15、1到n這n個(gè)數(shù)字的一個(gè)排列，每個(gè)數(shù)字為一個(gè)城市的編號(hào)。例如當(dāng)n=5時(shí)，“34215”表示該方案實(shí)施的路線為3->4->2->1->5->3。遺傳算法的核心是通過兩個(gè)個(gè)體的交叉操作，產(chǎn)生兩個(gè)新的個(gè)體。下面的程序給出了最簡單的一種交叉算法。具體過程如下：(1) 選定中間一段作為互換段，該段的起止下標(biāo)為t1，t2，隨機(jī)生成t1，t2后，互換兩段。(2) 互換后，在每個(gè)新的排列中可能有重復(fù)數(shù)字，因而不能作為新個(gè)體的編碼，一般再做兩步處理：將兩個(gè)互換段中，共同的數(shù)字標(biāo)記為0，表示已處理完。將兩個(gè)互換段中其余數(shù)字標(biāo)記為1，按順序?qū)⒒Q段外重復(fù)的數(shù)字進(jìn)行替換。例如：n=12,兩

16、個(gè)個(gè)體分別是：a1:1354*2679*1012811a2:32112*671011*8549t1=5，t2=8。上述每一行中，兩個(gè)星號(hào)間的部分為互換段。假定數(shù)組的下標(biāo)從1開始，互換后有：a1:1354*671011*1012811a2:32112*2679*8549然后，將數(shù)字6,7對(duì)應(yīng)的項(xiàng)標(biāo)記為0，星號(hào)內(nèi)數(shù)字2,9,10,11對(duì)應(yīng)的項(xiàng)標(biāo)記為1，并且按順序?qū)?yīng)關(guān)系為:10<->2，11<->9。于是，將a19=10替換為a19=2，將a22=2替換為a22=10，類似再做第2組替換。這樣處理后，就得到了兩個(gè)新個(gè)體：a1:135467101121289a2:310112

17、267985411(3)輸出兩個(gè)新個(gè)體的編碼。(4)程序：#include<>#include<>#defineN20inta1N,a2N,kz1N,kz2N，n;intrand1(intk)intt=0;while(t<2|t>k)t=(int)(double)rand()/RAND_MAX*k);returnt;voidread1(inta,intm)讀入數(shù)組元素a1至am，a0=0，略。voidwrt1(inta,intm)輸出數(shù)組元素a1至am，略。voidcross(inta1,inta2,intt1,intt2,intn)inti,j,k,t,k

18、j;for(i=t1;i<=t2;i+)t=a1i;；for(i=1;i<=n;i+)if(i<t1|i>t2)kz1i=kz2i=-1;else；for(i=t1;i<=t2;i+)for(j=t1;j<=t2;j+)if(a1i=a2j);break;for(i=t1;i<=t2;i+)if(kz1i=1)for(j=t1;j<=t2;j+)if(kz2j=1)kj=j;break;for(j=1;j<=n;j+)if()a1j=a2kj;break;for(j=1;j<=n;j+)if()a2j=a1i;break;kz1i=k

19、z2kj=0;main()intk,t1,t2;printf("input(n>5):n");scanf("%d",&n);printf("inputarray1(%d'numbers):n",n);read1(a1,n);printf("inputarray2(%d'numbers):n",n);read1(a2,n);t1=rand1(n-1);dot2=rand1(n-1);while(t1=t2);if(t1>t2)k=t1;t1=t2;t2=k;wrt1(a1,n);w

20、rt1(a2,n);'20071(格雷碼，GrayCode)格雷碼是對(duì)十進(jìn)制數(shù)的一種二進(jìn)制編碼。編碼順序與相應(yīng)的十進(jìn)制數(shù)的大小不一致。其特點(diǎn)是：對(duì)于兩個(gè)相鄰的十進(jìn)制數(shù)，對(duì)應(yīng)的兩個(gè)格雷碼只有一個(gè)二進(jìn)制位不同。另外，最大數(shù)與最小數(shù)之間也僅有一個(gè)二進(jìn)制位不同，以4位二進(jìn)制數(shù)為例，編碼如下：十進(jìn)制數(shù)格雷碼十進(jìn)制數(shù)格雷碼00000811001000191101200111011113001011111040110121010501111310116010114100170100151000如果把每個(gè)二進(jìn)制的位看作一個(gè)開關(guān)，則將一個(gè)數(shù)變?yōu)橄噜彽牧硪粋€(gè)數(shù)，只須改動(dòng)一個(gè)開關(guān)。因此，格雷碼廣泛用于信號(hào)處

21、理、數(shù)-模轉(zhuǎn)換等領(lǐng)域。下面程序的任務(wù)是：由鍵盤輸入二進(jìn)制數(shù)的位數(shù)n(n<16)，再輸入一個(gè)十進(jìn)制數(shù)m(0Km<2n),然后輸出對(duì)應(yīng)于m的格雷碼(共n位，用數(shù)組gr口存放)。為了將程序補(bǔ)充完整，你必須認(rèn)真分析上表的規(guī)律，特別是對(duì)格雷碼固定的某一位，從哪個(gè)十進(jìn)制數(shù)起，由0變?yōu)?，或由1變?yōu)?。#include<>main()intbound=1,m,n,i,j,b,p,gr15;printf("inputn,mn");scanf("%d%d",&n,&m);for(i=1;i<=n;i+)bound=;if(m&

22、lt;0|m>=bound)printf("Dataerror!n");b=1;for(i=1;i<=n;i+)p=0;b=b*2;for(;j<=m;j+)if()p=1-p;gri=p;for(i=n;)printf("%1d",gri);/*在"%1d"中出現(xiàn)的是數(shù)字1，不是字母l*/printf("n");2 (連續(xù)郵資問題)某國發(fā)行了n種不同面值的郵票，并規(guī)定每封信最多允許貼m張郵票，在這些約束下，為了能貼出1,2,3，maxvalue連續(xù)整數(shù)集合的所有郵資，并使maxvalue的值最大

23、，應(yīng)該如何設(shè)計(jì)各郵票的面值例如，當(dāng)n=5、m=4時(shí)，面值設(shè)計(jì)為1,3,11,15,32，可使maxvalue達(dá)到最大值70(或者說，用這些面值的1至4張郵票可以表示不超過70的所有郵資，但無法表示郵資71。而用其他面值的1至4張郵票如果可以表示不超過k的所有郵資，必有k<70)。下面是用遞歸回溯求解連續(xù)郵資問題的程序。數(shù)組x1:n表示n種不同的郵票面值，并約定各元素按下標(biāo)是嚴(yán)格遞增的。數(shù)組bestx1:n存放使maxvalue達(dá)到最大值的郵票面值(最優(yōu)解)，數(shù)組ymaxl用于記錄當(dāng)前已選定的郵票面值x1:i能貼出的各種郵資所需的最少郵票張數(shù)。請(qǐng)將程序補(bǔ)充完整。#include<&g

24、t;#defineNN20#definemaxint30000#definemaxl500/*郵資的最大值*/intn,m,bestxNN,xNN,ymaxl,maxvalue=0;voidresult()輸出結(jié)果：最大值：maxvalue及最優(yōu)解：bestx1:n(略)voidbacktrace(inti,intr)intj,k,zmaxl;for(j=0;j<=;j+)if(yj<m)for(k=1;k<=m-yj;k+)if(yj+k<=y)y=yj+k;while(yr<maxint)r+;if(i>n)if(r-1>maxvalue)maxv

25、alue=;for(j=1;j<=n;j+)bestxj=xj;return;for(k=0;k<maxl;k+)zk=yk;for(j=;j<=r;j+)xi=j;for(k=0;k<maxl;k+)yk=zk;voidmain()intj;printf("inputn,m:n");scanf(“%d%”d,&n,&m);for(j=1;j<maxl;j+)yj=maxint;y0=0;x0=0;x1=1;backtrace(2,1);result();'20081 (找第k大的數(shù))給定一個(gè)長度為1,000,000的無

26、序正整數(shù)序列，以及另一個(gè)數(shù)n(1<=n<=1000000)，接下來以類似快速排序的方法找到序列中第n大的數(shù)(關(guān)于第n大的數(shù)：例如序列1，2，3，4，5，6中第3大的數(shù)是4)。#include<>#include<>inta1000001,n,ans=-1;voidswap(int*a,int*b)intc;c=*a;*a=*b;*b=c;intFindKth(intleft,intright,intn)inttmp,value,i,j;if(left=right)returnleft;tmp=rand()%(right-left)+left;swap(&atmp,&aleft);value=CDi=left;j=right;while(i<j)while(i<j&&g)j-;if(i<j)ai=aj;i+;elsebreak;while(i<j&&)i+;if(i<j)aj=ai;j-;elsebreak;®if(i<n)returnFindKth(®);if(i>n)returnreturni;intmain()inti;intm=1000000;for(i=1;i<=m;i+)scanf(&qu