資源簡介

全國信息學奧林匹克聯(lián)賽（NOIP2008）復賽
提高組
一、題目概覽
中文題目名稱 笨小猴 火柴棒等式 傳紙條 雙棧排序
英文題目名稱 word matches message twostack
可執(zhí)行文件名 word matches message twostack
輸入文件名 word,in matches.in message.in twostack.in
輸出文件名 word.out matches.out message.out twostack.out
每個測試點時限 1秒 1秒 1秒 1秒
測試點數(shù)目 10 10 10 10
每個測試點分值 10 10 10 10
比較方式 全文比較 全文比較 全文比較 全文比較
題目類型 傳統(tǒng) 傳統(tǒng) 傳統(tǒng) 傳統(tǒng)
二、提交源程序文件名
對于Pascal語言 word.pas matches.pas message.pas twostack.pas
對于C語言 word.c matches.c message.c twostack.c
對于C++語言 word.cpp matches.cpp message.cpp twostack.cpp
三、編譯命令（不包含任何優(yōu)化開關）
對于Pascal語言 fpc word.pas fpc matches.pas fpc message.pas fpc twostack.pas
對于C語言 gcc –o word word.c gcc –o matches matches.c gcc –o message message.c gcc –o twostack twostack.c
對于C++語言 g++ -o word word.cpp g++-o matches matches.cpp g++ -o message message.cpp g++ -o twostack twostack.cpp
四、運行內存限制
運行內存上限 50M 50M 50M 50M
注意事項：
1. 文件名（程序名和輸入輸出文件名）必須使用大寫。
2. C/C++中函數(shù)main()的返回值類型必須是int，程序正常結束時的返回值必須是0。
3. 全國統(tǒng)一評測時采用的機器配置為：CPU 1.9GHz，內存512M，上述時限以此配置為準。各省在自測時可根據(jù)具體配置調整時限。
1. 笨小猴
(word.pas/c/cpp)
【問題描述】
笨小猴的詞匯量很小，所以每次做英語選擇題的時候都很頭疼。但是他找到了一種方法，經試驗證明，用這種方法去選擇選項的時候選對的幾率非常大！
這種方法的具體描述如下：假設maxn是單詞中出現(xiàn)次數(shù)最多的字母的出現(xiàn)次數(shù)，minn是單詞中出現(xiàn)次數(shù)最少的字母的出現(xiàn)次數(shù)，如果maxn-minn是一個質數(shù)，那么笨小猴就認為這是個Lucky Word，這樣的單詞很可能就是正確的答案。
【輸入】
輸入文件word.in只有一行，是一個單詞，其中只可能出現(xiàn)小寫字母，并且長度小于100。
【輸出】
輸出文件word.out共兩行，第一行是一個字符串，假設輸入的的單詞是Lucky Word，那么輸出“Lucky Word”，否則輸出“No Answer”；
第二行是一個整數(shù)，如果輸入單詞是Lucky Word，輸出maxn-minn的值，否則輸出0。
【輸入輸出樣例1】
word.in word.out
error Lucky Word2
【輸入輸出樣例1解釋】
單詞error中出現(xiàn)最多的字母r出現(xiàn)了3次，出現(xiàn)次數(shù)最少的字母出現(xiàn)了1次，3-1=2，2是質數(shù)。
【輸入輸出樣例2】
word.in word.out
Olympic No Answer0
【輸入輸出樣例2解釋】
單詞olympic中出現(xiàn)最多的字母i出現(xiàn)了2次，出現(xiàn)次數(shù)最少的字母出現(xiàn)了1次，2-1=1，1不是質數(shù)。
2. 火柴棒等式
(matches.pas/c/cpp)
【問題描述】
給你n根火柴棍，你可以拼出多少個形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整數(shù)（若該數(shù)非零，則最高位不能是0）。用火柴棍拼數(shù)字0-9的拼法如圖所示：
注意：
1. 加號與等號各自需要兩根火柴棍
2. 如果A≠B，則A+B=C與B+A=C視為不同的等式（A、B、C>=0）
3. n根火柴棍必須全部用上
【輸入】
輸入文件matches.in共一行，又一個整數(shù)n（n<=24）。
【輸出】
輸出文件matches.out共一行，表示能拼成的不同等式的數(shù)目。
【輸入輸出樣例1】
matches.in matches.out
14 2
【輸入輸出樣例1解釋】
2個等式為0+1=1和1+0=1。
【輸入輸出樣例2】
matches.in matches.out
18 9
【輸入輸出樣例2解釋】
9個等式為：
0+4=4
0+11=11
1+10=11
2+2=4
2+7=9
4+0=4
7+2=9
10+1=11
11+0=11
3. 傳紙條
(wassage.pas/c/cpp)
【問題描述】
小淵和小軒是好朋友也是同班同學，他們在一起總有談不完的話題。一次素質拓展活動中，班上同學安排做成一個m行n列的矩陣，而小淵和小軒被安排在矩陣對角線的兩端，因此，他們就無法直接交談了。幸運的是，他們可以通過傳紙條來進行交流。紙條要經由許多同學傳到對方手里，小淵坐在矩陣的左上角，坐標(1,1)，小軒坐在矩陣的右下角，坐標(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。
在活動進行中，小淵希望給小軒傳遞一張紙條，同時希望小軒給他回復。班里每個同學都可以幫他們傳遞，但只會幫他們一次，也就是說如果此人在小淵遞給小軒紙條的時候幫忙，那么在小軒遞給小淵的時候就不會再幫忙。反之亦然。
還有一件事情需要注意，全班每個同學愿意幫忙的好感度有高有低（注意：小淵和小軒的好心程度沒有定義，輸入時用0表示），可以用一個0-100的自然數(shù)來表示，數(shù)越大表示越好心。小淵和小軒希望盡可能找好心程度高的同學來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學的好心程度只和最大。現(xiàn)在，請你幫助小淵和小軒找到這樣的兩條路徑。
【輸入】
輸入文件message.in的第一行有2個用空格隔開的整數(shù)m和n，表示班里有m行n列（1<=m,n<=50）。
接下來的m行是一個m*n的矩陣，矩陣中第i行j列的整數(shù)表示坐在第i行j列的學生的好心程度。每行的n個整數(shù)之間用空格隔開。
【輸出】
輸出文件message.out共一行，包含一個整數(shù)，表示來回兩條路上參與傳遞紙條的學生的好心程度之和的最大值。
【輸入輸出樣例】
message.in message.out
3 30 3 92 8 55 7 0 34
【限制】
30%的數(shù)據(jù)滿足：1<=m,n<=10
100%的數(shù)據(jù)滿足：1<=m,n<=50
4. 雙棧排序
(twostack.pas/c/cpp)
【問題描述】
Tom最近在研究一個有趣的排序問題。如圖所示，通過2個棧S1和S2，Tom希望借助以下4種操作實現(xiàn)將輸入序列升序排序。
操作a
如果輸入序列不為空，將第一個元素壓入棧S1
操作b
如果棧S1不為空，將S1棧頂元素彈出至輸出序列
操作c
如果輸入序列不為空，將第一個元素壓入棧S2
操作d
如果棧S2不為空，將S2棧頂元素彈出至輸出序列
如果一個1~n的排列P可以通過一系列操作使得輸出序列為1，2，…，(n-1)，n，Tom就稱P是一個“可雙棧排序排列”。例如(1,3,2,4)就是一個“可雙棧排序序列”，而(2,3,4,1)不是。下圖描述了一個將(1,3,2,4)排序的操作序列：
當然，這樣的操作序列有可能有幾個，對于上例(1,3,2,4)，是另外一個可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。
【輸入】
輸入文件twostack.in的第一行是一個整數(shù)n。
第二行有n個用空格隔開的正整數(shù)，構成一個1~n的排列。
【輸出】
輸出文件twostack.out共一行，如果輸入的排列不是“可雙棧排序排列”，輸出數(shù)字0；否則輸出字典序最小的操作序列，每兩個操作之間用空格隔開，行尾沒有空格。
【輸入輸出樣例1】
twostack.in twostack.out
41 3 2 4 a b a a b b a b
【輸入輸出樣例2】
twostack.in twostack.out
42 3 4 1 0
【輸入輸出樣例3】
twostack.in twostack.out
32 3 1 a c a b b d
【限制】
30%的數(shù)據(jù)滿足： n<=10
50%的數(shù)據(jù)滿足： n<=50
100%的數(shù)據(jù)滿足： n<=1000

展開更多......

收起↑