1、NOIP普及組歷屆試題分析,安徽省六安第一中學(xué) 江家和,引言,noip復(fù)賽的知識面很廣泛，對選手的綜合素質(zhì)考核要求更為嚴格，難度和分數(shù)的階梯層次更趨科學(xué)合理，對信息學(xué)活動的推動力和社會公信力更為增強。,NOIP普及組題型分布,NOIP普及組題型分布,一、枚舉類試題,枚舉法的基本思想是根據(jù)提出的問題枚舉所有可能的解，并用問題給定的條件檢驗?zāi)男┙馐切枰?，哪些解是不需要的。能使條件成立，即為其解。 枚舉法其實是最簡單的搜索算法。,珠心算測驗 (noip2014普及組第一題),珠心算是一種通過在腦中模擬算盤變化來完成快速運算的一種計算技術(shù)。珠心算訓(xùn)練，既能夠開發(fā)智力，又能夠為日常生活帶來很多便利，因

2、而在很多學(xué)校得到普及。 某學(xué)校的珠心算老師采用一種快速考察珠心算加法能力的測驗方法。他隨機生成一個正整數(shù)集合，集合中的數(shù)各不相同，然后要求學(xué)生回答：其中有多少個數(shù)，恰好等于集合中另外兩個（不同的）數(shù)之和？ 最近老師出了一些測驗題，請你幫忙求出答案。,珠心算測驗 (noip2014普及組第一題),【輸入】 輸入共兩行，第一行包含一個整數(shù)n，表示測試題中給出的正整數(shù)個數(shù)。 第二行有n個正整數(shù)，每兩個正整數(shù)之間用一個空格隔開，表示測試題中給出的正整數(shù)。 【輸出】 輸出共一行，包含一個整數(shù)，表示測驗題答案。 【樣例輸入】【樣例輸出】 4 2 1 2 3 4,對于100%的數(shù)據(jù)，3n100 測驗題給出的

3、正整數(shù)大小不超過10,000。,試題分析,題意大意：給你n個數(shù)，在這n個數(shù)中，找到滿足A+B=C的C的個數(shù)，注意不是這個等式的個數(shù)。,樣例中，1,2,3,4有1+2=3，1+3=4兩個。,由于本題數(shù)據(jù)規(guī)模n=100，我們可以直接枚舉C, A, B，三層循環(huán)解決問題。,方法1：三層循環(huán),考試中，有許多選手的程序是這樣的，錯在哪里？,ans:=0; for c:=1 to n do for a:=1 to n do for b:=1 to n do if (fc=fa+fb)and(ca)and(ab)and(cb) then inc(ans); writeln(ans);,樣例中，上述錯誤答案是

4、4：3=1+2, 3=2+1, 4=1+3, 4=3+1,方法1：參考程序,var i,n,a,b,c,t,ans:longint; f:array0.105of longint; begin readln(n); for i:=1 to n do read(fi); ans:=0; for c:=1 to n do begin t:=0; for a:=1 to n do for b:=1 to n do if (fc=fa+fb)and(t=0)and(ca)and(ab)and(cb) then begin inc(ans); t:=1; end; end; writeln(ans);

5、end.,方法2：兩層循環(huán),我們能不能使用兩層循環(huán)呢？,由于本題測驗題給出的正整數(shù)大小不超過10,000，我們可以直接枚舉A,B，判斷A+B在不在給定的數(shù)中即可。,定義一個數(shù)組vis，初始值為0； 讀入數(shù)ai時，visai標(biāo)記為1。 for i=1 to n do read(fi); visfi=1; ,方法2：兩層循環(huán),兩層循環(huán)枚舉a,b的值，判斷a+b是否存在： for a=1 to n do for b=1 to n do if (visfa+fb=1) and (ab) then begin inc(ans); visfa+fb=2; /避免出現(xiàn)重復(fù)的等式 end;,方法2：參考代碼,

6、var i, n, a, b, ans:longint; vis:array0.20005of 0.2; f:array0.105of longint; begin readln(n); fillchar(vis,sizeof(vis),0); for i:=1 to n do begin read(fi); visfi:=1; end; ans:=0; for a:=1 to n do for b:=1 to n do if (visfa+fb=1)and(ab) then begin inc(ans); visfa+fb:=2; end; writeln(ans); end.,數(shù)字統(tǒng)計 (

7、noip2010普及組第一題),請統(tǒng)計某個給定范圍L, R的所有整數(shù)中，數(shù)字2出現(xiàn)的次數(shù)。 比如在給定范圍2, 22，數(shù)字2在數(shù)2中出現(xiàn)了1次，在數(shù)12中出現(xiàn)了1次，在數(shù)20中出現(xiàn)了1次，在數(shù)21中出現(xiàn)了1次，在數(shù)22中出現(xiàn)了2次，所以數(shù)字2在該范圍內(nèi)一共出現(xiàn)了6次。 輸入格式 輸入共一行，為兩個正整數(shù)L和R，之間用一個空格隔開。 輸出格式 輸出共1行，表示數(shù)字2出現(xiàn)的次數(shù)。 樣例輸入：2 22 樣例輸出：6,試題分析,題目大意是給定a,b，統(tǒng)計a,b之間數(shù)字2出現(xiàn)的次數(shù)。 從a到b直接枚舉每一個數(shù)，判斷這個數(shù)中含有幾個2。,for i=a to b do 求i中含2的個數(shù)t; ans=ans

8、+t; 輸出t;,參考程序：,var i,a,b,ans:longint; begin readln(a,b); ans:=0; for i:=a to b do begin if i mod 10=2 then inc(ans); if i div 10 mod 10=2 then inc(ans); if i div 10 div 10 mod 10=2 then inc(ans); if i div 10 div 10 div 10 mod 10=2 then inc(ans); end; writeln(ans); end.,掃雷游戲 (noip2015普及組第二題),掃雷游戲是一款十

9、分經(jīng)典的單機小游戲。 在 n 行 m 列的雷區(qū)中有一些格子含有地雷（稱之為地雷格） ，其他格子不含地雷（稱之為非地雷格） 。玩家翻開一個非地雷格時，該格將會出現(xiàn)一個數(shù)字提示周圍格子中有多少個是地雷格。 游戲的目標(biāo)是在不翻出任何地雷格的條件下，找出所有的非地雷格。 現(xiàn)在給出n行m列的雷區(qū)中的地雷分布， 要求計算出每個非地雷格周圍的地雷格數(shù)。注：一個格子的周圍格子包括其上、下、左、右、左上、右上、左下、右下八個方向上與之直接相鄰的格子。,掃雷游戲 (noip2015普及組第二題),輸入樣例133*?*? 輸入樣例223?*?*?,輸出樣例1mine.out*102211*1 輸出樣例2mine.o

10、ut2*1*21,對于100%的數(shù)據(jù)，1n100，1m100,問題分析：,本題也是簡單的枚舉類試題。 我們從雷區(qū)的第一行第一列(1,1)開始，判斷它周圍有多少個地雷。 由于本題讀入的是字符，讀入時需要注意： readln(n,m); for i=1 to n do begin for j=1 to m do read(aij); readln; end;,問題分析：,一個格子的周圍格子包括其上、下、左、右、左上、右上、左下、右下八個方向上與之直接相鄰的格子。判斷如下： if aij-1=* then inc(s); if aij+1=* then inc(s); if ai+1j-1=* th

11、en inc(s); if ai+1j+1=* then inc(s); if ai+1j=* then inc(s); if ai-1j-1=* then inc(s); if ai-1j+1=* then inc(s); if ai-1j=* then inc(s);,參考程序：,var i,j,n,m,s:longint; a:array0.105,0.105of char; begin readln(n,m); for i:=1 to n do begin for j:=1 to m do read(aij); readln; end; for i:=1 to n do begin f

12、or j:=1 to m do begin s:=0; if ai,j=* then write(ai,j),else begin if aij-1=* then inc(s); if aij+1=* then inc(s); if ai+1j-1=* then inc(s); if ai+1j+1=* then inc(s); if ai+1j=* then inc(s); if ai-1j-1=* then inc(s); if ai-1j+1=* then inc(s); if ai-1j=* then inc(s); write(s); end; end; writeln; end;

13、end.,比例簡化 (noip2014普及組第二題),在社交媒體上，經(jīng)常會看到針對某一個觀點同意與否的民意調(diào)查以及結(jié)果。例如，對某 一觀點表示支持的有 1498 人，反對的有 902 人，那么贊同與反對的比例可以簡單的記為1498:902。 不過，如果把調(diào)查結(jié)果就以這種方式呈現(xiàn)出來，大多數(shù)人肯定不會滿意。因為這個比例的數(shù)值太大，難以一眼看出它們的關(guān)系。對于上面這個例子，如果把比例記為 5:3，雖然與 真實結(jié)果有一定的誤差，但依然能夠較為準確地反映調(diào)查結(jié)果，同時也顯得比較直觀。 現(xiàn)給出支持人數(shù) A，反對人數(shù) B，以及一個上限 L，請你將 A 比 B 化簡為 A比 B，要求在 A和 B均不大于 L

14、 且 A和 B互質(zhì)（兩個整數(shù)的最大公約數(shù)是 1）的前提下，A/B A/B 且 A/B - A/B 的值盡可能小。,比例簡化 (noip2014普及組第二題),輸入格式 輸入共一行，包含三個整數(shù) A，B，L，每兩個整數(shù)之間用一個空格隔開，分別表示支持人數(shù)、反對人數(shù)以及上限。 輸出格式 輸出共一行，包含兩個整數(shù) A，B，中間用一個空格隔開，表示化簡后的比例。 樣例輸入 1498 902 10 樣例輸出 5 3,比例簡化試題分析,讀入a,b,L后，從1到L分別枚舉a和b。判斷a和b是否合法，合法的話就記錄下來。,輸入a,b,L; for i=1 to L do for j=1 to L do if

15、i,j合法 then ansx=i; ansy=j; 輸出ansx, ansy;,比例簡化試題分析,程序的關(guān)鍵在于如何判斷i,j合法。,if (gcd(i,j)=1)and(i/j=a/b) then if i/j-a/bminn then begin minn:=i/j-a/b; ansx:=i; ansy:=j; end;,條件1：i和j互質(zhì)；,條件2：i/j的值大于等于A/B的值 ；,條件3：i/jA/B的值盡可能小 ；,比例簡化參考程序：,var a,b,L,i,j,ansx,ansy:longint; minn:real; function gcd(x,y:longint):long

16、int; begin if y=0 then exit(x); gcd:=gcd(y,x mod y); end; begin readln(a,b,L); minn:=99999999; for i:=1 to L do for j:=1 to L do if (gcd(i,j)=1)and(i/j=a/b) then if i/j-a/bminn then begin minn:=i/j-a/b; ansx:=i; ansy:=j; end; writeln(ansx, ,ansy); end.,二、模擬類試題,有些問題，我們很難建立數(shù)學(xué)模型，或者很難用計算機建立遞推、遞歸、枚舉、回溯法等

17、算法。在這種情況下，一般采用模擬策略。 所謂模擬策略就是模擬某個過程，通過改變數(shù)學(xué)模型的各種參數(shù)，進而觀察變更這些參數(shù)所引起過程狀態(tài)的變化，由此展開算法設(shè)計。,金幣 (noip2015普及組第一題),國王將金幣作為工資，發(fā)放給忠誠的騎士。第一天，騎士收到一枚金幣；之后兩天（第二天和第三天），每天收到兩枚金幣；之后三天（第四、五、六天），每天收到三枚金幣；之后四天（第七、八、九、十天），每天收到四枚金幣；這種工資發(fā)放模式會一直這樣延續(xù)下去：當(dāng)連續(xù)N天每天收到N枚金幣后，騎士會在之后的連續(xù)N+1天里，每天收到N+1枚金幣。請計算在前K天里，騎士一共獲得了多少金幣。 輸入格式：輸入文件只有1行，包含

18、一個正整數(shù)K，表示發(fā)放金幣的天數(shù)。 輸出格式：輸出文件只有1行，包含一個正整數(shù)，即騎士收到的金幣數(shù)。 輸入輸出樣例 輸入樣例： 1000 輸出樣例： 29820,試題分析,本題直接模擬即可。定義變量時注意不要混淆了： i代表枚舉的天數(shù)，t代表連續(xù)的天數(shù)，也是每天收到的金幣數(shù)，s收到的金幣總數(shù)。,讀入天數(shù)k; i=1; t=1; s=0; while ik then break; t=t+1; 輸出s;,參考程序：,var i, j, k, s, t:longint; begin readln(k); i:=1; t:=1; s:=0; while ik then break; end; inc

19、(t); end; writeln(s); end.,螺旋方陣 (noip2014普及組第三題),一個n行n列的螺旋矩陣可由如下方法生成： 從矩陣的左上角(第1行第1列)出發(fā)，初始時向右移動；如果前方是未曾經(jīng)過的格子，則繼續(xù)前進，否則右轉(zhuǎn)；重復(fù)上述操作直至經(jīng)過矩陣中所有格子。根據(jù)經(jīng)過順序，在格子中依次填入1,2,3,.，便構(gòu)成了一個螺旋矩陣。 現(xiàn)給出矩陣大小n以及i和j，請你求出該矩陣中第i行第j列的數(shù)是多少。 下圖是一個n=4時的螺旋矩陣。,螺旋方陣 (noip2014普及組第三題),輸入格式 輸入共一行，包含三個整數(shù) n，i，j，每兩個整數(shù)之間用一個空格隔開，分別表示矩陣大小、待求的數(shù)所在

20、的行號和列號。 輸出格式 輸出共一行，包含一個整數(shù)，表示相應(yīng)矩陣中第 i 行第 j 列的數(shù)。 樣例輸入：4 2 3 樣例輸出：14 對于 50%的數(shù)據(jù)，1 n 100;對于 100%的數(shù)據(jù)，1 n 30,000，1 i n，1 j n。,螺旋方陣試題分析,本題首先讓我們想到傳統(tǒng)的模擬，從1,1開始往數(shù)組中填充數(shù)字，但對于30000,30000的數(shù)組，直接爆零。,對于讀入的n, x, y，先判斷(x,y)在第幾圈，再模擬圈內(nèi)的數(shù)字。,螺旋方陣試題分析,如：n=4, (2,2)在第2圈，(3,1)在第1圈。 n=6，(4,5)在第2圈,圈數(shù)q=min(x, y, n-x+1, n-y+1 ),即目

21、標(biāo)位置到四個邊界距離的最小值,螺旋方陣試題分析,圈數(shù)q求出后，前q圈的數(shù)字總和很容易求出來。,對于任何一個方陣： 第1圈有4n-4個數(shù); 第2圈有4(n-2)-4個數(shù)； 第3圈有4(n-4)-4個數(shù)； 第q圈有4(n-q(n-1)-4個數(shù),螺旋方陣試題分析,前1圈有4n-4個數(shù); 前2圈有4n-4 + 4(n-2)-4 = 2(4n-2*4)個數(shù)； 前3圈有4(n-4)-4 + 2(4n-8) = 3(4n-3*4)個數(shù)； 前q圈有q(4n-4q)個數(shù)；,螺旋方陣試題分析,目標(biāo)位置(i,j)到底在當(dāng)前這一圈的第幾個位置？ 如目標(biāo)數(shù)26所在的位置(4,5)，在第2圈的什么位置？ 分兩種情況： 1

22、）目標(biāo)數(shù)(i,j)在上行或右行； i+j-2q+1 2）目標(biāo)數(shù)(i,j)在下行或左行； 距離第一個數(shù)的距離 i+j-2q+1,螺旋方陣參考程序：,var n,i,j,q,ans:longint; function min(a,b:longint):longint; begin if ab then exit(a) else exit(b); end; begin readln(n,i,j); q:=min(i,min(j,min(n-i+1,n-j+1); if i=j then ans:=q*(4*(n-1)-4*q)+10*q-4*n-3+i+j else ans:=q*(4*n-4*q)

23、+2*q+1-i-j; writeln(ans); end.,計數(shù)問題 (noip2013普及組第一題),試計算在區(qū)間1到n的所有整數(shù)中，數(shù)字x（0 x9）共出現(xiàn)了多少次？例如，在1到11中，即在1、2、3、4、5、6、7、8、9、10、11中，數(shù)字1出現(xiàn)了4次。 輸入： 輸入共1行，包含2個整數(shù)n、x，之間用一個空格隔開。輸出： 輸出共1行，包含一個整數(shù)，表示x出現(xiàn)的次數(shù)。 輸入示例： 111 輸出示例： 4 其他說明： 對于100%的數(shù)據(jù)，1n1,000,000，0 x9。,計數(shù)問題 試題分析,這道題入門難度，直接模擬。 循環(huán)1到n之間的所有數(shù)，對每個數(shù)的每位判斷即可。,讀入n,x; fo

24、r i=1 to n do k=i; while k的每一位j do if j=x then inc(ans); 輸出ans;,計數(shù)問題 參考程序,這道題入門難度，直接模擬。 循環(huán)1到n之間的所有數(shù)，對每個數(shù)的每位判斷即可。,var i,n,x,k,ans:longint; begin readln(n,x); ans:=0; for i:=1 to n do begin k:=i; while k0 do begin if k mod 10=x then inc(ans); k:=k div 10; end; end; writeln(ans); end.,尋寶 (noip2012普及組第二

25、題),傳說很遙遠的藏寶樓頂層藏著誘人的寶藏。小明歷盡千辛萬苦終于找到傳說中的這個藏寶樓，藏寶樓的門口豎著一個木板，上面寫有幾個大字：尋寶說明書。說明書的內(nèi)容如下： 藏寶樓共有 N+1 層，最上面一層是頂層，頂層有一個房間里面藏著寶藏。除了頂層外，藏寶樓另有 N 層，每層 M 個房間，這 M 個房間圍成一圈并按逆時針方向依次編號為 0，M-1。其中一些房間有通往上一層的樓梯，每層樓的樓梯設(shè)計可能不同。每個房間里有一個指示牌，指示牌上有一個數(shù)字 x，表示從這個房間開始按逆時針方向選擇第 x 個有樓梯的房間（假定該房間的編號為 k），從該房間上樓，上樓后到達上一層的 k 號房間。比如當(dāng)前房間的指示牌

26、上寫著 2，則按逆時針方向開始嘗試，找到第 2 個有樓梯的房間，從該房間上樓。如果當(dāng)前房間本身就有樓梯通向上層，該房間作為第一個有樓梯的房間。,尋寶 (noip2012普及組第二題),尋寶說明書的最后用紅色大號字體寫著：“尋寶須知：幫助你找到每層上樓房間的指示牌上的數(shù)字（即每層第一個進入的房間內(nèi)指示牌上的數(shù)字）總和為打開寶箱的密鑰”。 請幫助小明算出這個打開寶箱的密鑰。 【輸入】 第一行 2 個整數(shù) N 和 M，之間用一個空格隔開。N 表示除了頂層外藏寶樓共 N 層樓，M 表示除頂層外每層樓有 M 個房間。 接下來 N*M 行，每行兩個整數(shù)，之間用一個空格隔開，每行描述一個房間內(nèi)的情況，其中第

27、(i-1)*M+j 行表示第 i 層 j-1 號房間的情況（i=1, 2, , N；j=1, 2, ,M）。第一個整數(shù)表示該房間是否有樓梯通往上一層（0 表示沒有，1 表示有），第二個整數(shù)表示指示牌上的數(shù)字。注意，從 j 號房間的樓梯爬到上一層到達的房間一定也是 j 號房間。 最后一行，一個整數(shù)，表示小明從藏寶樓底層的幾號房間進入開始尋寶（注：房間編號從 0 開始）。,尋寶 (noip2012普及組第二題),【輸出】 輸出只有一行，一個整數(shù)，表示打開寶箱的密鑰，這個數(shù)可能會很大，請輸出對 20123取模的結(jié)果即可。 【輸入輸出樣例】 treasure.in treasure.out 2 3 5

28、 1 2 0 3 1 4 0 1 1 5 1 2 1,尋寶 (noip2012普及組第二題),【輸入輸出樣例說明】 第一層： 0 號房間，有樓梯通往上層，指示牌上的數(shù)字是 2； 1 號房間，無樓梯通往上層，指示牌上的數(shù)字是 3； 2 號房間，有樓梯通往上層，指示牌上的數(shù)字是 4； 第二層： 0 號房間，無樓梯通往上層，指示牌上的數(shù)字是 1； 1 號房間，有樓梯通往上層，指示牌上的數(shù)字是 5； 2 號房間，有樓梯通往上層，指示牌上的數(shù)字是 2； 小明首先進入第一層（底層）的 1 號房間，記下指示牌上的數(shù)字為 3，然后從這個房間開始，沿逆時針方向選擇第 3 個有樓梯的房間 2 號房間進入，上樓后到

29、達第二層的 2 號房間，記下指示牌上的數(shù)字為 2，由于當(dāng)前房間本身有樓梯通向上層，該房間作為第一個有樓梯的房間。因此，此時沿逆時針方向選擇第 2 個有樓梯的房間即為 1 號房間，進入后上樓梯到達頂層。這時把上述記下的指示牌上的數(shù)字加起來，即 3+2=5，所以打開寶箱的密鑰就是 5。,尋寶 試題分析,題目大意：n層樓，每層m個房間。每個房間有一個號碼，樓梯。從底樓出發(fā)，如果該房間有樓梯，直接上樓，否則走到該層下個指定的房間。 將每一層第一個到達的房間號加起來就是答案。,尋寶 試題分析,我們把每一層樓看成一個圈，完全模擬一下小明的行走路線即可。注意細節(jié)： 1.房間號從0開始，所以讀入時要注意；,r

30、eadln(n,m); for i=1 to n do for j=0 to m-1 do 讀入樓梯和號碼；,尋寶 試題分析,我們把每一層樓看成一個圈，完全模擬一下小明的行走路線即可。注意細節(jié)： 1.房間號從0開始，所以讀入時要注意； 2.讀入時統(tǒng)計每一層有多少個帶樓梯的房間；,readln(n,m); for i=1 to n do for j=0 to m-1 do begin readln(stairi,j, numi,j); if stairi,j=1 then inc(sumi); end;,尋寶 試題分析,我們把每一層樓看成一個圈，完全模擬一下小明的行走路線即可。注意細節(jié)： 1.房

31、間號從0開始，所以讀入時要注意； 2.讀入時統(tǒng)計每一層有多少個帶樓梯的房間； 3.理解“從這個房間開始按逆時針方向選擇第 x 個有樓梯的房間”。假如當(dāng)前房間沒有樓梯，指示牌上的號為j：,while j0 do begin if stairi,k=1 then dec(j); if j0 then k:=(k+1) mod m; end;,尋寶 參考程序,var i,j,n,m,k,ans:longint; num:array0.10001,0.101 of longint; sum:array0.10001of longint; stair:array0.10001,0.101 of 0.1;

32、 begin readln(n,m); fillchar(sum,sizeof(sum),0); for i:=1 to n do for j:=0 to m-1 do begin readln(stairi,j,numi,j); if stairi,j=1 then inc(sumi); end; readln(k); ans:=0; for i:=1 to n do begin ans:=(ans+numi,k) mod 20123; numi,k:=numi,k mod sumi; if numi,k=0 then numi,k:=sumi;,j:=numi,k; while j0 do

33、 begin if stairi,k=1 then dec(j); if j0 then k:=(k+1) mod m; end; end; writeln(ans); end.,接水問題 (noip2010普及組第二題),學(xué)校里有一個水房，水房里一共裝有m 個龍頭可供同學(xué)們打開水，每個龍頭每秒鐘的供水量相等，均為1。 現(xiàn)在有n名同學(xué)準備接水，他們的初始接水順序已經(jīng)確定。將這些同學(xué)按接水順序從1到n 編號，i 號同學(xué)的接水量為wi。接水開始時，1 到m 號同學(xué)各占一個水龍頭，并同時打開水龍頭接水。當(dāng)其中某名同學(xué)j 完成其接水量要求wj后，下一名排隊等候接水的同學(xué)k馬上接替j 同學(xué)的位置開始接水

34、。這個換人的過程是瞬間完成的，且沒有任何水的浪費。即j同學(xué)第x 秒結(jié)束時完成接水，則k 同學(xué)第x+1 秒立刻開始接水。若當(dāng)前接水人數(shù)n不足m，則只有n個龍頭供水，其它mn個龍頭關(guān)閉。 現(xiàn)在給出n 名同學(xué)的接水量，按照上述接水規(guī)則，問所有同學(xué)都接完水需要多少秒。,接水問題 (noip2010普及組第二題),輸入 第1 行2 個整數(shù)n 和m，用一個空格隔開，分別表示接水人數(shù)和龍頭個數(shù)。 第2 行n 個整數(shù)w1、w2、wn，每兩個整數(shù)之間用一個空格隔開，wi表示i 號同學(xué)的接水量。 輸出 輸出只有一行，1 個整數(shù)，表示接水所需的總時間。 樣例輸入： 5 3 4 4 1 2 1 樣例輸出： 4,接水問

35、題 試題分析,題目大意：n個人排隊順序接水，共m個水龍頭。求接完水需要最少的秒數(shù)。 本題直接模擬即可。有的選手在考試中使用秒去枚舉，結(jié)果嚴重超時。 對于每一個人， 選擇這m個水龍頭中接水量最小的去接。 最后輸出這m個水龍頭中接水量最大的。,接水問題 參考程序,var a:array0.10001of longint; s:array0.101of longint; n,m,i,j,k,ans,minn:longint; begin readln(n,m); for i:=1 to n do read(ai); fillchar(s,sizeof(s),0); for i:=1 to n do

36、begin minn:=9999999; for j:=1 to m do if sjans then ans:=si; writeln(ans); end.,三、字符串類試題,對于字符串、表達式的求解、 大整數(shù)的處理等等，我們經(jīng)常采用字符串來處理。 字符串處理常見函數(shù)和過程： length()、delete() pos()、val()、str(),數(shù)字反轉(zhuǎn) (noip2011普及組第一題),給定一個整數(shù)，請將該數(shù)各個位上數(shù)字反轉(zhuǎn)得到一個新數(shù)。新數(shù)也應(yīng)滿足整數(shù)的常見形式，即除非給定的原數(shù)為零，否則反轉(zhuǎn)后得到的新數(shù)的最高位數(shù)字不應(yīng)為零（如：輸入-380，輸出-83）。 輸入 輸入共1行，一個整數(shù)

37、N。 輸出 輸出共1行，一個整數(shù)，表示反轉(zhuǎn)后的新數(shù)。 樣例輸入 123 樣例輸出 321,數(shù)字反轉(zhuǎn) 試題分析,方法1：直接降位取個位 降位：n div 10 取個位：n mod 10 注意刪去末尾的0！ 缺點：數(shù)不能太大，容易溢出！,數(shù)字反轉(zhuǎn) 試題分析,var n:longint; begin readln(n); if n0 do begin write(n mod 10); n:=n div 10; end; end; end.,數(shù)字反轉(zhuǎn) 試題分析,方法2：字符串 注意1：負數(shù)的處理,if s1=- then begin write(-); delete(s,1,1); end;,數(shù)字反轉(zhuǎn)

38、 試題分析,方法2：字符串 注意1：負數(shù)的處理 注意2：末尾0的處理：,len=length(s); while (slen=0) do dec(len); for i= len downto 1 do write(si);,數(shù)字反轉(zhuǎn) 參考程序,var s:ansistring; i,len:longint; begin readln(s); if s1=- then begin write(-); delete(s,1,1); end; len:=length(s); while (slen=0)do dec(len); for i:=len downto 1 do write(si); e

39、nd.,統(tǒng)計單詞個數(shù) (noip2011普及組第二題),一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有的還能統(tǒng)計出特定單詞在文章中出現(xiàn)的次數(shù)?，F(xiàn)在，請你編程實現(xiàn)這一功能，具體要求是：給定一個單詞，請你輸出它在給定的文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置。注意：匹配單詞時，不區(qū)分大小寫，但要求完全匹配，即給定單詞必須與文章中的某一獨立單詞在不區(qū)分大小寫的情況下完全相同（參見樣例1），如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見樣例2）。,統(tǒng)計單詞個數(shù) (noip2011普及組第二題),輸入格式 第1行為一個字符串，其中只含字母，表示給定單詞；第2行為一個字

40、符串，其中只可能包含字母和空格，表示給定的文章。 輸出格式 只有一行，如果在文章中找到給定單詞則輸出兩個整數(shù)，兩個整數(shù)之間用一個空格隔開，分別是單詞在文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置（即在文章中第一次出現(xiàn)時，單詞首字母在文章中的位置，位置從0開始）；如果單詞在文章中沒有出現(xiàn)，則直接輸出一個整數(shù)-1。,統(tǒng)計單詞個數(shù) (noip2011普及組第二題),樣例輸入1：Totobeornottobeisaquestion 樣例輸出1：20 樣例輸入2：toDidtheOttomanEmpireloseitspoweratthattime 樣例輸出2：-1【輸入輸出樣例2說明】表示給定的單詞to在文章中

41、沒有出現(xiàn)，輸出整數(shù)-1。 注釋說明 1單詞長度10。1文章長度1,000,000。,統(tǒng)計單詞個數(shù) 試題分析,本題是簡單的字符串處理。 讀入單詞和文章（字符串）后，可以把單詞和文章全部轉(zhuǎn)換成大寫（或小寫），然后循環(huán)在文章中對單詞進行查找，找到就存儲位置，并統(tǒng)計找到的次數(shù)。 轉(zhuǎn)換成大寫有兩種方法： 方法1：利用ord()和chr()函數(shù)逐個字符轉(zhuǎn)換： for i=1 to length(s) do if si=a then si:=chr(ord(si)-32); 方法2：利用upcase()函數(shù)直接轉(zhuǎn)換： s=upcase(s);,統(tǒng)計單詞個數(shù) 試題分析,本題還有一個問題需要處理： 查找的單詞s

42、1只是文章s中某個單詞的一部分，如： To DidtheOttomanEmpire 處理方法：讀入單詞s1后，在s1的兩端各添加一個空格。 s1= + s1 + ,統(tǒng)計單詞個數(shù) 參考程序,var s1,s:ansistring; i,p,len,ans:longint; begin readln(s1); /單詞 readln(s); /文章 s1:= +upcase(s1)+ ; s:= +upcase(s)+ ; p:=-1; ans:=0; len:=length(s1); for i:=1 to length(s)-len+1 do if copy(s,i,len)=s1 then b

43、egin if p=-1 then p:=i-1; inc(ans); end; if p=-1 then write(p) else write(ans, ,p); end.,四、貪心類試題,從問題的某一個初始解出發(fā)，向給定的目標(biāo)遞推。推進的每一步不是依據(jù)某一固定的遞推公式，而是做一個當(dāng)時看似最佳的貪心選擇，不斷地將問題歸納為更小的相似的子問題，最終產(chǎn)生出一個全局最優(yōu)解。,排座椅 (noip2008普及組第二題),上課的時候總有一些同學(xué)和前后左右的人交頭接耳，這是令小學(xué)班主任十分頭疼的一件事情。不過，班主任小雪發(fā)現(xiàn)了一些有趣的現(xiàn)象，當(dāng)同學(xué)們的座次確定下來之后，只有有限的D對同學(xué)上課時會交頭接

44、耳。同學(xué)們在教室中坐成了M行N列，坐在第i行第j列的同學(xué)的位置是（i，j），為了方便同學(xué)們進出，在教室中設(shè)置了K條橫向的通道，L條縱向的通道。于是，聰明的小雪想到了一個辦法，或許可以減少上課時學(xué)生交頭接耳的問題：她打算重新擺放桌椅，改變同學(xué)們桌椅間通道的位置，因為如果一條通道隔開了兩個會交頭接耳的同學(xué)，那么他們就不會交頭接耳了。 請你幫忙給小雪編寫一個程序，給出最好的通道劃分方案。在該方案下，上課時交頭接耳的學(xué)生對數(shù)最少。,排座椅 (noip2008普及組第二題),輸入 輸入的第一行，有5個用空格隔開的整數(shù)，分別是M，N，K，L，D（2=N，M=1000，0=KM，0=LN，D=2000）。接

45、下來D行，每行有4個用空格隔開的整數(shù)，第i行的4個整數(shù)Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)與(Pi,Qi)的兩個同學(xué)會交頭接耳（輸入保證他們前后相鄰或者左右相鄰）。輸入數(shù)據(jù)保證最優(yōu)方案的唯一性。 輸出 輸出共兩行。第一行包含K個整數(shù)，a1a2aK，表示第a1行和a1+1行之間、第a2行和第a2+1行之間、第aK行和第aK+1行之間要開辟通道，其中aiai+1，每兩個整數(shù)之間用空格隔開（行尾沒有空格）。第二行包含L個整數(shù)，b1b2bk，表示第b1列和b1+1列之間、第b2列和第b2+1列之間、第bL列和第bL+1列之間要開辟通道，其中bibi+1，每兩個整數(shù)之間用空格隔開（行尾沒有

46、空格）。,排座椅 (noip2008普及組第二題),輸入樣例 4 5 1 2 3 4 2 4 3 2 3 3 3 2 5 2 4 輸出樣例 2 2 4,排座椅 試題分析,貪心。 題意：教室有m行n列，現(xiàn)在要劃分k條橫向通道，L條縱向的通道。交頭接耳的學(xué)生位置xi,yi和pi,qi。怎么劃分通道，使得上課時交頭接耳的學(xué)生對數(shù)最少。 用rowi記錄第i行與第i+1行之間有多少對交頭接耳的； 用coli記錄第i列與第i+1列有多少對交頭接耳的。 將row從大到小排序，前k個即為要隔開的行；將col從大到小排序，前L個即為要隔開的列。,排座椅 試題分析,程序的框架： 讀入m,n,k,L,d; For

47、i=1 to d 讀入x,y,p,q; if x=p then inc(rowmin(x,p).value) else inc(colmin(y,q).value); 對數(shù)組row按row.value從大到小排序; 對于數(shù)組row1到rowk按row.no從小到大排序； 輸出row1rowk; 對數(shù)組col按col.value從大到小排序; 對于數(shù)組col1到colL按col.no從小到大排序； 輸出col1colL;,排座椅 參考程序,var m,n,t,k,L,d,i,j,x,y,p,q,maxx:longint; row,col,a:array0.1005 of longint; fun

48、ction min(x,y:longint):longint; begin if xy then exit(y) else exit(x); end; begin readln(m,n,k,L,d); fillchar(row,sizeof(row),0); fillchar(col,sizeof(col),0); for i:=1 to d do begin readln(x,y,p,q); if x=p then inc(colmin(y,q) else inc(rowmin(x,p); end; t:=0; while trowmaxx then maxx:=i; rowmaxx:=-1

49、; inc(t); end;,t:=0; while tcolmaxx then maxx:=i; colmaxx:=-1; inc(t); end; for i:=1 to m do if rowi=-1 then write(i, ); writeln; for i:=1 to n do if coli=-1 then write(i, ); writeln; end.,紀念品分組 (noip2007普及組第二題),元旦快到了，校學(xué)生會讓樂樂負責(zé)新年晚會的紀念品發(fā)放工作。為使得參加晚會的同學(xué)所獲得 的紀念品價值相對均衡，他要把購來的紀念品根據(jù)價格進行分組，但每組最多只能包括兩件紀念品， 并

50、且每組紀念品的價格之和不能超過一個給定的整數(shù)。為了保證在盡量短的時間內(nèi)發(fā)完所有紀念品，樂樂希望分組的數(shù)目最少。 你的任務(wù)是寫一個程序，找出所有分組方案中分組數(shù)最少的一種，輸出最少的分組數(shù)目。,紀念品分組 (noip2007普及組第二題),輸入 包含n+2行: 第1行包括一個整數(shù)w，為每組紀念品價格之和的上眼=第2行為一個整數(shù)n，表示購來的紀念品的總件數(shù)G 第3-n+2行每行包含一個正整數(shù)Pi (5 = Pi = w3)w表示所對應(yīng)紀念品的價格。 輸出 僅一行，包含一個整數(shù)，ep最少的分組數(shù)目合,紀念品分組 (noip2007普及組第二題),樣例輸入：樣例輸出： 1006 9 90 20 20

51、30 50 60 70 80 90 100%的數(shù)據(jù)滿足: 1 = n = 30000，80 = W = 200,紀念品分組 試題分析,算法：貪心 先按n件紀念品的價值進行排序，貪心策略是價值最小的與價值最大的為一組，這樣分組是最少的。,紀念品分組 試題分析,算法：貪心 先按n件紀念品的價值進行排序，貪心策略是價值最小的與價值最大的為一組，這樣分組是最少的。,紀念品分組 參考程序,var i,j,t,m,n,left,right,ans:longint; a:array0.30001of longint; begin readln(m,n); for i:=1 to n do readln(ai

52、); for i:=1 to n-1 do for j:=i+1 to n do if aiaj then begin t:=ai;ai:=aj;aj:=t;end; ans:=0; left:=1;right:=n; while left=right do begin if aleft+aright=m then begin inc(left);dec(right);end else dec(right); inc(ans); end; if left=right then inc(ans); writeln(ans); end.,六、簡單動態(tài)規(guī)劃類試題,動態(tài)規(guī)劃是解決多階段決策最優(yōu)化問題的

53、一種思想方法。一般我們從初始階段出發(fā)，枚舉每個階段的所有狀態(tài)，在狀態(tài)轉(zhuǎn)移的過程中，我們需要決策。根據(jù)每一步所選決策的不同，將隨即引起狀態(tài)的轉(zhuǎn)移，最終在變化的狀態(tài)中產(chǎn)生一個決策序列。動態(tài)規(guī)劃就是為了使產(chǎn)生的決策序列在符合某種條件下達到最優(yōu)。 普及組一般考查的動態(tài)規(guī)劃：01背包，最長上升子序列，一些簡單的線性動規(guī)。,守望者的逃離 (noip2007普及組第三題),惡魔獵手尤迫安野心勃勃.他背叛了暗夜精靈，率深藏在海底的那加企圖叛變：守望者在與尤迪安的交鋒中遭遇了圍殺.被困在一個荒蕪的大島上。為了殺死守望者，尤迪安開始對這個荒島施咒，這座島很快就會沉下去，到那時，島上的所有人都會遇難：守望者的跑步速

54、度，為17m/s， 以這樣的速度是無法逃離荒島的。慶幸的是守望者擁有閃爍法術(shù)，可在1s內(nèi)移動60m，不過每次使用閃爍法術(shù)都會消耗魔法值10點。守望者的魔法值恢復(fù)的速度為4點/s，只有處在原地休息狀態(tài)時才能恢復(fù)。 現(xiàn)在已知守望者的魔法初值M，他所在的初始位置與島的出口之間的距離S，島沉沒的時間T。你的任務(wù)是寫一個程序幫助守望者計算如何在最短的時間內(nèi)逃離荒島，若不能逃出，則輸出守望者在剩下的時間內(nèi)能走的最遠距離。注意:守望者跑步、閃爍或休息活動均以秒(s)為單位。且每次活動的持續(xù)時間為整數(shù)秒。距離的單位為米(m)。,守望者的逃離 (noip2007普及組第三題),輸入 輸入文件escape.in僅

55、一行，包括空格隔開的三個非負整數(shù)M，S，T。 輸出 輸出文件escape.out包含兩行: 第1行為字符串“Yes”或“No” (區(qū)分大小寫)，即守望者是否能逃離荒島。 第2行包含一個整數(shù)，第一行為“Yes” (區(qū)分大小寫）時表示守望著逃離荒島的最短時間 第一行為“No” (區(qū)分大小寫)時表示守望者能走的最遠距離。 樣例輸入 39 200 4 樣例輸出 No 197 提示 100%的數(shù)據(jù)滿足: 1 = T = 300000,0 = M=1000 1 =S = 108,守望者的逃離 試題分析,題目大意：一個人在t時間內(nèi)是否能夠行走的s米的距離，行走的方式有兩種： 1. 使用魔法（每秒60米），缺

56、點每秒耗費10點魔法值； 2. 跑步（每秒17米）。,守望者的逃離 試題分析,算法：貪心 + 背包型動態(tài)規(guī)劃,貪心的策略：有魔法的情況下，肯定先用魔法跑，這樣跑的快！ 如果魔法不夠，那么我們利用背包模型，只有在下列兩種選擇中選擇其中一種： 1、使用魔法 2、跑步,守望者的逃離 試題分析,令fi表示前i秒利用魔法行走的距離； dpi表示利用魔法或者跑步行走的最大距離。,很容易求出1到t的fi的值：,for i=1 to t do if magic=10 then magic=magic-10; fi=fi-1+60; else magic=magic+4; fi=fi-1; ,守望者的逃離 試題

57、分析,下面求dpi，01背包： dpi=max(dpi-1+17, fi);,守望者的逃離 參考程序,小朋友的數(shù)字 (noip2013普及組第三題),有 n 個小朋友排成一列。每個小朋友手上都有一個數(shù)字,這個數(shù)字可正可負。規(guī)定每個小朋友的特征值等于排在他前面(包括他本人)的小朋友中連續(xù)若干個(最少有一個)小朋友手上的數(shù)字之和的最大值。作為這些小朋友的老師,你需要給每個小朋友一個分數(shù),分數(shù)是這樣規(guī)定的:第一個小朋友的分數(shù)是他的特征值,其它小朋友的分數(shù)為排在他前面的所有小朋友中(不包括他本人),小朋友分數(shù)加上其特征值的最大值。請計算所有小朋友分數(shù)的最大值,輸出時保持最大值的符號,將其絕對值對 p

58、取模后輸出。,小朋友的數(shù)字 (noip2013普及組第三題),輸入格式 第一行包含兩個正整數(shù) n、p,之間用一個空格隔開。第二行包含 n 個數(shù),每兩個整數(shù)之間用一個空格隔開,表示每個小朋友手上的數(shù)字。 輸出格式 輸出只有一行,包含一個整數(shù),表示最大分數(shù)對 p 取模的結(jié)果。 樣例輸入1 5 997 1 2 3 4 5 樣例輸出1 21,小朋友的數(shù)字 試題分析,主要考查選手的語文理解能力，關(guān)鍵把題讀懂。 需要理解的兩個值： 特征值：前面連續(xù)若干個數(shù)字和的最大值； 分數(shù)：前面每個小朋友的分數(shù)+特征值的最大值,小朋友的數(shù)字 試題分析,算法：動態(tài)規(guī)劃 + 貪心,求小朋友的特征值需要求最大子段和。,for i=1 to n do dpi=max( dpi-1+ai, ai );,每個小朋友的特征值ti: for i=1 to n do dpi=max( dpi-1+ai, ai ); ti=max(ti-1, dpi); ,小朋友的數(shù)字 試題分析,算法：動態(tài)規(guī)劃 + 貪心,求小朋友的分數(shù)需要貪心：如果第一個小朋友的分數(shù)+特征值為負數(shù)，那么后面所有小朋友的分數(shù)=第一個小朋友的分數(shù)+特征值，否則=前一個小朋友的分數(shù)+特征值。,for i=