NOIP2011普及組復(fù)賽試題+源程序

1、NOIP2011 普及組 復(fù)賽1數(shù)字反轉(zhuǎn)（reverse.cpp/c/pas）【問題描述】給定一個(gè)整數(shù)，請(qǐng)將該數(shù)各個(gè)位上數(shù)字反轉(zhuǎn)得到一個(gè)新數(shù)。新數(shù)也應(yīng)滿足整數(shù)的常見形式，即除非給定的原數(shù)為零，否則反轉(zhuǎn)后得到的新數(shù)的最高位數(shù)字不應(yīng)為零。（參見樣例2）【輸入】 輸入文件名為reverse.in。 輸入共一行，一個(gè)整數(shù)N。【輸出】 輸出文件名為reverse.out。 輸出共1行，一個(gè)整數(shù)，表示反轉(zhuǎn)后的新數(shù)?！据斎胼敵鰳永?】reverse.inreverse.out123321【輸入輸出樣例2】reverse.inreverse.out-380-83【數(shù)據(jù)范圍】 -1,000,000,000N1,

2、000,000,000?！窘忸}】這道題非常簡單，可以讀字符串處理，也可以讀數(shù)字來處理，只不過要注意符號(hào)問題（以及-0，但測試數(shù)據(jù)沒出）?！痉ㄒ弧孔址幚鞻ar i,l,k:integer;s:string;p:boolean;begin assign(input, reverse.in); reset(input); assign(output, reverse.out); rewrite(output); readln(s); l:=length(s); k:=1; if s1=- then begin write(-); k:=2; end; p:=true; for i:=l down

3、to k do begin if(p)and(si=0) then continue else begin write(si); p:=false; end; end; close(input); close(output);end.【法二】數(shù)字處理Var f:integer;n,ans:longint;begin assign(input, reverse.in); reset(input); assign(output, reverse.out); rewrite(output); readln(n); if n0 then begin f:=-1; n:=-n; end else f:=

4、1; ans:=0; while n0 do begin ans:=ans*10+n mod 10; n:=n div 10; end; ans:=ans*f; writeln(ans); close(input); close(output);end.2.統(tǒng)計(jì)單詞數(shù)(stat.pas/c/cpp)【問題描述】一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有的還能統(tǒng)計(jì)出特定單詞在文章中出現(xiàn)的次數(shù)?，F(xiàn)在，請(qǐng)你編程實(shí)現(xiàn)這一功能，具體要求是：給定一個(gè)單詞，請(qǐng)你輸出它在給定的文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置。注意：匹配單詞時(shí)，不區(qū)分大小寫，但要求完全匹配，即給定單詞必

5、須與文章中的某一獨(dú)立單詞在不區(qū)分大小寫的情況下完全相同（參見樣例1），如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見樣例2）【輸入】輸入文件名為 stat.in，2 行。第 1 行為一個(gè)字符串，其中只含字母，表示給定單詞；第 2 行為一個(gè)字符串，其中只可能包含字母和空格，表示給定的文章?！据敵觥枯敵鑫募麨?stat.out。只有一行，如果在文章中找到給定單詞則輸出兩個(gè)整數(shù)，兩個(gè)整數(shù)之間用一個(gè)空格隔開，分別是單詞在文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置（即在文章中第一次出現(xiàn)時(shí)，單詞首字母在文章中的位置，位置從0 開始）；如果單詞在文章中沒有出現(xiàn)，則直接輸出一個(gè)整數(shù)-1?！据斎胼敵鰳永?】s

6、tat.instat.outToto be or not to be is a question2 0【輸入輸出樣例1解釋】輸出結(jié)果表示給定的單詞 To 在文章中出現(xiàn)兩次，第一次出現(xiàn)的位置為0?！据斎胼敵鰳永?】stat.instat.outtoDid the Ottoman Empire lose its power at that time-1【輸入輸出樣例2解釋】表示給定的單詞 to 在文章中沒有出現(xiàn)，輸出整數(shù)-1。【數(shù)據(jù)范圍】1單詞長度10。1文章長度1,000,000?！窘忸}】這道題也不是很難，program stat;var I,n,p:longint;s,s1:string;c:

7、char;begin assign(input,stat.in); reset(input); assign(output,stat.out); rewrite(output); readln(s);s:=upcase(s); / 函數(shù)upcase()參數(shù)可為char，也可為stringi:=-1; /i統(tǒng)計(jì)讀入的字符位置，首個(gè)字符出現(xiàn)的位置是0s1:=; /s1累加讀入的字符n:=0; /n統(tǒng)計(jì)出現(xiàn)次數(shù)p:=-1; /p標(biāo)記第一次出現(xiàn)的位置repeat read(c); c:=upcase(c); /統(tǒng)一大小寫 i:=i+1; if c= then /遇到空格，匹配是否相同 begin if

8、 s=s1 then begin n:=n+1; if p=-1 then /p標(biāo)記第一次出現(xiàn)的位置，如果p是第一次更改，記錄位置 p:=i-length(s); end; s1:=; end else s1:=s1+c; /不是空格，繼續(xù)疊加until eoln(input);if s1=s then /處理最后一個(gè)單詞是否相同的情況 begin n:=n+1; if p=-1 then p:=i-length(s)+1; /最后沒有空格 end;if n=0 then writeln(-1)else writeln(n, ,p); close(input);close(output);en

9、d.3. 瑞士輪(swiss.cpp/c/pas)【背景】在雙人對(duì)決的競技性比賽，如乒乓球、羽毛球、國際象棋中，最常見的賽制是淘汰賽和循環(huán)賽。前者的特點(diǎn)是比賽場數(shù)少，每場都緊張刺激，但偶然性較高。后者的特點(diǎn)是較為公平，偶然性較低，但比賽過程往往十分冗長。本題中介紹的瑞士輪賽制，因最早使用于 1895 年在瑞士舉辦的國際象棋比賽而得名。它可以看作是淘汰賽與循環(huán)賽的折衷，既保證了比賽的穩(wěn)定性，又能使賽程不至于過長?！締栴}描述】2*N 名編號(hào)為12N 的選手共進(jìn)行R 輪比賽。每輪比賽開始前，以及所有比賽結(jié)束后，都會(huì)按照總分從高到低對(duì)選手進(jìn)行一次排名。選手的總分為第一輪開始前的初始分?jǐn)?shù)加上已參加過的所

10、有比賽的得分和。總分相同的，約定編號(hào)較小的選手排名靠前。每輪比賽的對(duì)陣安排與該輪比賽開始前的排名有關(guān)：第 1 名和第2 名、第3 名和第4名、第2K1 名和第2K 名、 、第 2N1 名和第2N 名，各進(jìn)行一場比賽。每場比賽勝者得1 分，負(fù)者得0 分。也就是說除了首輪以外，其它輪比賽的安排均不能事先確定，而是要取決于選手在之前比賽中的表現(xiàn)。現(xiàn)給定每個(gè)選手的初始分?jǐn)?shù)及其實(shí)力值，試計(jì)算在 R 輪比賽過后，排名第Q 的選手編號(hào)是多少。我們假設(shè)選手的實(shí)力值兩兩不同，且每場比賽中實(shí)力值較高的總能獲勝。【輸入】輸入文件名為 swiss.in。輸入的第一行是三個(gè)正整數(shù) N、R、Q，每兩個(gè)數(shù)之間用一個(gè)空格隔開

11、，表示有2*N 名選手、R 輪比賽，以及我們關(guān)心的名次Q。第二行是 2*N 個(gè)非負(fù)整數(shù)s1, s2, , s2N，每兩個(gè)數(shù)之間用一個(gè)空格隔開，其中si 表示編號(hào)為i 的選手的初始分?jǐn)?shù)。第三行是 2*N 個(gè)正整數(shù)w1, w2, , w2N，每兩個(gè)數(shù)之間用一個(gè)空格隔開，其中wi 表示編號(hào)為i 的選手的實(shí)力值。【輸出】輸出文件名為 swiss.out。輸出只有一行，包含一個(gè)整數(shù)，即 R 輪比賽結(jié)束后，排名第Q 的選手的編號(hào)?！据斎胼敵鰳永縮wiss.inswiss.out2 4 27 6 6 710 5 20 151【輸入輸出樣例說明】本輪對(duì)陣本輪結(jié)束后的得分選手編號(hào)/初始/7667第1輪 767

12、8第2輪 7689第3 輪 8699第4 輪 96109【數(shù)據(jù)范圍】 對(duì)于 30%的數(shù)據(jù)，1N100；對(duì)于 50%的數(shù)據(jù)，1N10,000；對(duì)于 100%的數(shù)據(jù)，1N100,000，1R50，1Q2N，0s1, s2, , s2N ，1w1,w2, , w2N ?！窘忸}】題目雖然長，但理解題意后就發(fā)現(xiàn)解題的瓶頸在于排序。如果每一輪比賽的結(jié)果都進(jìn)行快速排序，時(shí)間復(fù)雜度為O（Rlongn），但事實(shí)證明這樣只能拿60分。如何AC，這需要一個(gè)巧算法：分析得知，快速排序?qū)嶋H上進(jìn)行了許多無用的工作：如果兩個(gè)人在第i輪都贏了，那么第i輪后的先后關(guān)系與第i-1輪是一樣的；反之，如果兩人都輸了，他們的先后關(guān)系也

13、不會(huì)變。所以，我們有一個(gè)新算法：一開始做一趟快速排序，然后對(duì)于每一輪，將此輪的n個(gè)贏者（他們的先后關(guān)系和上一輪不變）和n個(gè)輸者（他們的先后關(guān)系和上一輪也不變分開，然后就是歸并，于是時(shí)間復(fù)雜度O（Rn）（實(shí)踐證明，如果單純的排序r次，必然結(jié)果是超時(shí)。事實(shí)上只需一次真正意義上的排序以后，在以后的比賽中，按原順序分成兩組，獲勝組和失敗組，這兩組依然是有序的，再把這兩組歸并成一組，就可以了?？倳r(shí)間復(fù)雜度O(N*R) ）program swiss;var a,b,v:array1.200000of longint; c,d:array1.100000,1.2of longint; n,r,q,i,j:l

14、ongint;procedure qsort(l,r:longint);var i,j,mid1,mid2,t:longint;begin i:=l;j:=r; mid1:=a(l+r)div 2; mid2:=v(l+r)div 2; repeat /按分?jǐn)?shù)從高到低排序，分?jǐn)?shù)相同的，編號(hào)較小的選手排名靠前 while (aimid1) or (ai=mid1) and (vimid2) do inc(i); while (ajmid2) do dec(j); if ij; if ir then qsort(i,r); if ldl2,1)or (cl1,1=dl2,1)and(cl1,2n)

15、or(l2n); while l1=n do begin i:=i+1; ai:=cl1,1; vi:=cl1,2; l1:=l1+1; end; while l2bv2*j then begin inc(a2*j-1); cj,1:=a2*j-1; /數(shù)組cj,1保存嬴方的總分；數(shù)組cj,2保存嬴方的號(hào)碼； cj,2:=v2*j-1; dj,1:=a2*j; /數(shù)組dj,1保存輸方的總分；數(shù)組dj,2保存輸方的號(hào)碼； dj,2:=v2*j; end else begin inc(a2*j); cj,1:=a2*j; cj,2:=v2*j; dj,1:=a2*j-1; dj,2:=v2*j-1

16、; end; mergesort; end; writeln(vq); close(input);close(output);end.4. 表達(dá)式的值(exp.cpp/c/pas)【問題描述】對(duì)于 1 位二進(jìn)制變量定義兩種運(yùn)算：運(yùn)算符運(yùn)算規(guī)則00=001=110=111=10 0=00 1=01 0=01 1=1運(yùn)算的優(yōu)先級(jí)是：1. 先計(jì)算括號(hào)內(nèi)的，再計(jì)算括號(hào)外的。2. “”運(yùn)算優(yōu)先于“”運(yùn)算，即計(jì)算表達(dá)式時(shí)，先計(jì)算運(yùn)算，再計(jì)算運(yùn)算。例如：計(jì)算表達(dá)式AB C 時(shí)，先計(jì)算B C，其結(jié)果再與A 做運(yùn)算。現(xiàn)給定一個(gè)未完成的表達(dá)式，例如_+(_*_)，請(qǐng)你在橫線處填入數(shù)字0 或者1，請(qǐng)問有多少種填法可

17、以使得表達(dá)式的值為0?！据斎搿枯斎胛募麨?exp.in，共2 行。第 1 行為一個(gè)整數(shù)L，表示給定的表達(dá)式中除去橫線外的運(yùn)算符和括號(hào)的個(gè)數(shù)。第 2 行為一個(gè)字符串包含L 個(gè)字符，其中只包含（、）、+、*這4 種字符，其中（、）是左右括號(hào)，+、*分別表示前面定義的運(yùn)算符“”和“”。這行字符按順序給出了給定表達(dá)式中除去變量外的運(yùn)算符和括號(hào)?！据敵觥枯敵鑫募?exp.out 共1 行。包含一個(gè)整數(shù)，即所有的方案數(shù)。注意：這個(gè)數(shù)可能會(huì)很大，請(qǐng)輸出方案數(shù)對(duì)10007 取模后的結(jié)果?！据斎胼敵鰳永?】exp.inexp.out4+(*)3【輸入輸出樣例說明】 給定的表達(dá)式包括橫線字符之后為：_+(_*_

18、)在橫線位置填入(0、0、0)、(0、1、0)、(0、0、1)時(shí)，表達(dá)式的值均為0，所以共有3種填法?！緮?shù)據(jù)范圍】 對(duì)于 20%的數(shù)據(jù)有0L10。對(duì)于 50%的數(shù)據(jù)有0L1,000。對(duì)于 70%的數(shù)據(jù)有0L10,000。對(duì)于 100%的數(shù)據(jù)有0L100,000。對(duì)于 50%的數(shù)據(jù)輸入表達(dá)式中不含括號(hào)?！窘忸}】算法類似于表達(dá)式計(jì)算，一個(gè)符號(hào)棧，兩個(gè)數(shù)據(jù)棧。記f(s,0)表示表達(dá)式s為0的方案數(shù)，f(s,1)表示表達(dá)式s為1的方案數(shù)。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)*f(b,0) f(a*b

19、,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 = ( ( (,=), + (,), * (,), ) (,) ); /符號(hào)優(yōu)先級(jí)表var stack_op:array1.maxn of char; stack_data0, stack_data1:array1.maxn of longint; n,top_op,

20、top_data, i, len:longint; a0, a1, b0, b1, t0, t1:longint; s:ansistring;ch,now:char;procedure push_op(ch:char); /運(yùn)算符壓棧 begin inc(top_op); stack_optop_op:=ch; end;function pop_op:char; /運(yùn)算符出棧 begin pop_op:= stack_optop_op; dec(top_op); end;function gettop:char; /取棧頂符號(hào) begin gettop:=stack_optop_op; end

21、;procedure push_data(a0,a1:longint); /數(shù)據(jù)壓棧 begin inc(top_data); stack_data0top_data:=a0; stack_data1top_data:=a1; end;procedure pop_data(var a0,a1:longint); /數(shù)據(jù)出棧 begin a0:=stack_data0top_data; a1:=stack_data1top_data; dec(top_data); end;function find(ch:char):integer; /讀入符號(hào)var i:longint;begin for i:= 1 to 4 do if opi=ch then exit(i); end;begin assign(input,exp.in); reset(input); assign(output,exp.out); rewrite(output); top_op:=0; top_d