信息學(xué)排序算法快排noip2011junior

1、普及組普及組（請選手務(wù)必仔細(xì)閱讀本頁內(nèi)容）一題目概況二提交源程序文件名三編譯命令（不包含任何優(yōu)化開關(guān)）四運(yùn)行內(nèi)存限制注意事項(xiàng)：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。2、C/C+中函數(shù) main()的返回值類型必須是，程序正常結(jié)束時(shí)的返回值必須是 0。3、評測時(shí)采用的機(jī)器配置為：CPU P4 3.0GHz，內(nèi)存 1G，上述時(shí)限以此配置為準(zhǔn)。4、特別提醒：評測在 NOI Linux 下進(jìn)行。第 1 頁 共 5 頁內(nèi)存上限128M128M128M128M對于 C+語言g+ -o reverse reverse.cpp -lmg+ -o ss.cpp -lmg+ -o swiss sw

2、iss.cpp -lmg+ -o exp exp.cpp -lm對于 C 語言gcc -o reverse reverse.c -lmgcc -o ss.c -lmgcc -o swiss swiss.c -lmgcc -o exp exp.c -lm對于 pascal 語言fpc reverse.pasfpc s.pasfpc swiss.pasfpc exp.pas對于 C+語言reverse.cpps.cppswiss.cppexp.cpp對于 C 語言reverse.cs.cswiss.cexp.c對于 pascal 語言reverse.pass. passwiss. pasexp.p

3、as中文題目名稱數(shù)字反轉(zhuǎn)統(tǒng)計(jì)單詞數(shù)輪表達(dá)式的值英文題目與子目錄名reversesswissexp可執(zhí)行文件名reversesswissexp輸入文件名reverse.ins.inswiss.inexp.in輸出文件名reverse.outs.outswiss.outexp.out每個(gè)測試點(diǎn)時(shí)限1 秒1 秒1 秒1 秒測試點(diǎn)數(shù)目10101010每個(gè)測試點(diǎn)分值10101010附加樣例文件有有有有結(jié)果比較方式全文比較（過濾行末空格及回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)傳統(tǒng)普及組1數(shù)字反轉(zhuǎn)(reverse.cpp/c/pas)【問題描述】給定一個(gè)整數(shù)，請將該數(shù)各個(gè)位上數(shù)字反轉(zhuǎn)得到一個(gè)新數(shù)。新數(shù)也應(yīng)滿足整數(shù)的常見

4、形式，即除非給定的原數(shù)為零，否則反轉(zhuǎn)后得到的新數(shù)的最數(shù)字不應(yīng)為零（參見樣例 2）?！据斎搿枯斎胛募麨?reverse.in。輸入共 1 行，一個(gè)整數(shù) N?！据敵觥枯敵鑫募麨?reverse.out。輸出共 1 行，一個(gè)整數(shù)，表示反轉(zhuǎn)后的新數(shù)?！据斎胼敵鰳永?1】【輸入輸出樣例 2】【數(shù)據(jù)范圍】-1,000,000,000 N 1,000,000,000。2統(tǒng)計(jì)單詞數(shù)(s.cpp/c/pas)【問題描述】一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有的還能統(tǒng)計(jì)出特定單詞在文章中出現(xiàn)的次數(shù)?，F(xiàn)在，請你編程實(shí)現(xiàn)這能，具體要求是：給定一個(gè)單詞，請你輸出它在給定的文

5、章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置。注意：匹配單詞時(shí)，不區(qū)分大小寫，但要求完全匹配，即給定單詞必須與文章中的某一獨(dú)立單詞在不區(qū)分大小寫的情況下完全相同（參見樣例 1），如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見樣例 2）。【輸入】輸入文件名為 s.in，2 行。第 1 行為一個(gè)字符串，其中只含字母，表示給定單詞；第 2 行為一個(gè)字符串，其中只可能包含字母和空格，表示給定的文章。第 2 頁 共 5 頁Reverse.inreverse.out-380-83reverse.inreverse.out123321普及組【輸出】輸出文件名為 s.out。只有一行，如果在文章中找到給定單詞則輸

6、出兩個(gè)整數(shù)，兩個(gè)整數(shù)之間用一個(gè)空格隔開，分別是單詞在文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置（即在文章中第一次出現(xiàn)時(shí)，單詞首字母在文章中的位置，位置從 0 開始）；如果單詞在文章中沒有出現(xiàn)，則直接輸出一個(gè)整數(shù)-1?！据斎胼敵鰳永?1】【輸入輸出樣例 1 說明】輸出結(jié)果表示給定的單詞 To 在文章中出現(xiàn)兩次，第一次出現(xiàn)的位置為 0?！据斎胼敵鰳永?2】【輸入輸出樣例 2 說明】表示給定的單詞 to 在文章中沒有出現(xiàn)，輸出整數(shù)-1。【數(shù)據(jù)范圍】1 單詞長度 10。1 文章長度 1,000,000。3輪(swiss.cpp/c/pas)【背景】在雙人對決的性比賽，如乒乓球、羽毛球、國際象棋中，最常見的賽制

7、是淘汰賽和循環(huán)賽。前者的特點(diǎn)是比賽場數(shù)少，每場都緊張刺激，但偶然性較高。后者的特點(diǎn)是較為公平，偶然性較低，但比賽過程往往十分冗長。本題中介紹的輪賽制，因最早使用于 1895 年在舉辦的國際象棋比賽而得名。它可以看作是淘汰賽與循環(huán)賽的折衷，既保證了比賽的穩(wěn)定性，又能使賽程不至于過長?！締栴}描述】2*N 名為 12N 的選手共進(jìn)行 R 輪比賽。每輪比賽開始前，以及所有比賽結(jié)束后，都會按照總分從高到低對選手進(jìn)行一次。選手的總分為第一輪開始前的初始分?jǐn)?shù)加上已參加過的所有比賽的得分和?？偡窒嗤?，約定較小的選手靠前。每輪比賽的對陣安排與該輪比賽開始前的有關(guān)：第 1 名和第 2 名、第 3 名和第 4名、

8、第 2K 1 名和第 2K 名、 、第 2N 1 名和第 2N 名，各進(jìn)行一場比賽。每場比賽勝者得 1 分，負(fù)者得 0 分。也就是說除了首輪以外，其它輪比賽的安排均不能事先確定，取決于選手在之前比賽中的表現(xiàn)?，F(xiàn)給定每個(gè)選手的初始分?jǐn)?shù)及其實(shí)力值，試計(jì)算在 R 輪比賽過后，第 Q 的選手編第 3 頁 共 5 頁s.ins.outtoDid the Ottoman Empire lose itser att time-1s.ins.outToto be or not to be is a question2 0普及組號是多少。假設(shè)選手的實(shí)力值兩兩不同，且每場比賽中實(shí)力值較高的總能獲勝。【輸入】輸入文

9、件名為 swiss.in。輸入的第一行是三個(gè)正整數(shù) N、R、Q，每兩個(gè)數(shù)之間用一個(gè)空格隔開，表示有 2*N 名選手、R 輪比賽，以及關(guān)心的名次 Q。第二行是 2*N 個(gè)非負(fù)整數(shù) s1, s2, , s2N，每兩個(gè)數(shù)之間用一個(gè)空格隔開，其中 si 表示編號為 i 的選手的初始分?jǐn)?shù)。第三行是 2*N 個(gè)正整數(shù) w1, w2, , w2N，每兩個(gè)數(shù)之間用一個(gè)空格隔開，其中 wi 表示編號為 i 的選手的實(shí)力值?！据敵觥枯敵鑫募麨?swiss.out。輸出只有一行，包含一個(gè)整數(shù)，即 R 輪比賽結(jié)束后，第 Q 的選手的?！据斎胼敵鰳永俊据斎胼敵鰳永f明】【數(shù)據(jù)范圍】對于 30%的數(shù)據(jù)，1 N 100

10、； 對于 50%的數(shù)據(jù)，1 N 10,000；對于 100%的數(shù)據(jù)，1 N 100,000，1 R 50，1 Q 2N，0 s1, s2, , s2N 108，1 w1, w2, , w2N 108。4表達(dá)式的值(exp.cpp/c/pas)【問題描述】對于 1 位二進(jìn)制變量定義兩種運(yùn)算：第 4 頁 共 5 頁本輪對陣本輪結(jié)束后的得分選手/初始/7667第 1 輪7678第 2 輪7689第 3 輪8699第 4 輪96109swiss.inswiss.out2 4 27 6 6 710 5 20 151普及組運(yùn)算的優(yōu)先級是：先計(jì)算括號內(nèi)的，再計(jì)算括號外的。“”運(yùn)算優(yōu)先于“”運(yùn)算，即計(jì)算表達(dá)式

11、時(shí)，先計(jì)算運(yùn)算，再計(jì)算運(yùn)算。例如：計(jì)算表達(dá)式 AB C 時(shí)，先計(jì)算 B C，其結(jié)果再與 A 做運(yùn)算?，F(xiàn)給定一個(gè)未完成的表達(dá)式，例如_+(_*_)，請你在橫線處填入數(shù)字 0 或者 1，請問有多少種填法可以使得表達(dá)式的值為 0?！据斎搿枯斎胛募麨?exp.in，共 2 行。第 1 行為一個(gè)整數(shù) L，表示給定的表達(dá)式中除去橫線外的運(yùn)算符和括號的個(gè)數(shù)。第 2 行為一個(gè)字符串包含 L 個(gè)字符，其中只包含（、）、+、*這 4 種字符，其中（、）是左右括號，+、*分別表示前面定義的運(yùn)算符“”和“”。這行字符按順序給出了給定表達(dá)式中除去變量外的運(yùn)算符和括號?！据敵觥枯敵鑫募?exp.out 共 1 行。包含一個(gè)整數(shù)，即所有的方案數(shù)。注意：這個(gè)數(shù)可能會很大，請輸出方案數(shù)對 10007 取模后的結(jié)果?！据斎胼敵鰳永?1】【輸入輸出樣例說明】給定的表達(dá)式包括橫線字符之后為：_+(_*_)在橫線位置填入(0、0、0)、(0、1、0)、(0、0、1)時(shí)，表達(dá)式的值均為種填法。【數(shù)據(jù)范圍】對于 20%的