NOIP普與組歷屆試題分析

NOIP普與組歷屆試題分析第一頁(yè)，共105頁(yè)。引言

noip復(fù)賽的知識(shí)面很廣泛，對(duì)選手的綜合素質(zhì)考核要求更為嚴(yán)格，難度和分?jǐn)?shù)的階梯層次更趨科學(xué)合理，對(duì)信息學(xué)活動(dòng)的推動(dòng)力和社會(huì)公信力更為增強(qiáng)。第二頁(yè)，共105頁(yè)。NOIP普及組題型分布題型題目枚舉掃雷游戲(2015p2)、珠心算測(cè)驗(yàn)(2014p1)數(shù)字統(tǒng)計(jì)(2010p1)、比例簡(jiǎn)化(2014p2)模擬金幣(2015p1)、螺旋方陣(2014p3)、計(jì)數(shù)問(wèn)題(2013p1)、尋寶(2012p2)、接水問(wèn)題(2010p2)字符串?dāng)?shù)字反轉(zhuǎn)(2011p1)、統(tǒng)計(jì)單詞個(gè)數(shù)(2011p2)ISBN號(hào)碼(2008p1)、乒乓球(2003p1)貪心排座椅(2008p2)、紀(jì)念品分組(2007p2)第三頁(yè)，共105頁(yè)。NOIP普及組題型分布題型題目簡(jiǎn)單動(dòng)態(tài)規(guī)劃子矩陣(2014p4)、小朋友的數(shù)字(2013p3)擺花(2012p3)、導(dǎo)彈攔截(2010p3)道路游戲(2009p4)、傳球游戲(2008p3)守望者的逃離(2007p3)、開(kāi)心的金明(2006p2)采藥(2005p3)、數(shù)字游戲(2003p2)數(shù)學(xué)/數(shù)論質(zhì)因數(shù)分解(2012p1)、細(xì)胞分裂(2009p3)Hanoi雙塔問(wèn)題(2007p4)、數(shù)列(2006p4)循環(huán)(2005p4)、棧(2003p3卡特蘭數(shù))數(shù)據(jù)結(jié)構(gòu)表達(dá)式求值(2013p2)、表達(dá)式的值(2011p4)FBI樹(shù)(2004p1)、求先序排列(2001p2)圖論（提高組）車(chē)站分級(jí)(2013p4拓?fù)渑判?文化之旅(2012p4floyd算法)第四頁(yè)，共105頁(yè)。一、枚舉類(lèi)試題枚舉法的基本思想是根據(jù)提出的問(wèn)題枚舉所有可能的解，并用問(wèn)題給定的條件檢驗(yàn)?zāi)男┙馐切枰?，哪些解是不需要的。能使條件成立，即為其解。枚舉法其實(shí)是最簡(jiǎn)單的搜索算法。第五頁(yè)，共105頁(yè)。珠心算測(cè)驗(yàn)(noip2014普及組第一題)珠心算是一種通過(guò)在腦中模擬算盤(pán)變化來(lái)完成快速運(yùn)算的一種計(jì)算技術(shù)。珠心算訓(xùn)練，既能夠開(kāi)發(fā)智力，又能夠?yàn)槿粘Ｉ顜?lái)很多便利，因而在很多學(xué)校得到普及。某學(xué)校的珠心算老師采用一種快速考察珠心算加法能力的測(cè)驗(yàn)方法。他隨機(jī)生成一個(gè)正整數(shù)集合，集合中的數(shù)各不相同，然后要求學(xué)生回答：其中有多少個(gè)數(shù)，恰好等于集合中另外兩個(gè)（不同的）數(shù)之和？最近老師出了一些測(cè)驗(yàn)題，請(qǐng)你幫忙求出答案。第六頁(yè)，共105頁(yè)。珠心算測(cè)驗(yàn)(noip2014普及組第一題)【輸入】輸入共兩行，第一行包含一個(gè)整數(shù)n，表示測(cè)試題中給出的正整數(shù)個(gè)數(shù)。第二行有n個(gè)正整數(shù)，每?jī)蓚€(gè)正整數(shù)之間用一個(gè)空格隔開(kāi)，表示測(cè)試題中給出的正整數(shù)。【輸出】輸出共一行，包含一個(gè)整數(shù)，表示測(cè)驗(yàn)題答案?！緲永斎搿? 【樣例輸出】4 21234對(duì)于100%的數(shù)據(jù)，3

≤

n

≤

100測(cè)驗(yàn)題給出的正整數(shù)大小不超過(guò)10,000。第七頁(yè)，共105頁(yè)。試題分析題意大意：給你n個(gè)數(shù)，在這n個(gè)數(shù)中，找到滿(mǎn)足A+B=C的C的個(gè)數(shù)，注意不是這個(gè)等式的個(gè)數(shù)。樣例中，1,2,3,4有1+2=3，1+3=4兩個(gè)。由于本題數(shù)據(jù)規(guī)模n<=100，我們可以直接枚舉C,A,B，三層循環(huán)解決問(wèn)題。第八頁(yè)，共105頁(yè)。方法1：三層循環(huán)考試中，有許多選手的程序是這樣的，錯(cuò)在哪里？ans:=0;forc:=1tondofora:=1tondoforb:=1tondoif(f[c]=f[a]+f[b])and(c<>a)and(a<>b)and(c<>b)theninc(ans);writeln(ans);樣例中，上述錯(cuò)誤答案是4：3=1+2,3=2+1,4=1+3,4=3+1第九頁(yè)，共105頁(yè)。方法1：參考程序vari,n,a,b,c,t,ans:longint;f:array[0..105]oflongint;beginreadln(n);fori:=1tondoread(f[i]);ans:=0;forc:=1tondobegin

t:=0;fora:=1tondoforb:=1tondoif(f[c]=f[a]+f[b])and(t=0)and(c<>a)and(a<>b)and(c<>b)thenbegininc(ans);

t:=1;end;end;writeln(ans);end.第十頁(yè)，共105頁(yè)。方法2：兩層循環(huán)我們能不能使用兩層循環(huán)呢？由于本題測(cè)驗(yàn)題給出的正整數(shù)大小不超過(guò)10,000，我們可以直接枚舉A,B，判斷A+B在不在給定的數(shù)中即可。定義一個(gè)數(shù)組vis，初始值為0；讀入數(shù)a[i]時(shí)，vis[a[i]]標(biāo)記為1。

fori=1tondo{read(f[i]);vis[f[i]]=1;}第十一頁(yè)，共105頁(yè)。方法2：兩層循環(huán)兩層循環(huán)枚舉a,b的值，判斷a+b是否存在：

fora=1tondoforb=1tondoif(vis[f[a]+f[b]]=1)and(a<>b)thenbegininc(ans);vis[f[a]+f[b]]=2;//避免出現(xiàn)重復(fù)的等式 end;第十二頁(yè)，共105頁(yè)。方法2：參考代碼vari,n,a,b,ans:longint;vis:array[0..20005]of0..2;f:array[0..105]oflongint;beginreadln(n);fillchar(vis,sizeof(vis),0);fori:=1tondobeginread(f[i]);vis[f[i]]:=1;end;ans:=0;fora:=1tondoforb:=1tondoif(vis[f[a]+f[b]]=1)and(a<>b)thenbegininc(ans);vis[f[a]+f[b]]:=2;end;writeln(ans);end.第十三頁(yè)，共105頁(yè)。數(shù)字統(tǒng)計(jì)(noip2010普及組第一題)請(qǐng)統(tǒng)計(jì)某個(gè)給定范圍[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次。輸入格式輸入共一行，為兩個(gè)正整數(shù)L和R，之間用一個(gè)空格隔開(kāi)。輸出格式輸出共1行，表示數(shù)字2出現(xiàn)的次數(shù)。樣例輸入：222樣例輸出：6第十四頁(yè)，共105頁(yè)。試題分析題目大意是給定a,b，統(tǒng)計(jì)a,b之間數(shù)字2出現(xiàn)的次數(shù)。從a到b直接枚舉每一個(gè)數(shù)，判斷這個(gè)數(shù)中含有幾個(gè)2。fori=atobdo{

求i中含2的個(gè)數(shù)t;ans=ans+t;}輸出t;第十五頁(yè)，共105頁(yè)。參考程序：vari,a,b,ans:longint;beginreadln(a,b);ans:=0;fori:=atobdobeginifimod10=2theninc(ans);ifidiv10mod10=2theninc(ans);ifidiv10div10mod10=2theninc(ans);ifidiv10div10div10mod10=2theninc(ans);end;writeln(ans);end.第十六頁(yè)，共105頁(yè)。掃雷游戲(noip2015普及組第二題)掃雷游戲是一款十分經(jīng)典的單機(jī)小游戲。在n行m列的雷區(qū)中有一些格子含有地雷（稱(chēng)之為地雷格），其他格子不含地雷（稱(chēng)之為非地雷格）。玩家翻開(kāi)一個(gè)非地雷格時(shí)，該格將會(huì)出現(xiàn)一個(gè)數(shù)字——提示周?chē)褡又杏卸嗌賯€(gè)是地雷格。游戲的目標(biāo)是在不翻出任何地雷格的條件下，找出所有的非地雷格。

現(xiàn)在給出n行m列的雷區(qū)中的地雷分布，要求計(jì)算出每個(gè)非地雷格周?chē)牡乩赘駭?shù)。

注：一個(gè)格子的周?chē)褡影ㄆ渖?、下、左、右、左上、右上、左下、右下八個(gè)方向上與之直接相鄰的格子。

第十七頁(yè)，共105頁(yè)。掃雷游戲(noip2015普及組第二題)輸入樣例

1

3

3

*??

???

?*?

輸入樣例

2

2

3

?*?

*??

輸出樣例

1

mine.out

*10

221

1*1

輸出樣例

2

mine.out

2*1

*21對(duì)于

100%的數(shù)據(jù)，1≤n≤100，1≤m≤100

第十八頁(yè)，共105頁(yè)。問(wèn)題分析：本題也是簡(jiǎn)單的枚舉類(lèi)試題。我們從雷區(qū)的第一行第一列(1,1)開(kāi)始，判斷它周?chē)卸嗌賯€(gè)地雷。由于本題讀入的是字符，讀入時(shí)需要注意：

readln(n,m);fori=1tondobeginforj=1tomdoread(a[i][j]);

readln;end;第十九頁(yè)，共105頁(yè)。問(wèn)題分析：一個(gè)格子的周?chē)褡影ㄆ渖稀⑾?、左、右、左上、右上、左下、右下八個(gè)方向上與之直接相鄰的格子。判斷如下：

ifa[i][j-1]='*'theninc(s);ifa[i][j+1]='*'theninc(s);ifa[i+1][j-1]='*'theninc(s);ifa[i+1][j+1]='*'theninc(s);ifa[i+1][j]='*'theninc(s);ifa[i-1][j-1]='*'theninc(s);ifa[i-1][j+1]='*'theninc(s);ifa[i-1][j]='*'theninc(s);

第二十頁(yè)，共105頁(yè)。參考程序：vari,j,n,m,s:longint;a:array[0..105,0..105]ofchar;beginreadln(n,m);fori:=1tondobeginforj:=1tomdoread(a[i][j]);readln;end;fori:=1tondobeginforj:=1tomdobegins:=0;ifa[i,j]='*'thenwrite(a[i,j])elsebeginifa[i][j-1]='*'theninc(s);ifa[i][j+1]='*'theninc(s);ifa[i+1][j-1]='*'theninc(s);ifa[i+1][j+1]='*'theninc(s);ifa[i+1][j]='*'theninc(s);ifa[i-1][j-1]='*'theninc(s);ifa[i-1][j+1]='*'theninc(s);ifa[i-1][j]='*'theninc(s);write(s);end;end;writeln;end;end.第二十一頁(yè)，共105頁(yè)。比例簡(jiǎn)化(noip2014普及組第二題)在社交媒體上，經(jīng)常會(huì)看到針對(duì)某一個(gè)觀點(diǎn)同意與否的民意調(diào)查以及結(jié)果。例如，對(duì)某一觀點(diǎn)表示支持的有1498人，反對(duì)的有902人，那么贊同與反對(duì)的比例可以簡(jiǎn)單的記為1498:902。不過(guò)，如果把調(diào)查結(jié)果就以這種方式呈現(xiàn)出來(lái)，大多數(shù)人肯定不會(huì)滿(mǎn)意。因?yàn)檫@個(gè)比例的數(shù)值太大，難以一眼看出它們的關(guān)系。對(duì)于上面這個(gè)例子，如果把比例記為5:3，雖然與真實(shí)結(jié)果有一定的誤差，但依然能夠較為準(zhǔn)確地反映調(diào)查結(jié)果，同時(shí)也顯得比較直觀?，F(xiàn)給出支持人數(shù)A，反對(duì)人數(shù)B，以及一個(gè)上限L，請(qǐng)你將A比B化簡(jiǎn)為A’比B’，要求在A’和B’均不大于L且A’和B’互質(zhì)（兩個(gè)整數(shù)的最大公約數(shù)是1）的前提下，A’/B’≥A/B且A’/B’-A/B的值盡可能小。

第二十二頁(yè)，共105頁(yè)。比例簡(jiǎn)化(noip2014普及組第二題)輸入格式輸入共一行，包含三個(gè)整數(shù)A，B，L，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，分別表示支持人數(shù)、反對(duì)人數(shù)以及上限。輸出格式輸出共一行，包含兩個(gè)整數(shù)A’，B’，中間用一個(gè)空格隔開(kāi)，表示化簡(jiǎn)后的比例。樣例輸入149890210樣例輸出53第二十三頁(yè)，共105頁(yè)。比例簡(jiǎn)化試題分析讀入a,b,L后，從1到L分別枚舉a’和b’。判斷a’和b’是否合法，合法的話(huà)就記錄下來(lái)。輸入a,b,L;

fori=1toLdoforj=1toLdoifi,j合法then{ansx=i;ansy=j;}輸出ansx,ansy;第二十四頁(yè)，共105頁(yè)。比例簡(jiǎn)化試題分析程序的關(guān)鍵在于如何判斷i,j合法。if(gcd(i,j)=1)and(i/j>=a/b)thenifi/j-a/b<minnthenbeginminn:=i/j-a/b;ansx:=i;ansy:=j;end;條件1：i和j互質(zhì)；條件2：i/j的值大于等于A/B的值

；條件3：i/j－A/B的值盡可能小

；第二十五頁(yè)，共105頁(yè)。比例簡(jiǎn)化參考程序：vara,b,L,i,j,ansx,ansy:longint;minn:real;functiongcd(x,y:longint):longint;beginify=0thenexit(x);gcd:=gcd(y,xmody);end;beginreadln(a,b,L);minn:=99999999;fori:=1toLdoforj:=1toLdoif(gcd(i,j)=1)and(i/j>=a/b)thenifi/j-a/b<minnthenbeginminn:=i/j-a/b;ansx:=i;ansy:=j;end;writeln(ansx,'',ansy);end.

第二十六頁(yè)，共105頁(yè)。二、模擬類(lèi)試題有些問(wèn)題，我們很難建立數(shù)學(xué)模型，或者很難用計(jì)算機(jī)建立遞推、遞歸、枚舉、回溯法等算法。在這種情況下，一般采用模擬策略。所謂模擬策略就是模擬某個(gè)過(guò)程，通過(guò)改變數(shù)學(xué)模型的各種參數(shù)，進(jìn)而觀察變更這些參數(shù)所引起過(guò)程狀態(tài)的變化，由此展開(kāi)算法設(shè)計(jì)。第二十七頁(yè)，共105頁(yè)。金幣(noip2015普及組第一題)國(guó)王將金幣作為工資，發(fā)放給忠誠(chéng)的騎士。第一天，騎士收到一枚金幣；之后兩天（第二天和第三天），每天收到兩枚金幣；之后三天（第四、五、六天），每天收到三枚金幣；之后四天（第七、八、九、十天），每天收到四枚金幣……；這種工資發(fā)放模式會(huì)一直這樣延續(xù)下去：當(dāng)連續(xù)N天每天收到N枚金幣后，騎士會(huì)在之后的連續(xù)N+1天里，每天收到N+1枚金幣。

請(qǐng)計(jì)算在前K天里，騎士一共獲得了多少金幣。

輸入格式：

輸入文件只有1行，包含一個(gè)正整數(shù)K，表示發(fā)放金幣的天數(shù)。輸出格式：

輸出文件只有1行，包含一個(gè)正整數(shù)，即騎士收到的金幣數(shù)。輸入輸出樣例

輸入樣例：

1000輸出樣例： 29820第二十八頁(yè)，共105頁(yè)。試題分析本題直接模擬即可。定義變量時(shí)注意不要混淆了：i代表枚舉的天數(shù)，t代表連續(xù)的天數(shù)，也是每天收到的金幣數(shù)，s收到的金幣總數(shù)。讀入天數(shù)k;i=1;t=1;s=0;whilei<=kdo{forj=1totdo{s=s+t;i=i+1;ifi>kthenbreak;}t=t+1;}輸出s;第二十九頁(yè)，共105頁(yè)。參考程序：vari,

j,

k,

s,

t:longint;beginreadln(k);i:=1;t:=1;s:=0;whilei<=kdobeginforj:=1totdobegininc(s,t);inc(i);

ifi>kthenbreak;end;inc(t);end;writeln(s);end.第三十頁(yè)，共105頁(yè)。螺旋方陣(noip2014普及組第三題)一個(gè)n行n列的螺旋矩陣可由如下方法生成：從矩陣的左上角(第1行第1列)出發(fā)，初始時(shí)向右移動(dòng)；如果前方是未曾經(jīng)過(guò)的格子，則繼續(xù)前進(jìn)，否則右轉(zhuǎn)；重復(fù)上述操作直至經(jīng)過(guò)矩陣中所有格子。根據(jù)經(jīng)過(guò)順序，在格子中依次填入1,2,3,....，便構(gòu)成了一個(gè)螺旋矩陣。

現(xiàn)給出矩陣大小n以及i和j，請(qǐng)你求出該矩陣中第i行第j列的數(shù)是多少。

下圖是一個(gè)n=4時(shí)的螺旋矩陣。第三十一頁(yè)，共105頁(yè)。螺旋方陣(noip2014普及組第三題)輸入格式輸入共一行，包含三個(gè)整數(shù)n，i，j，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，分別表示矩陣大小、待求的數(shù)所在的行號(hào)和列號(hào)。輸出格式輸出共一行，包含一個(gè)整數(shù)，表示相應(yīng)矩陣中第i行第j列的數(shù)。樣例輸入：423

樣例輸出：14對(duì)于50%的數(shù)據(jù)，1≤n≤100;

對(duì)于100%的數(shù)據(jù)，1≤n≤30,000，1≤i≤n，1≤j≤n。

第三十二頁(yè)，共105頁(yè)。螺旋方陣試題分析本題首先讓我們想到傳統(tǒng)的模擬，從[1,1]開(kāi)始往數(shù)組中填充數(shù)字，但對(duì)于[30000,30000]的數(shù)組，直接爆零。對(duì)于讀入的n,x,y，先判斷(x,y)在第幾圈，再模擬圈內(nèi)的數(shù)字。第三十三頁(yè)，共105頁(yè)。螺旋方陣試題分析如：n=4,(2,2)在第2圈，(3,1)在第1圈。n=6，(4,5)在第2圈圈數(shù)q=min(x,y,n-x+1,n-y+1

)即目標(biāo)位置到四個(gè)邊界距離的最小值第三十四頁(yè)，共105頁(yè)。螺旋方陣試題分析圈數(shù)q求出后，前q圈的數(shù)字總和很容易求出來(lái)。對(duì)于任何一個(gè)方陣：第1圈有4n-4個(gè)數(shù);第2圈有4(n-2)-4個(gè)數(shù)；第3圈有4(n-4)-4個(gè)數(shù)；……第q圈有4(n-q(n-1))-4個(gè)數(shù)第三十五頁(yè)，共105頁(yè)。螺旋方陣試題分析前1圈有4n-4個(gè)數(shù);前2圈有4n-4+4(n-2)-4=2(4n-2*4)個(gè)數(shù)；前3圈有4(n-4)-4+2(4n-8)=3(4n-3*4)個(gè)數(shù)；……前q圈有q(4n-4q)個(gè)數(shù)；第三十六頁(yè)，共105頁(yè)。螺旋方陣試題分析目標(biāo)位置(i,j)到底在當(dāng)前這一圈的第幾個(gè)位置？如目標(biāo)數(shù)26所在的位置(4,5)，在第2圈的什么位置？分兩種情況：1）目標(biāo)數(shù)(i,j)在上行或右行；i+j-2q+12）目標(biāo)數(shù)(i,j)在下行或左行；距離第一個(gè)數(shù)的距離

i+j-2q+1第三十七頁(yè)，共105頁(yè)。螺旋方陣參考程序：varn,i,j,q,ans:longint;functionmin(a,b:longint):longint;beginifa<bthenexit(a)elseexit(b);end;beginreadln(n,i,j);q:=min(i,min(j,min(n-i+1,n-j+1)));ifi<=jthenans:=q*(4*(n-1)-4*q)+10*q-4*n-3+i+jelseans:=q*(4*n-4*q)+2*q+1-i-j;writeln(ans);end.第三十八頁(yè)，共105頁(yè)。計(jì)數(shù)問(wèn)題(noip2013普及組第一題)試計(jì)算在區(qū)間1到n的所有整數(shù)中，數(shù)字x（0≤x≤9）共出現(xiàn)了多少次？

例如，在1到11中，即在1、2、3、4、5、6、7、8、9、10、11中，數(shù)字1出現(xiàn)了4次。輸入：輸入共1行，包含2個(gè)整數(shù)n、x，之間用一個(gè)空格隔開(kāi)。

輸出：輸出共1行，包含一個(gè)整數(shù)，表示x出現(xiàn)的次數(shù)。

輸入示例：

11

1輸出示例：

4其他說(shuō)明：對(duì)于100%的數(shù)據(jù)，1≤n≤1,000,000，0≤x≤9。

第三十九頁(yè)，共105頁(yè)。計(jì)數(shù)問(wèn)題試題分析這道題入門(mén)難度，直接模擬。循環(huán)1到n之間的所有數(shù)，對(duì)每個(gè)數(shù)的每位判斷即可。讀入n,x;fori=1tondo{k=i;whilek的每一位jdoifj=xtheninc(ans);}輸出ans;第四十頁(yè)，共105頁(yè)。計(jì)數(shù)問(wèn)題參考程序這道題入門(mén)難度，直接模擬。循環(huán)1到n之間的所有數(shù)，對(duì)每個(gè)數(shù)的每位判斷即可。vari,n,x,k,ans:longint;beginreadln(n,x);ans:=0;fori:=1tondobegink:=i;whilek>0dobeginifkmod10=xtheninc(ans);k:=kdiv10;end;end;writeln(ans);end.第四十一頁(yè)，共105頁(yè)。尋寶(noip2012普及組第二題)

傳說(shuō)很遙遠(yuǎn)的藏寶樓頂層藏著誘人的寶藏。小明歷盡千辛萬(wàn)苦終于找到傳說(shuō)中的這個(gè)藏寶樓，藏寶樓的門(mén)口豎著一個(gè)木板，上面寫(xiě)有幾個(gè)大字：尋寶說(shuō)明書(shū)。說(shuō)明書(shū)的內(nèi)容如下：

藏寶樓共有N+1層，最上面一層是頂層，頂層有一個(gè)房間里面藏著寶藏。除了頂層外，藏寶樓另有N層，每層M個(gè)房間，這M個(gè)房間圍成一圈并按逆時(shí)針?lè)较蛞来尉幪?hào)為0，…，M-1。其中一些房間有通往上一層的樓梯，每層樓的樓梯設(shè)計(jì)可能不同。每個(gè)房間里有一個(gè)指示牌，指示牌上有一個(gè)數(shù)字x，表示從這個(gè)房間開(kāi)始按逆時(shí)針?lè)较蜻x擇第x個(gè)有樓梯的房間（假定該房間的編號(hào)為k），從該房間上樓，上樓后到達(dá)上一層的k號(hào)房間。比如當(dāng)前房間的指示牌上寫(xiě)著2，則按逆時(shí)針?lè)较蜷_(kāi)始嘗試，找到第2個(gè)有樓梯的房間，從該房間上樓。如果當(dāng)前房間本身就有樓梯通向上層，該房間作為第一個(gè)有樓梯的房間。第四十二頁(yè)，共105頁(yè)。尋寶(noip2012普及組第二題)

尋寶說(shuō)明書(shū)的最后用紅色大號(hào)字體寫(xiě)著：“尋寶須知：幫助你找到每層上樓房間的指示牌上的數(shù)字（即每層第一個(gè)進(jìn)入的房間內(nèi)指示牌上的數(shù)字）總和為打開(kāi)寶箱的密鑰”。

請(qǐng)幫助小明算出這個(gè)打開(kāi)寶箱的密鑰?！据斎搿?/p>

第一行2個(gè)整數(shù)N和M，之間用一個(gè)空格隔開(kāi)。N表示除了頂層外藏寶樓共N層樓，M表示除頂層外每層樓有M個(gè)房間。

接下來(lái)N*M

行，每行兩個(gè)整數(shù)，之間用一個(gè)空格隔開(kāi)，每行描述一個(gè)房間內(nèi)的情況，其中第(i-1)*M+j行表示第i層j-1號(hào)房間的情況（i=1,2,…,N；j=1,2,…,M）。第一個(gè)整數(shù)表示該房間是否有樓梯通往上一層（0表示沒(méi)有，1表示有），第二個(gè)整數(shù)表示指示牌上的數(shù)字。注意，從j號(hào)房間的樓梯爬到上一層到達(dá)的房間一定也是j號(hào)房間。

最后一行，一個(gè)整數(shù)，表示小明從藏寶樓底層的幾號(hào)房間進(jìn)入開(kāi)始尋寶（注：房間編號(hào)從0開(kāi)始）。第四十三頁(yè)，共105頁(yè)。尋寶(noip2012普及組第二題)【輸出】輸出只有一行，一個(gè)整數(shù)，表示打開(kāi)寶箱的密鑰，這個(gè)數(shù)可能會(huì)很大，請(qǐng)輸出對(duì)20123取模的結(jié)果即可。

【輸入輸出樣例】treasure.in treasure.out23 51203140115121第四十四頁(yè)，共105頁(yè)。尋寶(noip2012普及組第二題)【輸入輸出樣例說(shuō)明】第一層：0號(hào)房間，有樓梯通往上層，指示牌上的數(shù)字是2；1號(hào)房間，無(wú)樓梯通往上層，指示牌上的數(shù)字是3；2號(hào)房間，有樓梯通往上層，指示牌上的數(shù)字是4；第二層：0號(hào)房間，無(wú)樓梯通往上層，指示牌上的數(shù)字是1；1號(hào)房間，有樓梯通往上層，指示牌上的數(shù)字是5；2號(hào)房間，有樓梯通往上層，指示牌上的數(shù)字是2；小明首先進(jìn)入第一層（底層）的1號(hào)房間，記下指示牌上的數(shù)字為3，然后從這個(gè)房間開(kāi)始，沿逆時(shí)針?lè)较蜻x擇第3個(gè)有樓梯的房間2號(hào)房間進(jìn)入，上樓后到達(dá)第二層的2號(hào)房間，記下指示牌上的數(shù)字為2，由于當(dāng)前房間本身有樓梯通向上層，該房間作為第一個(gè)有樓梯的房間。因此，此時(shí)沿逆時(shí)針?lè)较蜻x擇第2個(gè)有樓梯的房間即為1號(hào)房間，進(jìn)入后上樓梯到達(dá)頂層。這時(shí)把上述記下的指示牌上的數(shù)字加起來(lái)，即3+2=5，所以打開(kāi)寶箱的密鑰就是5。第四十五頁(yè)，共105頁(yè)。尋寶試題分析題目大意：n層樓，每層m個(gè)房間。每個(gè)房間有一個(gè)號(hào)碼，樓梯。從底樓出發(fā)，如果該房間有樓梯，直接上樓，否則走到該層下個(gè)指定的房間。將每一層第一個(gè)到達(dá)的房間號(hào)加起來(lái)就是答案。第四十六頁(yè)，共105頁(yè)。尋寶試題分析我們把每一層樓看成一個(gè)圈，完全模擬一下小明的行走路線(xiàn)即可。注意細(xì)節(jié)：1.房間號(hào)從0開(kāi)始，所以讀入時(shí)要注意；readln(n,m);fori=1tondoforj=0tom-1do讀入樓梯和號(hào)碼；第四十七頁(yè)，共105頁(yè)。尋寶試題分析我們把每一層樓看成一個(gè)圈，完全模擬一下小明的行走路線(xiàn)即可。注意細(xì)節(jié)：1.房間號(hào)從0開(kāi)始，所以讀入時(shí)要注意；2.讀入時(shí)統(tǒng)計(jì)每一層有多少個(gè)帶樓梯的房間；readln(n,m);fori=1tondoforj=0tom-1do

beginreadln(stair[i,j],num[i,j]);ifstair[i,j]=1theninc(sum[i]);end;第四十八頁(yè)，共105頁(yè)。尋寶試題分析我們把每一層樓看成一個(gè)圈，完全模擬一下小明的行走路線(xiàn)即可。注意細(xì)節(jié)：1.房間號(hào)從0開(kāi)始，所以讀入時(shí)要注意；2.讀入時(shí)統(tǒng)計(jì)每一層有多少個(gè)帶樓梯的房間；3.理解“從這個(gè)房間開(kāi)始按逆時(shí)針?lè)较蜻x擇第x個(gè)有樓梯的房間”。假如當(dāng)前房間沒(méi)有樓梯，指示牌上的號(hào)為j：whilej>0dobeginifstair[i,k]=1thendec(j);ifj>0thenk:=(k+1)modm;end;第四十九頁(yè)，共105頁(yè)。尋寶參考程序vari,j,n,m,k,ans:longint;num:array[0..10001,0..101]oflongint;sum:array[0..10001]oflongint;stair:array[0..10001,0..101]of0..1;beginreadln(n,m);fillchar(sum,sizeof(sum),0);fori:=1tondoforj:=0tom-1dobeginreadln(stair[i,j],num[i,j]);ifstair[i,j]=1theninc(sum[i]);end;readln(k);ans:=0;fori:=1tondobeginans:=(ans+num[i,k])mod20123;num[i,k]:=num[i,k]modsum[i];ifnum[i,k]=0thennum[i,k]:=sum[i];j:=num[i,k];whilej>0dobeginifstair[i,k]=1thendec(j);ifj>0thenk:=(k+1)modm;end;end;writeln(ans);end.

第五十頁(yè)，共105頁(yè)。接水問(wèn)題(noip2010普及組第二題)學(xué)校里有一個(gè)水房，水房里一共裝有m個(gè)龍頭可供同學(xué)們打開(kāi)水，每個(gè)龍頭每秒鐘的供水量相等，均為1。現(xiàn)在有n名同學(xué)準(zhǔn)備接水，他們的初始接水順序已經(jīng)確定。將這些同學(xué)按接水順序從1到n編號(hào)，i號(hào)同學(xué)的接水量為wi。接水開(kāi)始時(shí)，1到m號(hào)同學(xué)各占一個(gè)水龍頭，并同時(shí)打開(kāi)水龍頭接水。當(dāng)其中某名同學(xué)j完成其接水量要求wj

后，下一名排隊(duì)等候接水的同學(xué)k馬上接替j同學(xué)的位置開(kāi)始接水。這個(gè)換人的過(guò)程是瞬間完成的，且沒(méi)有任何水的浪費(fèi)。即j同學(xué)第x秒結(jié)束時(shí)完成接水，則k同學(xué)第x+1秒立刻開(kāi)始接水。若當(dāng)前接水人數(shù)n不足m，則只有n個(gè)龍頭供水，其它m?n個(gè)龍頭關(guān)閉?，F(xiàn)在給出n名同學(xué)的接水量，按照上述接水規(guī)則，問(wèn)所有同學(xué)都接完水需要多少秒。第五十一頁(yè)，共105頁(yè)。接水問(wèn)題(noip2010普及組第二題)輸入第1行2個(gè)整數(shù)n和m，用一個(gè)空格隔開(kāi)，分別表示接水人數(shù)和龍頭個(gè)數(shù)。第2行n個(gè)整數(shù)w1、w2、……、wn，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，wi

表示i號(hào)同學(xué)的接水量。輸出輸出只有一行，1個(gè)整數(shù)，表示接水所需的總時(shí)間。樣例輸入： 53 44121樣例輸出：

4第五十二頁(yè)，共105頁(yè)。接水問(wèn)題試題分析題目大意：n個(gè)人排隊(duì)順序接水，共m個(gè)水龍頭。求接完水需要最少的秒數(shù)。本題直接模擬即可。有的選手在考試中使用秒去枚舉，結(jié)果嚴(yán)重超時(shí)。對(duì)于每一個(gè)人，選擇這m個(gè)水龍頭中接水量最小的去接。最后輸出這m個(gè)水龍頭中接水量最大的。第五十三頁(yè)，共105頁(yè)。接水問(wèn)題參考程序vara:array[0..10001]oflongint;s:array[0..101]oflongint;n,m,i,j,k,ans,minn:longint;beginreadln(n,m);fori:=1tondoread(a[i]);fillchar(s,sizeof(s),0);fori:=1tondobeginminn:=9999999;forj:=1tomdoifs[j]<minnthenbegink:=j;minn:=s[j];end;inc(s[k],a[i]);end;ans:=0;fori:=1tomdoifs[i]>ansthenans:=s[i];writeln(ans);end.

第五十四頁(yè)，共105頁(yè)。三、字符串類(lèi)試題對(duì)于字符串、表達(dá)式的求解、大整數(shù)的處理等等，我們經(jīng)常采用字符串來(lái)處理。字符串處理常見(jiàn)函數(shù)和過(guò)程：length()、delete()pos()、val()、str()第五十五頁(yè)，共105頁(yè)。數(shù)字反轉(zhuǎn)(noip2011普及組第一題)給定一個(gè)整數(shù)，請(qǐng)將該數(shù)各個(gè)位上數(shù)字反轉(zhuǎn)得到一個(gè)新數(shù)。新數(shù)也應(yīng)滿(mǎn)足整數(shù)的常見(jiàn)形式，即除非給定的原數(shù)為零，否則反轉(zhuǎn)后得到的新數(shù)的最高位數(shù)字不應(yīng)為零（如：輸入-380，輸出-83）。輸入輸入共1行，一個(gè)整數(shù)N。輸出輸出共1行，一個(gè)整數(shù)，表示反轉(zhuǎn)后的新數(shù)。樣例輸入123樣例輸出321第五十六頁(yè)，共105頁(yè)。數(shù)字反轉(zhuǎn)試題分析方法1：直接降位取個(gè)位降位：ndiv10取個(gè)位：nmod10注意刪去末尾的0！缺點(diǎn)：數(shù)不能太大，容易溢出！第五十七頁(yè)，共105頁(yè)。數(shù)字反轉(zhuǎn)試題分析varn:longint;beginreadln(n);ifn<0thenbeginwrite('-');n:=-n;end;ifn=0thenwrite(0)elsebeginwhile(nmod10=0)don:=ndiv10;whilen>0dobeginwrite(nmod10);n:=ndiv10;end;end;end.第五十八頁(yè)，共105頁(yè)。數(shù)字反轉(zhuǎn)試題分析方法2：字符串注意1：負(fù)數(shù)的處理ifs[1]='-'thenbeginwrite('-');delete(s,1,1);end;

第五十九頁(yè)，共105頁(yè)。數(shù)字反轉(zhuǎn)試題分析方法2：字符串注意1：負(fù)數(shù)的處理注意2：末尾0的處理：len=length(s);while(s[len]='0')dodec(len);

fori=lendownto1dowrite(s[i]);

第六十頁(yè)，共105頁(yè)。數(shù)字反轉(zhuǎn)參考程序vars:ansistring;i,len:longint;beginreadln(s);ifs[1]='-'thenbeginwrite('-');delete(s,1,1);end;len:=length(s);while(s[len]='0')dodec(len);fori:=lendownto1dowrite(s[i]);end.第六十一頁(yè)，共105頁(yè)。統(tǒng)計(jì)單詞個(gè)數(shù)(noip2011普及組第二題)一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有的還能統(tǒng)計(jì)出特定單詞在文章中出現(xiàn)的次數(shù)。

現(xiàn)在，請(qǐng)你編程實(shí)現(xiàn)這一功能，具體要求是：給定一個(gè)單詞，請(qǐng)你輸出它在給定的文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置。注意：匹配單詞時(shí)，不區(qū)分大小寫(xiě)，但要求完全匹配，即給定單詞必須與文章中的某一獨(dú)立單詞在不區(qū)分大小寫(xiě)的情況下完全相同（參見(jiàn)樣例1），如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見(jiàn)樣例2）。

第六十二頁(yè)，共105頁(yè)。統(tǒng)計(jì)單詞個(gè)數(shù)(noip2011普及組第二題)輸入格式第1行為一個(gè)字符串，其中只含字母，表示給定單詞；

第2行為一個(gè)字符串，其中只可能包含字母和空格，表示給定的文章。輸出格式只有一行，如果在文章中找到給定單詞則輸出兩個(gè)整數(shù)，兩個(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，分別是單詞在文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置（即在文章中第一次出現(xiàn)時(shí)，單詞首字母在文章中的位置，位置從0開(kāi)始）；如果單詞在文章中沒(méi)有出現(xiàn)，則直接輸出一個(gè)整數(shù)-1。

第六十三頁(yè)，共105頁(yè)。統(tǒng)計(jì)單詞個(gè)數(shù)(noip2011普及組第二題)樣例輸入1：

To

to

be

or

not

to

be

is

a

question樣例輸出1：

2

0樣例輸入2：

to

Did

the

Ottoman

Empire

lose

its

power

at

that

time

樣例輸出2：

-1

【輸入輸出樣例2說(shuō)明】

表示給定的單詞to在文章中沒(méi)有出現(xiàn)，輸出整數(shù)-1。注釋說(shuō)明1≤單詞長(zhǎng)度≤10。

1≤文章長(zhǎng)度≤1,000,000。第六十四頁(yè)，共105頁(yè)。統(tǒng)計(jì)單詞個(gè)數(shù)試題分析本題是簡(jiǎn)單的字符串處理。讀入單詞和文章（字符串）后，可以把單詞和文章全部轉(zhuǎn)換成大寫(xiě)（或小寫(xiě)），然后循環(huán)在文章中對(duì)單詞進(jìn)行查找，找到就存儲(chǔ)位置，并統(tǒng)計(jì)找到的次數(shù)。轉(zhuǎn)換成大寫(xiě)有兩種方法：方法1：利用ord()和chr()函數(shù)逐個(gè)字符轉(zhuǎn)換：fori=1tolength(s)doifs[i]>='a'thens[i]:=chr(ord(s[i])-32);方法2：利用upcase()函數(shù)直接轉(zhuǎn)換：s=upcase(s);第六十五頁(yè)，共105頁(yè)。統(tǒng)計(jì)單詞個(gè)數(shù)試題分析本題還有一個(gè)問(wèn)題需要處理：查找的單詞s1只是文章s中某個(gè)單詞的一部分，如：ToDid

the

Ottoman

Empire處理方法：讀入單詞s1后，在s1的兩端各添加一個(gè)空格。s1=''+s1+''第六十六頁(yè)，共105頁(yè)。統(tǒng)計(jì)單詞個(gè)數(shù)參考程序vars1,s:ansistring;i,p,len,ans:longint;beginreadln(s1);//單詞

readln(s);//文章

s1:=''+upcase(s1)+'';s:=''+upcase(s)+'';p:=-1;ans:=0;len:=length(s1);fori:=1tolength(s)-len+1doifcopy(s,i,len)=s1thenbeginifp=-1thenp:=i-1;inc(ans);end;ifp=-1thenwrite(p)elsewrite(ans,'',p);end.第六十七頁(yè)，共105頁(yè)。四、貪心類(lèi)試題從問(wèn)題的某一個(gè)初始解出發(fā)，向給定的目標(biāo)遞推。推進(jìn)的每一步不是依據(jù)某一固定的遞推公式，而是做一個(gè)當(dāng)時(shí)看似最佳的貪心選擇，不斷地將問(wèn)題歸納為更小的相似的子問(wèn)題，最終產(chǎn)生出一個(gè)全局最優(yōu)解。第六十八頁(yè)，共105頁(yè)。排座椅(noip2008普及組第二題)上課的時(shí)候總有一些同學(xué)和前后左右的人交頭接耳，這是令小學(xué)班主任十分頭疼的一件事情。不過(guò)，班主任小雪發(fā)現(xiàn)了一些有趣的現(xiàn)象，當(dāng)同學(xué)們的座次確定下來(lái)之后，只有有限的D對(duì)同學(xué)上課時(shí)會(huì)交頭接耳。同學(xué)們?cè)诮淌抑凶闪薓行N列，坐在第i行第j列的同學(xué)的位置是（i，j），為了方便同學(xué)們進(jìn)出，在教室中設(shè)置了K條橫向的通道，L條縱向的通道。于是，聰明的小雪想到了一個(gè)辦法，或許可以減少上課時(shí)學(xué)生交頭接耳的問(wèn)題：她打算重新擺放桌椅，改變同學(xué)們桌椅間通道的位置，因?yàn)槿绻粭l通道隔開(kāi)了兩個(gè)會(huì)交頭接耳的同學(xué)，那么他們就不會(huì)交頭接耳了。

請(qǐng)你幫忙給小雪編寫(xiě)一個(gè)程序，給出最好的通道劃分方案。在該方案下，上課時(shí)交頭接耳的學(xué)生對(duì)數(shù)最少。第六十九頁(yè)，共105頁(yè)。排座椅(noip2008普及組第二題)輸入輸入的第一行，有5個(gè)用空格隔開(kāi)的整數(shù)，分別是M，N，K，L，D（2<=N，M<=1000，0<=K<M，0<=L<N，D<=2000）。

接下來(lái)D行，每行有4個(gè)用空格隔開(kāi)的整數(shù)，第i行的4個(gè)整數(shù)Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)與(Pi,Qi)的兩個(gè)同學(xué)會(huì)交頭接耳（輸入保證他們前后相鄰或者左右相鄰）。

輸入數(shù)據(jù)保證最優(yōu)方案的唯一性。輸出輸出共兩行。

第一行包含K個(gè)整數(shù)，a1a2……aK，表示第a1行和a1+1行之間、第a2行和第a2+1行之間、…、第aK行和第aK+1行之間要開(kāi)辟通道，其中ai<

ai+1，每?jī)蓚€(gè)整數(shù)之間用空格隔開(kāi)（行尾沒(méi)有空格）。

第二行包含L個(gè)整數(shù)，b1b2……bk，表示第b1列和b1+1列之間、第b2列和第b2+1列之間、…、第bL列和第bL+1列之間要開(kāi)辟通道，其中bi<

bi+1，每?jī)蓚€(gè)整數(shù)之間用空格隔開(kāi)（行尾沒(méi)有空格）。第七十頁(yè)，共105頁(yè)。排座椅(noip2008普及組第二題)輸入樣例45123424323332524

輸出樣例224第七十一頁(yè)，共105頁(yè)。排座椅試題分析貪心。題意：教室有m行n列，現(xiàn)在要?jiǎng)澐謐條橫向通道，L條縱向的通道。交頭接耳的學(xué)生位置[xi,yi]和[pi,qi]。怎么劃分通道，使得上課時(shí)交頭接耳的學(xué)生對(duì)數(shù)最少。用row[i]記錄第i行與第i+1行之間有多少對(duì)交頭接耳的；用col[i]記錄第i列與第i+1列有多少對(duì)交頭接耳的。將row從大到小排序，前k個(gè)即為要隔開(kāi)的行；將col從大到小排序，前L個(gè)即為要隔開(kāi)的列。第七十二頁(yè)，共105頁(yè)。排座椅試題分析程序的框架：讀入m,n,k,L,d;Fori=1tod{

讀入x,y,p,q;ifx=ptheninc(row[min(x,p)].value)elseinc(col[min(y,q)].value);}對(duì)數(shù)組row按row.value從大到小排序;對(duì)于數(shù)組row[1]到row[k]按row.no從小到大排序；輸出row[1]…row[k];對(duì)數(shù)組col按col.value從大到小排序;對(duì)于數(shù)組col[1]到col[L]按col.no從小到大排序；輸出col[1]…col[L];第七十三頁(yè)，共105頁(yè)。排座椅參考程序varm,n,t,k,L,d,i,j,x,y,p,q,maxx:longint;row,col,a:array[0..1005]oflongint;functionmin(x,y:longint):longint;beginifx>ythenexit(y)elseexit(x);end;beginreadln(m,n,k,L,d);fillchar(row,sizeof(row),0);fillchar(col,sizeof(col),0);fori:=1toddobeginreadln(x,y,p,q);ifx=ptheninc(col[min(y,q)])elseinc(row[min(x,p)]);end;t:=0;whilet<kdo//求行中說(shuō)話(huà)最多的k個(gè)人

beginmaxx:=1;fori:=2tomdoifrow[i]>row[maxx]thenmaxx:=i;row[maxx]:=-1;inc(t);end;t:=0;whilet<Ldo//求列中說(shuō)話(huà)最多的L個(gè)人

beginmaxx:=1;fori:=2tondoifcol[i]>col[maxx]thenmaxx:=i;col[maxx]:=-1;inc(t);end;fori:=1tomdoifrow[i]=-1thenwrite(i,'');writeln;fori:=1tondoifcol[i]=-1thenwrite(i,'');writeln;end.第七十四頁(yè)，共105頁(yè)。紀(jì)念品分組(noip2007普及組第二題)元旦快到了，校學(xué)生會(huì)讓樂(lè)樂(lè)負(fù)責(zé)新年晚會(huì)的紀(jì)念品發(fā)放工作。為使得參加晚會(huì)的同學(xué)所獲得的紀(jì)念品價(jià)值相對(duì)均衡，他要把購(gòu)來(lái)的紀(jì)念品根據(jù)價(jià)格進(jìn)行分組，但每組最多只能包括兩件紀(jì)念品，并且每組紀(jì)念品的價(jià)格之和不能超過(guò)一個(gè)給定的整數(shù)。為了保證在盡量短的時(shí)間內(nèi)發(fā)完所有紀(jì)念品，樂(lè)樂(lè)希望分組的數(shù)目最少。你的任務(wù)是寫(xiě)一個(gè)程序，找出所有分組方案中分組數(shù)最少的一種，輸出最少的分組數(shù)目。第七十五頁(yè)，共105頁(yè)。紀(jì)念品分組(noip2007普及組第二題)輸入包含n+2行:第1行包括一個(gè)整數(shù)w，為每組紀(jì)念品價(jià)格之和的上眼=

第2行為一個(gè)整數(shù)n，表示購(gòu)來(lái)的紀(jì)念品的總件數(shù)G第3-n+2行每行包含一個(gè)正整數(shù)Pi(5<=Pi<=w3)w表示所對(duì)應(yīng)紀(jì)念品的價(jià)格。輸出僅一行，包含一個(gè)整數(shù)，

ep最少的分組數(shù)目合第七十六頁(yè)，共105頁(yè)。紀(jì)念品分組(noip2007普及組第二題)樣例輸入： 樣例輸出：100 69

90

20

20

30

50

60

70

80

90100%的數(shù)據(jù)滿(mǎn)足:1<=n<=30000，

80<=W<=200第七十七頁(yè)，共105頁(yè)。紀(jì)念品分組試題分析算法：貪心先按n件紀(jì)念品的價(jià)值進(jìn)行排序，貪心策略是價(jià)值最小的與價(jià)值最大的為一組，這樣分組是最少的。第七十八頁(yè)，共105頁(yè)。紀(jì)念品分組試題分析算法：貪心先按n件紀(jì)念品的價(jià)值進(jìn)行排序，貪心策略是價(jià)值最小的與價(jià)值最大的為一組，這樣分組是最少的。第七十九頁(yè)，共105頁(yè)。紀(jì)念品分組參考程序vari,j,t,m,n,left,right,ans:longint;a:array[0..30001]oflongint;beginreadln(m,n);fori:=1tondoreadln(a[i]);fori:=1ton-1doforj:=i+1tondoifa[i]>a[j]thenbegint:=a[i];a[i]:=a[j];a[j]:=t;end;ans:=0;left:=1;right:=n;whileleft<=rightdobeginifa[left]+a[right]<=mthenbegininc(left);dec(right);endelsedec(right);inc(ans);end;ifleft=righttheninc(ans);writeln(ans);end.第八十頁(yè)，共105頁(yè)。六、簡(jiǎn)單動(dòng)態(tài)規(guī)劃類(lèi)試題動(dòng)態(tài)規(guī)劃是解決多階段決策最優(yōu)化問(wèn)題的一種思想方法。一般我們從初始階段出發(fā)，枚舉每個(gè)階段的所有狀態(tài)，在狀態(tài)轉(zhuǎn)移的過(guò)程中，我們需要決策。根據(jù)每一步所選決策的不同，將隨即引起狀態(tài)的轉(zhuǎn)移，最終在變化的狀態(tài)中產(chǎn)生一個(gè)決策序列。動(dòng)態(tài)規(guī)劃就是為了使產(chǎn)生的決策序列在符合某種條件下達(dá)到最優(yōu)。普及組一般考查的動(dòng)態(tài)規(guī)劃：01背包，最長(zhǎng)上升子序列，一些簡(jiǎn)單的線(xiàn)性動(dòng)規(guī)。第八十一頁(yè)，共105頁(yè)。守望者的逃離(noip2007普及組第三題)惡魔獵手尤迫安野心勃勃.他背叛了暗夜精靈，率深藏在海底的那加企圖叛變：守望者在與尤迪安的交鋒中遭遇了圍殺.被困在一個(gè)荒蕪的大島上。為了殺死守望者，尤迪安開(kāi)始對(duì)這個(gè)荒島施咒，這座島很快就會(huì)沉下去，到那時(shí)，島上的所有人都會(huì)遇難：守望者的跑步速度，為17m/s，以這樣的速度是無(wú)法逃離荒島的。慶幸的是守望者擁有閃爍法術(shù)，可在1s內(nèi)移動(dòng)60m，不過(guò)每次使用閃爍法術(shù)都會(huì)消耗魔法值10點(diǎn)。守望者的魔法值恢復(fù)的速度為4點(diǎn)/s，只有處在原地休息狀態(tài)時(shí)才能恢復(fù)?，F(xiàn)在已知守望者的魔法初值M，他所在的初始位置與島的出口之間的距離S，島沉沒(méi)的時(shí)間T。你的任務(wù)是寫(xiě)一個(gè)程序幫助守望者計(jì)算如何在最短的時(shí)間內(nèi)逃離荒島，若不能逃出，則輸出守望者在剩下的時(shí)間內(nèi)能走的最遠(yuǎn)距離。注意:守望者跑步、閃爍或休息活動(dòng)均以秒(s)為單位。且每次活動(dòng)的持續(xù)時(shí)間為整數(shù)秒。距離的單位為米(m)。第八十二頁(yè)，共105頁(yè)。守望者的逃離(noip2007普及組第三題)輸入輸入文件escape.in僅一行，包括空格隔開(kāi)的三個(gè)非負(fù)整數(shù)M，S，T。輸出輸出文件escape.out包含兩行:第1行為字符串“Yes”或“No”(區(qū)分大小寫(xiě))，即守望者是否能逃離荒島。第2行包含一個(gè)整數(shù)，第一行為“Yes”(區(qū)分大小寫(xiě)）時(shí)表示守望著逃離荒島的最短時(shí)間第一行為“No”(區(qū)分大小寫(xiě))

時(shí)表示守望者能走的最遠(yuǎn)距離。樣例輸入392004樣例輸出No197提示100%的數(shù)據(jù)滿(mǎn)足:1<=T<=300000,

0<=M<=10001<=S<=10^8第八十三頁(yè)，共105頁(yè)。守望者的逃離試題分析題目大意：一個(gè)人在t時(shí)間內(nèi)是否能夠行走的s米的距離，行走的方式有兩種：1.使用魔法（每秒60米），缺點(diǎn)每秒耗費(fèi)10點(diǎn)魔法值；2.跑步（每秒17米）。第八十四頁(yè)，共105頁(yè)。守望者的逃離試題分析算法：貪心

+背包型動(dòng)態(tài)規(guī)劃貪心的策略：有魔法的情況下，肯定先用魔法跑，這樣跑的快！如果魔法不夠，那么我們利用背包模型，只有在下列兩種選擇中選擇其中一種：1、使用魔法2、跑步第八十五頁(yè)，共105頁(yè)。守望者的逃離試題分析令f[i]表示前i秒利用魔法行走的距離；dp[i]表示利用魔法或者跑步行走的最大距離。很容易求出1到t的f[i]的值：fori=1totdo{ifmagic>=10then{magic=magic-10;f[i]=f[i-1]+60;}else{magic=magic+4;f[i]=f[i-1];}}第八十六頁(yè)，共105頁(yè)。守望者的逃離試題分析下面求dp[i]，01背包：

dp[i]=max(dp[i-1]+17,f[i]);第八十七頁(yè)，共105頁(yè)。守望者的逃離參考程序vari,m,s,t,ok:longint;f,dp:array[0..300001]oflongint;functionmax(x,y:longint):longint;beginifx>ythenexit(x)elseexit(y);end;beginreadln(m,s,t);fillchar(f,sizeof(f),0);fillchar(dp,sizeof(dp),0);ok:=0;fori:=1totdobeginifm>=10thenbeginm:=m-10;f[i]:=f[i-1]+60;endelsebeginm:=m+4;f[i]:=f[i-1];end;dp[i]:=max(dp[i-1]+17,f[i]);

ifdp[i]>=sthenbeginwriteln('Yes');writeln(i);ok:=1;break;end;end;ifok=0thenbeginwriteln('No');writeln(dp[t]);end;end.

第八十八頁(yè)，共105頁(yè)。小朋友的數(shù)字(noip2013普及組第三題)有n個(gè)小朋友排成一列。每個(gè)小朋友手上都有一個(gè)數(shù)字,這個(gè)數(shù)字可正可負(fù)。規(guī)定每個(gè)小朋友的特征值等于排在他前面(包括他本人)的小朋友中連續(xù)若干個(gè)(最少有一個(gè))小朋友手上的數(shù)字之和的最大值。

作為這些小朋友的老師,你需要給每個(gè)小朋友一個(gè)分?jǐn)?shù),分?jǐn)?shù)是這樣規(guī)定的:第一個(gè)小朋友的分?jǐn)?shù)是他的特征值,其它小朋友的分?jǐn)?shù)為排在他前面的所有小朋友中(不包括他本人),小朋友分?jǐn)?shù)加上其特征值的最大值。

請(qǐng)計(jì)算所有小朋友分?jǐn)?shù)的最大值,輸出時(shí)保持最大值的符號(hào),將其絕對(duì)值對(duì)p取模后輸出。第八十九頁(yè)，共105頁(yè)。小朋友的數(shù)字(noip2013普及組第三題)輸入格式第一行包含兩個(gè)正整數(shù)n、p,之間用一個(gè)空格隔開(kāi)。

第二行包含n個(gè)數(shù),每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi),表示每個(gè)小朋友手上的數(shù)字。輸出格式輸出只有一行,包含一個(gè)整數(shù),表示最大分?jǐn)?shù)對(duì)p取模的結(jié)果。樣例輸入1599712345樣例輸出121第九十頁(yè)，共105頁(yè)。小朋友的數(shù)字試題分析主要考查選手的語(yǔ)文理解能力，關(guān)鍵把題讀懂。需要理解的兩個(gè)值：特征值：前面連續(xù)若干個(gè)數(shù)字和的最大值；分?jǐn)?shù)：前面每個(gè)小朋友的分?jǐn)?shù)+特征值的最大值第九十一頁(yè)，共105頁(yè)。小朋友的數(shù)字試題分析算法：動(dòng)態(tài)規(guī)劃

+貪心求小朋友的特征值需要求最大子段和。fori=1tondodp[i]=max(dp[i-1]+a[i],a[i]);每個(gè)小朋友的特征值t[i]:fori=1tondo{dp[i]=max(dp[i-1]+a[i],a[i]);

t[i]=max(t[i-1],dp[i]);}第九十二頁(yè)，共105頁(yè)。小朋友的數(shù)字試題分析算法：動(dòng)態(tài)規(guī)劃

+貪心求小朋友的分?jǐn)?shù)需要貪心：如果第一個(gè)小朋友的分?jǐn)?shù)+特征值為負(fù)數(shù)，那么后面所有小朋友的分?jǐn)?shù)=第一個(gè)小朋友的分?jǐn)?shù)+特征值，否則=前一個(gè)小朋友的分?jǐn)?shù)+特征值。fori=2tondoifte[1]+fen[1]<0thenfen[i]=te[1]+fen[1]elsefen[i]=te[i-1]+fen[i-1];第九十三頁(yè)，共105頁(yè)。采藥（noip2005普及組第三題）辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為此，他想拜附近