1、NOIP2011普及組復賽1數字反轉（ reverse.cpp/c/pas）【問題描述】給定一個整數，請將該數各個位上數字反轉得到一個新數。新數也應滿足整數的常見形式，即除非給定的原數為零，否則反轉后得到的新數的最高位數字不應為零。（參見樣例2）【輸入】輸入文件名為 reverse.in 輸入共一行，一個整數。N。【輸出】輸出文件名為reverse.out。輸出共 1 行，一個整數，表示反轉后的新數。【輸入輸出樣例1】reverse.in123reverse.out321【輸入輸出樣例2】reverse.in-380reverse.out-83【數據范圍】-1,000,000,000 N1,0

2、00,000,000 。【解題】 這道題非常簡單，可以讀字符串處理，也可以讀數字來處理，只不過要注意符號問題（以及-0 ，但測試數據沒出） 。【法一】字符串處理Var i,l,k:integer;s:string;p:boolean;beginassign(input, 'reverse.in');reset(input);assign(output, 'reverse.out');rewrite(output);readln(s);l:=length(s);k:=1;if s1='-' thenbeginwrite('-');k

3、:=2;end;p:=true;for i:=l downto k dobeginif(p)and(si='0') then continueelsebeginwrite(si);p:=false;end;end;close(input);close(output);end.【法二】數字處理Var f:integer;n,ans:longint;beginassign(input, 'reverse.in');reset(input);assign(output, 'reverse.out');rewrite(output);readln(n);

4、if n<0 thenbeginf:=-1;n:=-n;endelsef:=1;ans:=0;while n<>0 dobeginans:=ans*10+n mod 10;n:=n div 10;end;ans:=ans*f;writeln(ans);close(input);close(output);end.2. 統計單詞數 (stat.pas/c/cpp)【問題描述】一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有的還能統計出特定單詞在文章中出現的次數。現在，請你編程實現這一功能，具體要求是：給定一個單詞，請你輸出它在給定的文章中出現的次

5、數和第一次出現的位置。 注意：匹配單詞時，不區分大小寫，但要求完全匹配，即給定單詞必須與文章中的某一獨立單詞在不區分大小寫的情況下完全相同（參見樣例1），如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見樣例2）【輸入】 輸入文件名為stat.in， 2 行。第 1 行為一個字符串，其中只含字母，表示給定單詞；第 2 行為一個字符串，其中只可能包含字母和空格，表示給定的文章。【輸出】 輸出文件名為 stat.out。只有一行，如果在文章中找到給定單詞則輸出兩個整數，兩個整數之間用一個空格隔開，分別是單詞在文章中出現的次數和第一次出現的位置（即在文章中第一次出現時，單詞首字母在文章中的位置，

6、位置從 0 開始）；如果單詞在文章中沒有出現，則直接輸出一個整數 -1。【輸入輸出樣例 1】stat.inToto be or not to be is a question【輸入輸出樣例1 解釋】輸出結果表示給定的單詞【輸入輸出樣例2】Tostat.out2 0在文章中出現兩次，第一次出現的位置為0。ostat.out-1Did the Ottoman Empire lose its power at that time【輸入輸出樣例2 解釋】表示給定的單詞to 在文章中沒有出現，輸出整數- 1。【數據范圍】1單詞長度10。1文章長度1,000,000。【解題】這道題也不是很

7、難，program stat;var I,n,p:longint;s,s1:string;c:char;beginassign(input,'stat.in');reset(input);assign(output,'stat.out');rewrite(output);readln(s);s:=upcase(s);/ 函數 upcase()參數可為 char ，也可為 stringi:=-1;/i統計讀入的字符位置，首個字符出現的位置是0s1:=''/s1累加讀入的字符n:=0;/n 統計出現次數p:=-1;/p標記第一次出現的位置repeat

8、read(c);c:=upcase(c);/ 統一大小寫i:=i+1;if c=' ' then/遇到空格，匹配是否相同beginif s=s1 thenbeginn:=n+1;if p=-1 then/p 標記第一次出現的位置，如果p 是第一次更改，記錄位置end;p:=i-length(s);s1:=''endelses1:=s1+c;/ 不是空格，繼續疊加until eoln(input);if s1=s then/ 處理最后一個單詞是否相同的情況beginn:=n+1;if p=-1 thenp:=i-length(s)+1 ;/最后沒有空格end;if

9、 n=0 thenwriteln(-1)else writeln(n,' ',p);close(input);close(output);end.3. 瑞士輪 (swiss.cpp/c/pas)【背景】在雙人對決的競技性比賽，如乒乓球、羽毛球、國際象棋中，最常見的賽制是淘汰賽和循環賽。前者的特點是比賽場數少，每場都緊張刺激，但偶然性較高。后者的特點是較為公平，偶然性較低，但比賽過程往往十分冗長。本題中介紹的瑞士輪賽制，因最早使用于 1895 年在瑞士舉辦的國際象棋比賽而得名。它可以看作是淘汰賽與循環賽的折衷，既保證了比賽的穩定性，又能使賽程不至于過長。【問題描述】2*N名編號為

10、12N的選手共進行R 輪比賽。每輪比賽開始前，以及所有比賽結束后，都會按照總分從高到低對選手進行一次排名。選手的總分為第一輪開始前的初始分數加上已參加過的所有比賽的得分和。總分相同的，約定編號較小的選手排名靠前。每輪比賽的對陣安排與該輪比賽開始前的排名有關：第1名和第2 名、第3名和第 4 名、第 2K 1 名和第 2K 名、第 2N 1 名和第 2N 名，各進行一場比賽。每場比賽勝者得1 分，負者得 0 分。也就是說除了首輪以外，其它輪比賽的安排均不能事先確定，而是要取決于選手在之前比賽中的表現。現給定每個選手的初始分數及其實力值，試計算在R輪比賽過后，排名第Q 的選手編號是多少。我們假設選

11、手的實力值兩兩不同，且每場比賽中實力值較高的總能獲勝。【輸入】輸入文件名為swiss.in。輸入的第一行是三個正整數N、 R、Q，每兩個數之間用一個空格隔開，表示有2*N名選手、 R 輪比賽，以及我們關心的名次Q。第二行是2*N個非負整數 s1, s2, s2N ，每兩個數之間用一個空格隔開，其中si 表示編號為 i 的選手的初始分數。第三行是2*N個正整數 w1, w 2, w2N ，每兩個數之間用一個空格隔開，其中 wi 表示編號為 i 的選手的實力值。【輸出】輸出文件名為swiss.out。輸出只有一行，包含一個整數，即R 輪比賽結束后，排名第Q 的選手的編號。【輸入輸出樣例】swiss

12、.in2 4 2swiss.out176671052015【輸入輸出樣例說明】本輪對陣本輪結束后的得分選手編號/初始/7667第 1 輪 7678第 2 輪 7689第 3 輪 8699第 4 輪 96109【數據范圍】對于30%的數據， 1 N 100；對于50%的數據， 1 N 10,000；對于100%的數據， 1 N 100,000，1 R 50，1Q 2N，0 s1, s2, , s2N 108122N108。，1 w,w , , w【解題】 題目雖然長，但理解題意后就發現解題的瓶頸在于排序。如果每一輪比賽的結果都進行快速排序，時間復雜度為O（Rlongn ），但事實證明這樣只能拿6

13、0 分。如何 AC，這需要一個巧算法：分析得知，快速排序實際上進行了許多無用的工作：如果兩個人在第 i輪都贏了， 那么第 i 輪后的先后關系與第 i-1 輪是一樣的； 反之， 如果兩人都輸了，他們的先后關系也不會變。所以，我們有一個新算法：一開始做一趟快速排序，然后對于每一輪，將此輪的n 個贏者（他們的先后關系和上一輪不變）和n 個輸者（他們的先后關系和上一輪也不變分開，然后就是歸并，于是時間復雜度 O（ Rn）（實踐證明，如果單純的排序 r 次，必然結果是超時。事實上只需一次真正意義上的排序以后，在以后的比賽中，按原順序分成兩組，獲勝組和失敗組，這兩組依然是有序的，再把這兩組歸并成一組，就可

14、以了。總時間復雜度O(N*R) ）program swiss;vara,b,v:array1.200000of longint;c,d:array1.100000,1.2of longint;n,r,q,i,j:longint;procedure qsort(l,r:longint);vari,j,mid1,mid2,t:longint;begini:=l;j:=r;mid1:=a(l+r)div 2; mid2:=v(l+r)div 2;repeat/按分數從高到低排序，分數相同的，編號較小的選手排名靠前while (ai>mid1) or (ai=mid1) and (vi<m

15、id2) do inc(i);while (aj<mid1) or (aj=mid1) and (vj>mid2) do dec(j);if i<=j thenbegint:=ai;ai:=aj;aj:=t;t:=vi;vi:=vj;vj:=t;inc(i);dec(j);end;until i>j;if i<r then qsort(i,r);if l<j then qsort(l,j);end;procedure mergesort;/ 歸并排序var i,l1,l2:longint;begini:=0;l1:=1;l2:=1;repeatif (cl1

16、,1>dl2,1)or (cl1,1=dl2,1)and(cl1,2<dl2,2) thenbegini:=i+1;ai:=cl1,1;vi:=cl1,2;l1:=l1+1;endelsebegini:=i+1;ai:=dl2,1;vi:=dl2,2;l2:=l2+1;end;until (l1>n)or(l2>n);while l1<=n dobegini:=i+1;ai:=cl1,1;vi:=cl1,2;l1:=l1+1;end;while l2<=n dobegini:=i+1;ai:=dl2,1;vi:=dl2,2;l2:=l2+1;end;end;

17、begin/ 主程序assign(input,'swiss.in');reset(input);assign(output,'swiss.out');rewrite(output);readln(n,r,q);for i:= 1 to n*2 do read(ai);/ 數組 a 保存初始分數for i:= 1 to n*2 do read(bi);/數組 b 保存實力值for i:=1 to n*2 do vi:=i;/數組 vi 保存排名第 i 的選手編號qsort(1,2*n);for i:= 1 to r dobeginfor j:= 1 to n do

18、if bv2*j-1>bv2*j thenbegininc(a2*j-1);cj,1:=a2*j-1;/數組 cj,1保存嬴方的總分；數組cj,2保存嬴方的號碼；cj,2:=v2*j-1;dj,1:=a2*j;/數組 dj,1保存輸方的總分；數組dj,2保存輸方的號碼；dj,2:=v2*j;endelsebegininc(a2*j);cj,1:=a2*j;cj,2:=v2*j;dj,1:=a2*j-1;dj,2:=v2*j-1;end;mergesort;end;writeln(vq);close(input);close(output);end.4.表達式的值 (exp.cpp/c/p

19、as)【問題描述】對于 1 位二進制變量定義兩種運算：運算符運算規則0=000 1=11 0=11 1=1×0×0=00×1=01×0=01×1=1運算的優先級是：1. 先計算括號內的，再計算括號外的。2. “×”運算優先于“”運算 ，即計算表達式時， 先計算×運算，再計算運算 。例如：計算表達式AB × C 時，先計算 B × C，其結果再與A 做運算。現給定一個未完成的表達式，例如_+(_*_) ，請你在橫線處填入數字0 或者 1，請問有多少種填法可以使得表達式的值為0。【輸入】輸入文件名為exp.i

20、n，共 2 行。第 1 行為一個整數 L，表示給定的表達式中 除去橫線外 的運算符和括號的個數。第 2 行為一個字符串包含 L 個字符，其中只包含 （ 、 ）、 +、這*4 種字符，其中 （ 、 ） 是左右括號， +、分*別表示前面定義的運算符“”和“×”。這行字符按順序給出了給定表達式中除去變量外的運算符和括號。【輸出】輸出文件exp.out 共1 行。包含一個整數，即所有的方案數。注意：這個數可能會很大，請輸出方案數對10007 取模后的結果。【輸入輸出樣例1】exp.inexp.out43+(*)【輸入輸出樣例說明】給定的表達式包括橫線字符之后為：_+(_*_)在橫線位置填入(

21、0、 0、 0)、 (0、 1、0)、 (0、0、 1)時，表達式的值均為0，所以共有 3 種填法。【數據范圍】對于20%的數據有 0 L 10。對于50%的數據有 0 L 1,000。對于70%的數據有 0 L 10,000。對于100%的數據有 0 L 100,000。對于50%的數據輸入表達式中不含括號。【解題】算法類似于表達式計算，一個符號棧，兩個數據棧。記f(s,0) 表示表達式s 為 0 的方案數， f(s,1) 表示表達式 s 為 1 的方案數。f(a+b,0) = f(a,0)*f(b,0)f(a+b,1) = f(a,0)*f(b,0)+f(a,0)*f(b,1)+f(a,1

22、)*f(b,0)f(a*b,0)=f(a,0)*f(b,0) + f(a,1)*f(b,0) + f(a,0)*f(b,1)f(a*b,1) = f(a,1) * f(b,1)program exp;const maxn= 100010; op:array1.4 of char = ('(','+','*',')'); flag:array1.4,1.4 of char = ( ( ('<','<','<','='), + ('<

23、9;,'>','<','>'), * ('<','>','>','>'), ) ('>','>','>','>');/符號優先級表varstack_op:array1.maxn of char;stack_data0, stack_data1:array1.maxn of longint;n,top_op, top_data, i, len:longint

24、;a0, a1, b0, b1, t0, t1:longint;s: ansistring;ch,now:char;procedure push_op(ch:char);/運算符壓棧begininc(top_op);stack_optop_op:=ch;end;function pop_op:char;/ 運算符出棧beginpop_op:= stack_optop_op;dec(top_op);end;function gettop:char;/取棧頂符號begingettop:=stack_optop_op;end;procedure push_data(a0,a1:longint);/數

25、據壓棧begininc(top_data);stack_data0top_data:=a0;stack_data1top_data:=a1;end;procedure pop_data(vara0,a1:longint);/數據出棧begina0:=stack_data0top_data;a1:=stack_data1top_data;dec(top_data);end;function find(ch:char):integer;/ 讀入符號vari:longint;beginfor i:= 1 to 4 doif opi=ch then exit(i);end;beginassign(input,'exp.in');re