信息學(xué)奧賽NOIP普及組歷屆試題分析

1、NOIP普及組歷屆試題分析NOIP普及組題型分布普及組題型分布題型題型題目題目枚舉枚舉掃雷游戲掃雷游戲(2015p2)(2015p2)、珠心算測(cè)驗(yàn)、珠心算測(cè)驗(yàn)(2014p1)(2014p1)數(shù)字統(tǒng)計(jì)數(shù)字統(tǒng)計(jì)(2010p1)(2010p1)、比例簡(jiǎn)化、比例簡(jiǎn)化(2014p2)(2014p2)模擬模擬金幣金幣(2015p1)(2015p1)、螺旋方陣螺旋方陣(2014p3)(2014p3)、計(jì)數(shù)問題、計(jì)數(shù)問題(2013p1)(2013p1)、字符串字符串?dāng)?shù)字反轉(zhuǎn)數(shù)字反轉(zhuǎn)(2011p1)(2011p1)、統(tǒng)計(jì)單詞個(gè)數(shù)、統(tǒng)計(jì)單詞個(gè)數(shù)(2011p2)(2011p2)貪心貪心NOIP普及組題型分布普及組題

2、型分布題型題型題目題目簡(jiǎn)單簡(jiǎn)單動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃子矩陣子矩陣(2014p4)(2014p4)、小朋友的數(shù)字、小朋友的數(shù)字(2013p3)(2013p3)數(shù)學(xué)數(shù)學(xué)/ /數(shù)論數(shù)論數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)表達(dá)式求值表達(dá)式求值(2013p2)(2013p2)、圖論圖論（提高組）（提高組）車站分級(jí)車站分級(jí)(2013p4 (2013p4 拓?fù)渑判蛲負(fù)渑判? )一、枚舉類試題一、枚舉類試題n枚舉法的基本思想是根據(jù)提出的問題枚舉所枚舉法的基本思想是根據(jù)提出的問題枚舉所有可能的解，并用問題給定的條件檢驗(yàn)?zāi)男┯锌赡艿慕猓⒂脝栴}給定的條件檢驗(yàn)?zāi)男┙馐切枰?，哪些解是不需要的。能使條件解是需要的，哪些解是不需要的。能使條件成

3、立，即為其解。成立，即為其解。n枚舉法其實(shí)是最簡(jiǎn)單的搜索算法。枚舉法其實(shí)是最簡(jiǎn)單的搜索算法。珠心算測(cè)驗(yàn)珠心算測(cè)驗(yàn) (noip2014普及組第一題普及組第一題)n珠心算是一種通過在腦中模擬算盤變化來完成快珠心算是一種通過在腦中模擬算盤變化來完成快速運(yùn)算的一種計(jì)算技術(shù)。珠心算訓(xùn)練，既能夠開速運(yùn)算的一種計(jì)算技術(shù)。珠心算訓(xùn)練，既能夠開發(fā)智力，又能夠?yàn)槿粘Ｉ顜砗芏啾憷?，因而發(fā)智力，又能夠?yàn)槿粘Ｉ顜砗芏啾憷?，因而在很多學(xué)校得到普及。在很多學(xué)校得到普及。 n某學(xué)校的珠心算老師采用一種快速考察珠心算加某學(xué)校的珠心算老師采用一種快速考察珠心算加法能力的測(cè)驗(yàn)方法。他隨機(jī)生成一個(gè)正整數(shù)集合，法能力的測(cè)驗(yàn)方法

4、。他隨機(jī)生成一個(gè)正整數(shù)集合，集合中的數(shù)各不相同，然后要求學(xué)生回答：其中集合中的數(shù)各不相同，然后要求學(xué)生回答：其中有多少個(gè)數(shù)，恰好等于集合中另外兩個(gè)（不同的）有多少個(gè)數(shù)，恰好等于集合中另外兩個(gè)（不同的）數(shù)之和？數(shù)之和？ 最近老師出了一些測(cè)驗(yàn)題，請(qǐng)你幫忙最近老師出了一些測(cè)驗(yàn)題，請(qǐng)你幫忙求出答案。求出答案。 珠心算測(cè)驗(yàn)珠心算測(cè)驗(yàn) (noip2014普及組第一題普及組第一題)n【輸入輸入】 輸入共兩行，第一行包含一個(gè)整數(shù)輸入共兩行，第一行包含一個(gè)整數(shù)n，表示測(cè)試，表示測(cè)試題中給出的正整數(shù)個(gè)數(shù)。題中給出的正整數(shù)個(gè)數(shù)。 第二行有第二行有n個(gè)正整數(shù)，每?jī)蓚€(gè)正整數(shù)之間用一個(gè)個(gè)正整數(shù)，每?jī)蓚€(gè)正整數(shù)之間用一個(gè)空格

5、隔開，表示測(cè)試題中給出的正整數(shù)。空格隔開，表示測(cè)試題中給出的正整數(shù)。 n【輸出輸出】 輸出共一行，包含一個(gè)整數(shù)，表示測(cè)驗(yàn)題答案。輸出共一行，包含一個(gè)整數(shù)，表示測(cè)驗(yàn)題答案。n【樣例輸入樣例輸入】【樣例輸出樣例輸出】 4 2 1 2 3 4對(duì)于對(duì)于100%的數(shù)據(jù)，的數(shù)據(jù)，3 n 100測(cè)驗(yàn)題給出的正整數(shù)大小不超過測(cè)驗(yàn)題給出的正整數(shù)大小不超過10,000。 試題分析試題分析n題意大意：給你題意大意：給你n個(gè)數(shù)，在這個(gè)數(shù)，在這n個(gè)數(shù)中，找個(gè)數(shù)中，找到滿足到滿足A+B=C的個(gè)數(shù)，的個(gè)數(shù)，注意不是這個(gè)等式注意不是這個(gè)等式的個(gè)數(shù)的個(gè)數(shù)。n樣例中，樣例中，1,2,3,4有有1+2=3，1+3=4兩個(gè)。兩個(gè)。n

6、由于本題數(shù)據(jù)規(guī)模由于本題數(shù)據(jù)規(guī)模n=100，我們可以直接，我們可以直接枚舉枚舉C, A, B，三層循環(huán)解決問題。，三層循環(huán)解決問題。數(shù)字統(tǒng)計(jì)數(shù)字統(tǒng)計(jì) (noip2010普及組第一題普及組第一題) 請(qǐng)統(tǒng)計(jì)某個(gè)給定范圍請(qǐng)統(tǒng)計(jì)某個(gè)給定范圍L, R的所有整數(shù)中，數(shù)字的所有整數(shù)中，數(shù)字2出現(xiàn)出現(xiàn)的次數(shù)。的次數(shù)。 比如在給定范圍比如在給定范圍2, 22，數(shù)字，數(shù)字2在數(shù)在數(shù)2中出現(xiàn)了中出現(xiàn)了1次，在次，在數(shù)數(shù)12中出現(xiàn)了中出現(xiàn)了1次，在數(shù)次，在數(shù)20中出現(xiàn)了中出現(xiàn)了1次，在數(shù)次，在數(shù)21中出中出現(xiàn)了現(xiàn)了1次，在數(shù)次，在數(shù)22中出現(xiàn)了中出現(xiàn)了2次，所以數(shù)字次，所以數(shù)字2在該范圍內(nèi)在該范圍內(nèi)一共出現(xiàn)了一共出現(xiàn)

7、了6次。次。n輸入格式輸入格式 輸入共一行，為兩個(gè)正整數(shù)輸入共一行，為兩個(gè)正整數(shù)L和和R，之間用一個(gè)空格隔，之間用一個(gè)空格隔開。開。n輸出格式輸出格式 輸出共輸出共1行，表示數(shù)字行，表示數(shù)字2出現(xiàn)的次數(shù)。出現(xiàn)的次數(shù)。n樣例輸入：樣例輸入：2 22n樣例輸出：樣例輸出：6掃雷游戲掃雷游戲 (noip2015普及組第二題普及組第二題) 掃雷游戲是一款十分經(jīng)典的單機(jī)小游戲。掃雷游戲是一款十分經(jīng)典的單機(jī)小游戲。 在在 n 行行 m 列的雷區(qū)中有一些格子含有地雷列的雷區(qū)中有一些格子含有地雷（稱之為地雷格）（稱之為地雷格） ，其他格子不含地雷（稱之，其他格子不含地雷（稱之為非地雷格）為非地雷格） 。玩家翻

8、開一個(gè)非地雷格時(shí)，該。玩家翻開一個(gè)非地雷格時(shí)，該格將會(huì)出現(xiàn)一個(gè)數(shù)字格將會(huì)出現(xiàn)一個(gè)數(shù)字提示周圍格子中有多提示周圍格子中有多少個(gè)是地雷格。少個(gè)是地雷格。 游戲的目標(biāo)是在不翻出任何地游戲的目標(biāo)是在不翻出任何地雷格的條件下，找出所有的非地雷格。雷格的條件下，找出所有的非地雷格。 現(xiàn)在給出現(xiàn)在給出n行行m列的雷區(qū)中的地雷分布，列的雷區(qū)中的地雷分布， 要要求計(jì)算出每個(gè)非地雷格周圍的地雷格數(shù)。求計(jì)算出每個(gè)非地雷格周圍的地雷格數(shù)。注：一個(gè)格子的周圍格子包括其上、下、左、注：一個(gè)格子的周圍格子包括其上、下、左、右、左上、右上、左下、右下八個(gè)方向上與之右、左上、右上、左下、右下八個(gè)方向上與之直接相鄰的格子。直接相

9、鄰的格子。 掃雷游戲掃雷游戲 (noip2015普及組第二題普及組第二題) 輸入樣例輸入樣例 13 3*?*? 輸入樣例輸入樣例 22 3?*?*? 輸出樣例輸出樣例 1mine.out*102211*1 輸出樣例輸出樣例 2mine.out2*1*21 對(duì)于對(duì)于 100%的數(shù)據(jù)，的數(shù)據(jù)，1n100，1m100 比例簡(jiǎn)化比例簡(jiǎn)化 (noip2014普及組第二題普及組第二題)n在社交媒體上，經(jīng)常會(huì)看到針對(duì)某一個(gè)觀點(diǎn)同意與在社交媒體上，經(jīng)常會(huì)看到針對(duì)某一個(gè)觀點(diǎn)同意與否的民意調(diào)查以及結(jié)果。例如，對(duì)某否的民意調(diào)查以及結(jié)果。例如，對(duì)某 一觀點(diǎn)表示一觀點(diǎn)表示支持的有支持的有 1498 人，反對(duì)的有人，反對(duì)

10、的有 902 人，那么贊同與人，那么贊同與反對(duì)的比例可以簡(jiǎn)單的記為反對(duì)的比例可以簡(jiǎn)單的記為1498:902。n不過，如果把調(diào)查結(jié)果就以這種方式呈現(xiàn)出來，大不過，如果把調(diào)查結(jié)果就以這種方式呈現(xiàn)出來，大多數(shù)人肯定不會(huì)滿意。因?yàn)檫@個(gè)比例的數(shù)值太大，多數(shù)人肯定不會(huì)滿意。因?yàn)檫@個(gè)比例的數(shù)值太大，難以一眼看出它們的關(guān)系。對(duì)于上面這個(gè)例子，如難以一眼看出它們的關(guān)系。對(duì)于上面這個(gè)例子，如果把比例記為果把比例記為 5:3，雖然與，雖然與 真實(shí)結(jié)果有一定的誤差，真實(shí)結(jié)果有一定的誤差，但依然能夠較為準(zhǔn)確地反映調(diào)查結(jié)果，同時(shí)也顯得但依然能夠較為準(zhǔn)確地反映調(diào)查結(jié)果，同時(shí)也顯得比較直觀。比較直觀。n現(xiàn)給出支持人數(shù)現(xiàn)給出支

11、持人數(shù) A，反對(duì)人數(shù)，反對(duì)人數(shù) B，以及一個(gè)上限，以及一個(gè)上限 L，請(qǐng)你將請(qǐng)你將 A 比比 B 化簡(jiǎn)為化簡(jiǎn)為 A比比 B，要求在，要求在 A和和 B均均不大于不大于 L 且且 A和和 B互質(zhì)（兩個(gè)整數(shù)的最大公約數(shù)互質(zhì)（兩個(gè)整數(shù)的最大公約數(shù)是是 1）的前提下，）的前提下，A/B A/B 且且 A/B - A/B 的值的值盡可能小。盡可能小。 比例簡(jiǎn)化比例簡(jiǎn)化 (noip2014普及組第二題普及組第二題)n輸入格式輸入格式n輸入共一行，包含三個(gè)整數(shù)輸入共一行，包含三個(gè)整數(shù) A，B，L，每?jī)蓚€(gè)整，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開，分別表示支持人數(shù)、反對(duì)數(shù)之間用一個(gè)空格隔開，分別表示支持人數(shù)、反對(duì)人數(shù)以及

12、上限。人數(shù)以及上限。n輸出格式輸出格式n輸出共一行，包含兩個(gè)整數(shù)輸出共一行，包含兩個(gè)整數(shù) A，B，中間用一個(gè)，中間用一個(gè)空格隔開，表示化簡(jiǎn)后的比例?？崭窀糸_，表示化簡(jiǎn)后的比例。n樣例輸入樣例輸入n1498 902 10n樣例輸出樣例輸出n5 3二、模擬類試題二、模擬類試題n有些問題，我們很難建立數(shù)學(xué)模型，或者很難有些問題，我們很難建立數(shù)學(xué)模型，或者很難用計(jì)算機(jī)建立遞推、遞歸、枚舉、回溯法等算用計(jì)算機(jī)建立遞推、遞歸、枚舉、回溯法等算法。在這種情況下，一般采用模擬策略。法。在這種情況下，一般采用模擬策略。n所謂模擬策略就是模擬某個(gè)過程，通過改變數(shù)所謂模擬策略就是模擬某個(gè)過程，通過改變數(shù)學(xué)模型的各種

13、參數(shù)，進(jìn)而觀察變更這些參數(shù)所學(xué)模型的各種參數(shù)，進(jìn)而觀察變更這些參數(shù)所引起過程狀態(tài)的變化，由此展開算法設(shè)計(jì)。引起過程狀態(tài)的變化，由此展開算法設(shè)計(jì)。 金幣金幣 (noip2015普及組第一題普及組第一題)n國(guó)王將金幣作為工資，發(fā)放給忠誠的騎士。第一天，騎士收到一枚金國(guó)王將金幣作為工資，發(fā)放給忠誠的騎士。第一天，騎士收到一枚金幣；之后兩天（第二天和第三天），每天收到兩枚金幣；之后三天幣；之后兩天（第二天和第三天），每天收到兩枚金幣；之后三天（第四、五、六天），每天收到三枚金幣；之后四天（第七、八、九、（第四、五、六天），每天收到三枚金幣；之后四天（第七、八、九、十天），每天收到四枚金幣十天），每天收

14、到四枚金幣；這種工資發(fā)放模式會(huì)一直這樣延續(xù)；這種工資發(fā)放模式會(huì)一直這樣延續(xù)下去：當(dāng)連續(xù)下去：當(dāng)連續(xù)N天每天收到天每天收到N枚金幣后，騎士會(huì)在之后的連續(xù)枚金幣后，騎士會(huì)在之后的連續(xù)N+1天天里，每天收到里，每天收到N+1枚金幣。枚金幣。請(qǐng)計(jì)算在前請(qǐng)計(jì)算在前K天里，騎士一共獲得了多少金幣。天里，騎士一共獲得了多少金幣。n 輸入格式：輸入格式：輸入文件只有輸入文件只有1行，包含一個(gè)正整數(shù)行，包含一個(gè)正整數(shù)K，表示發(fā)放金幣的天數(shù)。，表示發(fā)放金幣的天數(shù)。n輸出格式：輸出格式：輸出文件只有輸出文件只有1行，包含一個(gè)正整數(shù)，即騎士收到的金幣數(shù)。行，包含一個(gè)正整數(shù)，即騎士收到的金幣數(shù)。n輸入輸出樣例輸入輸出樣

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

16、 現(xiàn)給出矩陣大小現(xiàn)給出矩陣大小n以及以及i和和j，請(qǐng)你求出該矩陣中第，請(qǐng)你求出該矩陣中第i行第行第j列的數(shù)是多少。列的數(shù)是多少。n 下圖是一個(gè)下圖是一個(gè)n=4時(shí)的螺旋矩陣。時(shí)的螺旋矩陣。螺旋方陣螺旋方陣 (noip2014普及組第三題普及組第三題)n輸入格式輸入格式n輸入共一行，包含三個(gè)整數(shù)輸入共一行，包含三個(gè)整數(shù) n，i，j，每?jī)蓚€(gè)整數(shù)，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開，分別表示矩陣大小、待求的之間用一個(gè)空格隔開，分別表示矩陣大小、待求的數(shù)所在的行號(hào)和列號(hào)。數(shù)所在的行號(hào)和列號(hào)。n輸出格式輸出格式n輸出共一行，包含一個(gè)整數(shù)，表示相應(yīng)矩陣中第輸出共一行，包含一個(gè)整數(shù)，表示相應(yīng)矩陣中第 i 行第行第

17、j 列的數(shù)。列的數(shù)。n樣例輸入：樣例輸入：4 2 3n 樣例輸出：樣例輸出：14n對(duì)于對(duì)于 50%的數(shù)據(jù)，的數(shù)據(jù)，1 n 100;對(duì)于對(duì)于 100%的數(shù)據(jù)，的數(shù)據(jù)，1 n 30,000，1 i n，1 j n。 螺旋方陣試題分析螺旋方陣試題分析n本題首先讓我們想到傳統(tǒng)的模擬，從本題首先讓我們想到傳統(tǒng)的模擬，從1,1開開始往數(shù)組中填充數(shù)字，但對(duì)于始往數(shù)組中填充數(shù)字，但對(duì)于30000,30000的數(shù)組，直接爆零。的數(shù)組，直接爆零。n對(duì)于讀入的對(duì)于讀入的n, x, y，先判斷，先判斷(x,y)在第幾圈，在第幾圈，再模擬圈內(nèi)的數(shù)字。再模擬圈內(nèi)的數(shù)字。螺旋方陣試題分析螺旋方陣試題分析n如：如：n=4,

18、(2,2)在第在第2圈，圈，(3,1)在第在第1圈。圈。nn=6，(4,5)在第在第2圈圈螺旋方陣試題分析螺旋方陣試題分析n目標(biāo)位置目標(biāo)位置(i,j)到底在當(dāng)前這一圈的第幾個(gè)位置？到底在當(dāng)前這一圈的第幾個(gè)位置？n如目標(biāo)數(shù)如目標(biāo)數(shù)26所在的位置所在的位置(4,5)，在第，在第2圈的什么圈的什么位置？位置？n分兩種情況：分兩種情況：n1）目標(biāo)數(shù)）目標(biāo)數(shù)(i,j)在上行或右行；在上行或右行；n i+j-2q+1n2）目標(biāo)數(shù)）目標(biāo)數(shù)(i,j)在下行或左行；在下行或左行；n 距離第一個(gè)數(shù)的距離距離第一個(gè)數(shù)的距離n i+j-2q+1計(jì)數(shù)問題計(jì)數(shù)問題 (noip2013普及組第一題普及組第一題)n試計(jì)算在區(qū)

19、間試計(jì)算在區(qū)間1到到n的所有整數(shù)中，數(shù)字的所有整數(shù)中，數(shù)字x（0 x9）共出現(xiàn)了多少次？共出現(xiàn)了多少次？例如，在例如，在1到到11中，即在中，即在1、2、3、4、5、6、7、8、9、10、11中，數(shù)字中，數(shù)字1出現(xiàn)了出現(xiàn)了4次。次。n輸入：輸入： 輸入共輸入共1行，包含行，包含2個(gè)整數(shù)個(gè)整數(shù)n、x，之間用一個(gè)空格隔，之間用一個(gè)空格隔開。開。 輸出：輸出： 輸出共輸出共1行，包含一個(gè)整數(shù)，表示行，包含一個(gè)整數(shù)，表示x出現(xiàn)的次數(shù)。出現(xiàn)的次數(shù)。 n輸入示例：輸入示例： 11 1n輸出示例：輸出示例： 4n其他說明：其他說明： 對(duì)于對(duì)于100%的數(shù)據(jù)，的數(shù)據(jù)，1n1,000,000，0 x9。 三、字

20、符串類試題三、字符串類試題n對(duì)于字符串、表達(dá)式的求解、對(duì)于字符串、表達(dá)式的求解、 大整數(shù)的處理大整數(shù)的處理等等，我們經(jīng)常采用字符串來處理。等等，我們經(jīng)常采用字符串來處理。n字符串處理常見函數(shù)：字符串處理常見函數(shù)：數(shù)字反轉(zhuǎn)數(shù)字反轉(zhuǎn) (noip2011普及組第一題普及組第一題)n給定一個(gè)整數(shù)，請(qǐng)將該數(shù)各個(gè)位上數(shù)字反轉(zhuǎn)得到一個(gè)新給定一個(gè)整數(shù)，請(qǐng)將該數(shù)各個(gè)位上數(shù)字反轉(zhuǎn)得到一個(gè)新數(shù)。新數(shù)也應(yīng)滿足整數(shù)的常見形式，即除非給定的原數(shù)數(shù)。新數(shù)也應(yīng)滿足整數(shù)的常見形式，即除非給定的原數(shù)為零，否則反轉(zhuǎn)后得到的新數(shù)的最高位數(shù)字不應(yīng)為零為零，否則反轉(zhuǎn)后得到的新數(shù)的最高位數(shù)字不應(yīng)為零（如：輸入（如：輸入-380，輸出，輸出

21、-83）。）。n輸入輸入 輸入共輸入共1行，一個(gè)整數(shù)行，一個(gè)整數(shù)N。n輸出輸出 輸出共輸出共1行，一個(gè)整數(shù)，表示反轉(zhuǎn)后的新數(shù)。行，一個(gè)整數(shù)，表示反轉(zhuǎn)后的新數(shù)。n樣例輸入樣例輸入 123n樣例輸出樣例輸出 321統(tǒng)計(jì)單詞個(gè)數(shù)統(tǒng)計(jì)單詞個(gè)數(shù) (noip2011普及組第二題普及組第二題)n一般的文本編輯器都有查找單詞的功能，該功一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有能可以快速定位特定單詞在文章中的位置，有的還能統(tǒng)計(jì)出特定單詞在文章中出現(xiàn)的次數(shù)。的還能統(tǒng)計(jì)出特定單詞在文章中出現(xiàn)的次數(shù)。現(xiàn)在，請(qǐng)你編程實(shí)現(xiàn)這一功能，具體要求現(xiàn)在，請(qǐng)你編程實(shí)現(xiàn)這一功能，具體要求是：給

22、定一個(gè)單詞，請(qǐng)你輸出它在給定的文章是：給定一個(gè)單詞，請(qǐng)你輸出它在給定的文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置。注意：匹中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置。注意：匹配單詞時(shí)，不區(qū)分大小寫，但要求完全匹配，配單詞時(shí)，不區(qū)分大小寫，但要求完全匹配，即給定單詞必須與文章中的某一獨(dú)立單詞在不即給定單詞必須與文章中的某一獨(dú)立單詞在不區(qū)分大小寫的情況下完全相同（參見樣例區(qū)分大小寫的情況下完全相同（參見樣例1），），如果給定單詞僅是文章中某一單詞的一部分則如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見樣例不算匹配（參見樣例2）。）。 統(tǒng)計(jì)單詞個(gè)數(shù)統(tǒng)計(jì)單詞個(gè)數(shù) (noip2011普及組第二題普及組第二題)n輸入

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

24、的位置，位置從0開始）；如果單詞在文章中沒有出現(xiàn)，則直接輸出一開始）；如果單詞在文章中沒有出現(xiàn)，則直接輸出一個(gè)整數(shù)個(gè)整數(shù)-1。統(tǒng)計(jì)單詞個(gè)數(shù)統(tǒng)計(jì)單詞個(gè)數(shù) (noip2011普及組第二題普及組第二題)n樣例輸入樣例輸入1： To to be or not to be is a questionn樣例輸出樣例輸出1：2 0n樣例輸入樣例輸入2：to Did the Ottoman Empire lose its power at that time n樣例輸出樣例輸出2：-1【輸入輸出樣例輸入輸出樣例2說明說明】表示給定的單詞表示給定的單詞to在文章中沒有出現(xiàn)，輸出整數(shù)在文章中沒有出現(xiàn)，輸出整數(shù)-1

25、。n注釋說明注釋說明 1單詞長(zhǎng)度單詞長(zhǎng)度10。1文章長(zhǎng)度文章長(zhǎng)度1,000,000。六、簡(jiǎn)單動(dòng)態(tài)規(guī)劃類試題六、簡(jiǎn)單動(dòng)態(tài)規(guī)劃類試題n動(dòng)態(tài)規(guī)劃是解決多階段決策最優(yōu)化問題的一種思想方動(dòng)態(tài)規(guī)劃是解決多階段決策最優(yōu)化問題的一種思想方法。一般我們從初始法。一般我們從初始階段階段出發(fā)，枚舉每個(gè)階段的所有出發(fā)，枚舉每個(gè)階段的所有狀態(tài)狀態(tài)，在狀態(tài)轉(zhuǎn)移的過程中，我們需要，在狀態(tài)轉(zhuǎn)移的過程中，我們需要決策決策。根據(jù)每。根據(jù)每一步所選決策的不同，將隨即引起狀態(tài)的轉(zhuǎn)移，最終一步所選決策的不同，將隨即引起狀態(tài)的轉(zhuǎn)移，最終在變化的狀態(tài)中產(chǎn)生一個(gè)決策序列。動(dòng)態(tài)規(guī)劃就是為在變化的狀態(tài)中產(chǎn)生一個(gè)決策序列。動(dòng)態(tài)規(guī)劃就是為了使產(chǎn)生的

26、決策序列在符合某種條件下達(dá)到最優(yōu)。了使產(chǎn)生的決策序列在符合某種條件下達(dá)到最優(yōu)。n普及組一般考查的動(dòng)態(tài)規(guī)劃：普及組一般考查的動(dòng)態(tài)規(guī)劃：01背包，最長(zhǎng)上升子序背包，最長(zhǎng)上升子序列，一些簡(jiǎn)單的線性動(dòng)規(guī)。列，一些簡(jiǎn)單的線性動(dòng)規(guī)。采藥采藥 （noip2005普及組第三題）普及組第三題）n辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥

27、的山洞里對(duì)他說：藥的山洞里對(duì)他說：“孩子，這個(gè)山洞里有一孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大。的總價(jià)值最大?！?采藥采藥 （noip2005普及組第三題）普及組第三題）n輸入格式：輸入格式：第一行有兩個(gè)整數(shù)第一行有兩個(gè)整數(shù)T和和M，T代表總共能夠用來采藥的時(shí)間，代表總共能夠用來采藥的時(shí)間，M代表山洞里的草藥的數(shù)目。接下來的代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個(gè)在行每行包括兩個(gè)在1到