試題、程序及解題報告1000

1、NOIP2005 解題孫慨然第一題：scholar給出 N（1N100）個人的情況，按照 5 條不同的獎學金條件發(fā)獎金（可重復得獎），求得到最多獎學金的人是誰，并求總獎學金數(shù)。這是一道簡單題，沒更好或更壞的算法。只需按照實際情況模擬即可，每人判斷5 個條件，該發(fā)多少發(fā)多少就行了。要注意的是每人最多得 15850 元，總數(shù)最多 1585000 元，注意長整的使用。#include #define MAXN 100 FILE *fpi,*fpo;char nameMAXN+121; n;main()long s=0,max=0,maxi, money;/*最大人數(shù)*/*人名*/i,mark,clm

2、ark,pchar g,w;r;fpi=fopen(scholar.in,r);fpo=fopen(scholar.out,w);fscanf(fpi,%d,&n); for(i=1;i80 & pr0) money+=8000;/*判斷各個獎*/if(mark85 & clmark80) money+=4000; if(mark90) money+=2000;if(mark85 & w=Y) money+=1000; if(clmark80 & g=Y) money+=850; s+=money;if(moneymax) max=money; maxi=i;fprf(fpo,%sn%ldn%

3、ldn,namemaxi,max,s); fclose(fpi);fclose(fpo);return(0);第二題：river一個青蛙要過一個寬為 P 米（1P109）的河，他一步能跳 S 到 T 米（1ST10），他不喜歡踩到河里的石子（石子數(shù) M100），給出每個石子的坐標，問最少踩到多少石子能過河。這道題在沒看數(shù)據規(guī)模之前以為是一道簡單的 DP，但是數(shù)據開到十億，無論在時間還是空間復雜度都過大，所以就要進行優(yōu)化了。解一：簡單方法：預期得分 30。簡單動態(tài)規(guī)劃，fi代表青蛙跳到 i 點時所可能踩到的最少石子數(shù)，所以有 fi=minfk+mapi(i-ski-t)，其中 mapi代表 i

4、上是否有石子，有是 1，否則 0。算法復雜度O(n2)。解二：改進方法：預期得分 100。會發(fā)現(xiàn)，雖然橋很長，但上面最多只有 100 個石子，想到能否用石子 DP，而應該是的。那能否基于第法？由于石子排布非常的疏，我們還會發(fā)現(xiàn)，如果兩個石子相隔甚遠，那他們中間的 fi大部分將會是同一個數(shù)，能否把兩個石子的距離縮短，使之還與原來等效？要是行的話怎么縮？同學時做了一個方法能夠過全部數(shù)據，用的滾動數(shù)組，下面列出了他的程序。也寫了個程序，和他不盡相同：我令 L=stonei-stonei-1（stonei代表按坐標由小到大順序排列的石塊坐標），當 L 能夠被 t 整除時（L%t=0），令 k=t；當

5、L 不能被 t 整除時（L%t!=0），令 k=L%t。然后令 k 為 k+t，最后判斷如果 kL，那么 map數(shù)組中 stonei和 stonei-1兩石頭的距離就被等效成為 L（也就是沒變）；如果 k=L，那么 map數(shù)組中 stonei和 stonei-1兩石頭的距離就被等效成為 k，可以看出來，這樣處理完，兩石子最大間距為 2*t，大大的縮短了數(shù)組，再按解一進行DP，就可以通過了。：Program River;Varf1, f2 : Text;x, Temp, i, l, s, t, p, q, n : Long; Stone : Array1.100 Of Long;a : Arra

6、y0.9 Ofeger;Procedure Qsort(l, r : Long);Vari, j, x, Temp : Long;Begini := l; j := r; x := Stone(l + r) Shr 1; RepeatWhile Stonei x Do Dec(j); If i j;If j l Then Qsort(l, j); If i = x Then Exit(Stonei); End;End;Function FindStone(x : Long) :Vari : Long; BeginFindStone := False; For i:=1 To n Do Begi

7、nIf Stonei = x Then Exit(True); End;End;Function FindMin(s, t : Long) : Long;Vari, Min : Long;Found :Begin;Min := MaxLong; Found := False; If s = t Then BeginFor i:=s To t Do BeginIf ai 101 Then Found := True;If ai M End;End Else Beginhen Min := ai;For i:=0 To t Do BeginIf ai 101 Then Found := True;

8、If ai MEnd;hen Min := ai;For i:=s To 9 Do BeginIf ai 101 Then Found := True;If ai 10) And (i 10) Then Begin i := i + (Temp - i) Div 10 - 1) * 10;End;p := i Mod 10 - t; q := i Mod 10 - s; If p 0 Then p := p + 10;If q 0 Then q := q + 10; x := FindMin(p, q);If FindStone(i) Then ai Mod 10 := x + 1 Else

9、ai Mod 10 := x; End;Wrin(f2, FindMin(0, 9); Close(f2);End.我：#include #define MAXN 100#define MAXS 100000 FILE *fpi,*fpo;long stoneMAXN+1=0; mapMAXS+1=0;long fMAXS+1=0;s,t,m,p=0,q;void qsort(l,r)/*排序石子*/i,j; long x,t; i=l;j=r;x=stone(i+j)/2; dofor(;stoneix;j-); if(i=j)t=stonei; stonei=stonej; stonej=

10、t;i+; j-;while(i=j); if(ir) qsort(i,r);if(lj) qsort(l,j);main() long l,k;i,j,min; fpi=fopen(river.in,r);fpo=fopen(river.out,w);fscanf(fpi,%ld %d %d %d,&l,&s,&t,&m); for(i=1;i=m;i+) fscanf(fpi,%ld,&stonei); qsort(1,m);for(i=1;i=m;i+) l=stonei-stonei-1; if(l%t=0) k=t;else k=l%t; k+=t; if(lk) k=l; p+=k

11、; mapp=1;for(i=1;i=p+t;i+)/*讀入石子坐標*/*排序*/*縮短數(shù)組，p 為 map 長度*/*動態(tài)規(guī)劃*/mAXN+1;for(j=i-t;j=i-s;j+) if(j0) continue; if(fjmin) min=fj;fi=mapi;mAXN+1;for(i=p+1;i=p+t;i+) if(fimin) min=fi; fprf(fpo,%dn,min);fclose(fpo); fclose(fpi);return(0);/*找最小值*/*輸出*/第三題：fireN 個人先按順序站成一個圈，然后發(fā)布（b1,b2,bk）樣式令，意思是 b1換到 b2 的位

12、置上，b2 換到 b3 的位置上，bk 換到 b1 的位置上，k 為此命令代價。要求用最小的總命令代價調整這個圈，使之變?yōu)槟繕藸顟B(tài)（就是滿足所有人的喜好）。如果不能滿足則輸出“-1”，否則輸出最小代價數(shù)。先看到 50000 的數(shù)據規(guī)模，想到它可能連動態(tài)規(guī)劃都不是，只能考慮 O(N)，O(NlogN)，O(N*k)之類的算法。通過思考可發(fā)現(xiàn)，令有個特點，他點到名的同學的位置都有變化，而其余的位置并不移動。可以證明，一個由 N 個人組成的隊列，發(fā)布命令使之變成一個和此隊列沒有一個同學位置相同的新隊列，所用的最少代價為 N（大家可以思考一下）。所以求最小命令代價轉變成了求最少與目標位置不同，也就是最

13、多與目標位置相同。而且又可以知道，只要有一個初始狀態(tài)，就會通過發(fā)布命令得到目標狀態(tài)，所以當且僅當所有人的喜好構不成一個圈時才不能滿足每個同學的愿望（輸出“-1”）。還要注意，通過輸入數(shù)據得到的是兩個圈，一個正的一個反的?，F(xiàn)在把問題簡化再反過來，問題轉化為：給出一個數(shù)字圈，它與一個遞增圈和一個遞減圈里的數(shù)字重合數(shù)字最多是幾個，用 N 減去這個數(shù)即為所求?？梢赃@樣算：先推出這個圈，把 reduce數(shù)組清零，再順時針把每個人的依次減去 1，2，N（正向），每個結果存為 t，把 t 當作下標（小于 0 的加上 N），讓 reduce0t+；然后順時針把每個人的依次減去N，N-1，1（反向），每個結果存

14、為 t，把 t 當作下標（小于 0 的加上 N），讓 reduce1t+；這樣求出 reduce 數(shù)組中的最大值為 max，輸出N-max 即可。為什么請大家自己思考:-D開始時，讀數(shù)據時間復雜度為 O(N)，生成圈時間復雜度為 O(N)，減數(shù)的時間復雜度為O(2*N)（一正一反），總復雜度約為 O(4*N)，完全受得了，要注意的還是長整問題（使之成為條件反射）。本題應該算動態(tài)規(guī)劃的狀態(tài)壓縮吧，大家如果有更好的算法可以跟我#include 。#define MAXN 50000 FILE *fpi,*fpo;long manMAXN+22;long cercleMAXN+2=0,1; used

15、MAXN+2=0;long reduce2MAXN+2=0; long n,max=0;main()long i,p,q=1,t; fpi=fopen(fire.in,r);fpo=fopen(fire.out,w);fscanf(fpi,%ld,&n);/*最大人數(shù)*/*每個人的左右手各連接誰*/*生成圈的順序*/*狀態(tài)數(shù)組*/for(i=1;i=n;i+) fscanf(fpi,%ld %ld,&mani0,&mani1);p=manq1; for(i=2;i=n+1;i+)if(manq1=p)p=q;/*生成圈*/q=manq0;elseif(manq0!=p) break; p=q;

16、q=manq1;if(usedq) break;else usedq=1; cerclei=q;/*此人三只手*/*此人要拉一個已經拉兩手的人*/if(i=n+1) fprf(fpo,-1n); elsefor(i=1;i=n;i+) if(t=cerclei-i)max) max=reduce0t; if(t=cerclei-n+i-1)max) max=reduce1t;fprf(fpo,%ldn,n-max);fclose(fpi); fclose(fpo); return(0);/*構不成圈*/*正圈*/*判斷最大值*/*反圈*/*判斷最大值*/*輸出*/第四題：equal給出一個多項

17、式，在備選中選擇與之等價的多項式。考的是編譯技術，用通常的方法把多項式轉變?yōu)橐豢枚鏄洌哼\算符為各個非葉節(jié)點，優(yōu)先級越低越靠近根節(jié)點；葉結點是數(shù)值或變量a。如圖：將樣例(a-1)2+4*a 轉化成：再通過加（plus）、減（也是 plus）、乘（mult）、乘方（sqre）運算函數(shù)，把字符串轉變?yōu)樽远x類型：expr（表達式型）。一個 expr 類型的數(shù)據包含：maxtime：最高次數(shù)，coei：i 次項系數(shù)，它可以表示任何一個多項式。最后比較每個備選同（expr 類型數(shù)據相同）的輸出。具體操作看注釋，題目沒，把與給出多項式含義相技巧，就是麻煩。有的同學用往里代數(shù)的方法出解，也可以過，但個人覺

18、得并沒有省事多少。#include #define MAXT 100 FILE *fpi,*fpo;char cequal2751=0; struct nodemaxtime;long coeMAXT+1;equal27=0;typedef struct node expr; n;/*最高次數(shù)*/*字符串型的表達式*/*定義 expr 類型*/*最高次*/*i 次向系數(shù)*/*備選expr 型的表達式*/*備選數(shù)*/left(i;k,x)/*根據右括號位置找相應的左括號位置*/for(i=1;i0;) x-;if(cequalkx=) i+;if(cequalkx=() i-;return(x)

19、;find(i;k,x,y,char ch1,char ch2)/*找 ch1 或 ch2 運算符*/1aa42-*+for(i=y;i=x;i-)if(cequalki=ch1 | cequalki=ch2) return(i); if(cequalki=) i=left(k,i);return(0);/*找到嘍！*/*跳過括號*/*沒找到*/void plus(expr q1,expr q2,expr *bak, i,lng;t)/*多項式加（減）法*/if(q1.maxtimeq2.maxtime) lng=q1.maxtime; else lng=q2.maxtime;for(i=0;

20、i=lng;i+) (*bak).coei=q1.coei+t*q2.coei;while(*bak).coelng=0) lng-; (*bak).maxtime=lng;void mult(expr q1,expr q2,expr *bak) i,j;for(i=0;i=q1.maxtime;i+) for(j=0;j=q2.maxtime;j+)(*bak).coei+j+=q1.coei*q2.coej; (*bak).maxtime=q1.maxtime+q2.maxtime;void sqre(expr q1,expr q2,expr *bak) i;expr q3,z=0; (*

21、bak).coe0=1;for(i=1;i=q2.coe0;i+) q3=z; mult(*bak),q1,&q3); (*bak)=q3;/*多項式乘法*/*多項式乘方*/*清零*/*不斷相乘*/void comput(l,i;k,x,y,expr *bak)/*遞歸調用的 comput 函數(shù)*/*把 x 到 y 的字符串表示為 expr 型返回*/expr q1=0,q2=0; if(cequalky=) & left(k,y)=x)comput(k,x+1,y-1,bak); return;/*如果式子被括號，返回括號內式子*/if(l=find(k,x,y,+,-)=0) l=find(k,x,y,*,*); if(l=0) l=find(k,x,y,);if(l=0)if(cequalkx=a)/*找優(yōu)先級最低的運算符*/*沒有運算符（葉節(jié)點）*/*當為變量 a 時*/(*bak).maxtime=1;(*bak).coe1=1; return;for(i=x;i=y;i+) (*bak).coe0*=10; (*bak).c