資源簡介

全國信息學奧林匹克聯賽（NOIP2011）復賽 普及組
全國信息學奧林匹克聯賽（NOIP2011）復賽
普及組
（請選手務必仔細閱讀本頁內容）
一．題目概況
中文題目名稱 數字反轉 統計單詞數 瑞士輪 表達式的值
英文題目與子目錄名 reverse stat swiss exp
可執行文件名 reverse stat swiss exp
輸入文件名 reverse.in stat.in swiss.in exp.in
輸出文件名 reverse.out stat.out swiss.out exp.out
每個測試點時限 1 秒 1 秒 1 秒 1 秒
測試點數目 10 10 10 10
每個測試點分值 10 10 10 10
附加樣例文件 有 有 有 有
結果比較方式 全文比較（過濾行末空格及文末回車）
題目類型 傳統 傳統 傳統 傳統
二．提交源程序文件名
對于 C++語言 reverse.cpp stat.cpp swiss.cpp exp.cpp
對于 C 語言 reverse.c stat.c swiss.c exp.c
對于 pascal 語言 reverse.pas stat. pas swiss. pas exp.pas
三．編譯命令（不包含任何優化開關）
對于 C++語言 g++ -o reverse g++ -o stat g++ -o swiss g++ -o exp
reverse.cpp -lm stat.cpp -lm swiss.cpp -lm exp.cpp -lm
對于 C 語言 gcc -o reverse gcc -o stat gcc -o swiss gcc -o exp exp.c -lm
reverse.c -lm stat.c -lm swiss.c -lm
對于 pascal 語言 fpc reverse.pas fpc stat.pas fpc swiss.pas fpc exp.pas
四．運行內存限制
內存上限 128M 128M 128M 128M
注意事項：
1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。
2、C/C++中函數 main()的返回值類型必須是 int，程序正常結束時的返回值必須是 0。
3、全國統一評測時采用的機器配置為：CPU P4 3.0GHz，內存 1G，上述時限以此配置為準。
4、特別提醒：評測在 NOI Linux 下進行。
第 1 頁 共 5 頁
全國信息學奧林匹克聯賽（NOIP2011）復賽 普及組
1．數字反轉
(reverse.cpp/c/pas)
【問題描述】
給定一個整數，請將該數各個位上數字反轉得到一個新數。新數也應滿足整數的常見形
式，即除非給定的原數為零，否則反轉后得到的新數的最高位數字不應為零（參見樣例 2）。
【輸入】
輸入文件名為 reverse.in。
輸入共 1 行，一個整數 N。
【輸出】
輸出文件名為 reverse.out。
輸出共 1 行，一個整數，表示反轉后的新數。
【輸入輸出樣例 1】
reverse.in reverse.out
123 321
【輸入輸出樣例 2】
Reverse.in reverse.out
-380 -83
【數據范圍】
-1,000,000,000≤ N≤ 1,000,000,000。
2．統計單詞數
(stat.cpp/c/pas)
【問題描述】
一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位
置，有的還能統計出特定單詞在文章中出現的次數。
現在，請你編程實現這一功能，具體要求是：給定一個單詞，請你輸出它在給定的文章
中出現的次數和第一次出現的位置。注意：匹配單詞時，不區分大小寫，但要求完全匹配，
即給定單詞必須與文章中的某一獨立單詞在不區分大小寫的情況下完全相同（參見樣例 1），
如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見樣例 2）。
【輸入】
輸入文件名為 stat.in，2 行。
第 1 行為一個字符串，其中只含字母，表示給定單詞；
第 2 行為一個字符串，其中只可能包含字母和空格，表示給定的文章。
第 2 頁 共 5 頁
全國信息學奧林匹克聯賽（NOIP2011）復賽 普及組
【輸出】
輸出文件名為 stat.out。
只有一行，如果在文章中找到給定單詞則輸出兩個整數，兩個整數之間用一個空格隔開，
分別是單詞在文章中出現的次數和第一次出現的位置（即在文章中第一次出現時，單詞首字
母在文章中的位置，位置從 0 開始）；如果單詞在文章中沒有出現，則直接輸出一個整數-1。
【輸入輸出樣例 1】
stat.in stat.out
To 2 0
to be or not to be is a question
【輸入輸出樣例 1 說明】
輸出結果表示給定的單詞 To在文章中出現兩次，第一次出現的位置為 0。
【輸入輸出樣例 2】
stat.in stat.out
to -1
Did the Ottoman Empire lose its power at that time
【輸入輸出樣例 2 說明】
表示給定的單詞 to 在文章中沒有出現，輸出整數-1。
【數據范圍】
1≤單詞長度≤ 10。
1≤文章長度≤ 1,000,000。
3．瑞士輪
(swiss.cpp/c/pas)
【背景】
在雙人對決的競技性比賽，如乒乓球、羽毛球、國際象棋中，最常見的賽制是淘汰賽和
循環賽。前者的特點是比賽場數少，每場都緊張刺激，但偶然性較高。后者的特點是較為公
平，偶然性較低，但比賽過程往往十分冗長。
本題中介紹的瑞士輪賽制，因最早使用于 1895 年在瑞士舉辦的國際象棋比賽而得名。
它可以看作是淘汰賽與循環賽的折衷，既保證了比賽的穩定性，又能使賽程不至于過長。
【問題描述】
2*N 名編號為 1~2N 的選手共進行 R 輪比賽。每輪比賽開始前，以及所有比賽結束后，
都會按照總分從高到低對選手進行一次排名。選手的總分為第一輪開始前的初始分數加上已
參加過的所有比賽的得分和。總分相同的，約定編號較小的選手排名靠前。
每輪比賽的對陣安排與該輪比賽開始前的排名有關：第 1 名和第 2 名、第 3 名和第 4
名、……、第 2K – 1 名和第 2K 名、…… 、第 2N – 1 名和第 2N 名，各進行一場比賽。每
場比賽勝者得 1 分，負者得 0 分。也就是說除了首輪以外，其它輪比賽的安排均不能事先確
定，而是要取決于選手在之前比賽中的表現。
現給定每個選手的初始分數及其實力值，試計算在 R 輪比賽過后，排名第 Q 的選手編
第 3 頁 共 5 頁
全國信息學奧林匹克聯賽（NOIP2011）復賽 普及組
號是多少。我們假設選手的實力值兩兩不同，且每場比賽中實力值較高的總能獲勝。
【輸入】
輸入文件名為 swiss.in。
輸入的第一行是三個正整數 N、R、Q，每兩個數之間用一個空格隔開，表示有 2*N 名
選手、R 輪比賽，以及我們關心的名次 Q。
第二行是 2*N 個非負整數 s1, s2, …, s2N，每兩個數之間用一個空格隔開，其中 si 表示編
號為 i 的選手的初始分數。
第三行是 2*N 個正整數 w1, w2, …, w2N，每兩個數之間用一個空格隔開，其中 wi 表示編
號為 i 的選手的實力值。
【輸出】
輸出文件名為 swiss.out。
輸出只有一行，包含一個整數，即 R 輪比賽結束后，排名第 Q 的選手的編號。
【輸入輸出樣例】
swiss.in swiss.out
2 4 2 1
7 6 6 7
10 5 20 15
【輸入輸出樣例說明】
本輪對陣 本輪結束后的得分
選手編號 / ① ② ③ ④
初始 / 7 6 6 7
第 1 輪 ①—④ ②—③ 7 6 7 8
第 2 輪 ④—① ③—② 7 6 8 9
第 3 輪 ④—③ ①—② 8 6 9 9
第 4 輪 ③—④ ①—② 9 6 10 9
【數據范圍】
對于 30%的數據，1≤N≤ 100；
對于 50%的數據，1≤N≤ 10,000；
對于 100%的數據，1≤N≤ 100,000，1≤ R≤ 50，1≤Q≤ 2N，0≤ s1, s2, …, s 82N≤ 10 ，1≤w1,
w2, …, w2N≤ 108。
4．表達式的值
(exp.cpp/c/pas)
【問題描述】
對于 1 位二進制變量定義兩種運算：
第 4 頁 共 5 頁
全國信息學奧林匹克聯賽（NOIP2011）復賽 普及組
運算符 運算規則
0 0=0
0 1=1

1 0=1
1 1=1
0 × 0=0
0 × 1=0
×
1 × 0=0
1 × 1=1
運算的優先級是：
1. 先計算括號內的，再計算括號外的。
2. “×”運算優先于“ ”運算，即計算表達式時，先計算×運算，再計算 運算。
例如：計算表達式 A B × C 時，先計算 B × C，其結果再與 A 做 運算。
現給定一個未完成的表達式，例如_+(_*_)，請你在橫線處填入數字 0 或者 1，請問
有多少種填法可以使得表達式的值為 0。
【輸入】
輸入文件名為 exp.in，共 2 行。
第 1 行為一個整數 L，表示給定的表達式中除去橫線外的運算符和括號的個數。
第 2 行為一個字符串包含 L 個字符，其中只包含’（’、’）’、’+’、’*’這 4 種字符，其中’
（’、’）’是左右括號，’+’、’*’分別表示前面定義的運算符“ ”和“×”。這行字符按順序
給出了給定表達式中除去變量外的運算符和括號。
【輸出】
輸出文件 exp.out 共 1 行。包含一個整數，即所有的方案數。注意：這個數可能會很大，
請輸出方案數對 10007 取模后的結果。
【輸入輸出樣例 1】
exp.in exp.out
4 3
+(*)
【輸入輸出樣例說明】
給定的表達式包括橫線字符之后為：_+(_*_)
在橫線位置填入(0、0、0)、(0、1、0)、(0、0、1)時，表達式的值均為 0，所以共有 3
種填法。
【數據范圍】
對于 20%的數據有 0≤L≤ 10。
對于 50%的數據有 0≤L≤ 1,000。
對于 70%的數據有 0≤L≤ 10,000。
對于 100%的數據有 0≤L≤ 100,000。
對于 50%的數據輸入表達式中不含括號。
第 5 頁 共 5 頁

展開更多......

收起↑