信息學(xué)競賽測試題練習(xí)版

1、鄭州市第一0一中學(xué)信息學(xué)奧賽班第N次測試、題目概況中文題目名稱Vigenere 密碼聰明的質(zhì)檢員mayan 游戲英文題目與子目錄名vigenereqcmayan可執(zhí)行文件名vigenereqcmayan輸入文件名vigenere.inqc.inmayan.in輸出文件名vigenere.outqc.outmayan.out每個測試點(diǎn)時限1 秒1 秒3 秒測試點(diǎn)數(shù)目102010每個測試點(diǎn)分值10510附加樣例文件有有有結(jié)果比較方式全文比較（過濾行末空格及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)運(yùn)行內(nèi)存上限128M128M128M、提交源程序文件名對于 C+詡言vigenere.cppqc.cppmayan

2、.cpp三、編譯命令（不包含任何優(yōu)化開關(guān)）g+-ovigenereg+-oqcvigenere.cpp-Imqc.cpp-Im注意事項(xiàng)：1 .文件名（程序名和輸入輸出文件名）必須使用英文小寫。2.C/C+中函數(shù) main（）的返回值類型必須是 int,程序正常結(jié)束時的返回值必須是 0。3.全國統(tǒng)一評測時采用的機(jī)器配置為：CPUAMDAthlon（tm）64x2DualCoreCPU5200+4.71GHz,內(nèi)存 2G,上述時限以此配置為準(zhǔn)。5.只提供 Linux 格式附加樣例文件。6.特別提醒：評測在 NOILinux 下進(jìn)行。g+-omayanmayan.cpp-Im對于 C+詡言1.Vig

3、en不e金碼(vigenere.cpp)【問題描述】16 世紀(jì)法國外交家 BlaisedeVigen6re 設(shè)計(jì)了一種多表密碼加密算法 Vigen6re 密碼。Vigenere 密碼的加密解密算法簡單易用，且破譯難度比較高，曾在美國南北戰(zhàn)爭中為南軍所廣泛使用。在密碼學(xué)中，我們稱需要加密的信息為明文，用 M 表示；稱加密后的信息為密文，用 C 表示；而密鑰是一種參數(shù)，是將明文轉(zhuǎn)換為密文或?qū)⒚芪霓D(zhuǎn)換為明文的算法中輸入的數(shù)據(jù)， 記為 k。 在 Vigen6re 密碼中， 密鑰 k 是一個字母串， k=k1k2kn。當(dāng)明文 M=rmr mi 時，得到的密文 C=oc2-cn,其中 ci=m?ki,運(yùn)算

4、？的規(guī)則如下表所示：BCDEFGHIjKIMNOPQRSTUVWXYZBCDEFGHIjKIMNOPQRSTUVWXYZVigenere 加密在操作時需要注意：1.?運(yùn)算忽略參與運(yùn)算的字母的大小寫，并保持字母在明文 M 中的大小寫形式;2.當(dāng)明文 M 的長度大于密鑰 k 的長度時，將密鑰 k 重復(fù)使用。例如，明文 M=Helloworld,密鑰 k=abc 時，密文 C=Hfnlpyosnd。明文H He e1 11 1aw wQr r1 1d d客釗a abca abC Ca abC Ca a密文H Hfn1 1PyQsnd d| |ZABYzAZABYzAXYzwXYXYzwXYVwXuV

5、wVwXuVwTUVSTUTUVSTURsTQRsRsTQRspQRopQpQRopQNopMNoNopMNoIMNKLMIMNKLMJKLJKLcDEFBcDEAcDEFBcDEABcDzABcBcDzABc z zABXYzAwXABXYzAwX zVwXYuVwXzVwXYuVwXTuVwsTuVRTuVwsTuVRsTuQR5TPOsTuQR5TPORSoRSop pQRQRN NopopoMNopLMNooMNopLMNoKLMNJKIMIKLMNJKIMIJKLHIJKGHJKLHIJKGHIJFGHIIJFGHIEFEFG GH HDEFGDEFGFGHIEFGHDFGHIEFG

6、HDE EF FGcDEFBcGcDEFBcDEADEAB BcDzAecDzAecYzABXYzAcYzABXYzAwXYzVwXYuwXYzVwXYuVwXTuVwsTVwXTuVwsTuVRsTuQftuVRsTuQftsTpQRsoposTpQRsopoR RN No op pQMNopQMNopLMLMN NoKLMN)oKLMN)KLMIJKLKLMIJKLH HI IJKJKDEFGHIJKKIMNJKIM4KIMNJKIM4JKLHI)KGHJKLHI)KGHI1FGHIEFGI1FGHIEFGHDEFGcDEFHDEFGcDEFBcDBcD ABcDzABcDzABcABcY

7、zAYzAXYzXYzwXYwXYVwXVwXuVwuVwTUVTUVSTUSTUB BA Az zY YR RsTuQRsTpsTuQRsTpQRsopQRNoQRsopQRNop p。M MN NopLMNoLopLMNoLMNoMNoH HG GF FE ED Dc cB BA Az zY YX Xw wV Vu uT Ts sR RQ Qp ppVwXYuVwXTVwXYuVwXTuVwsTuVRsuVwsTuVRsTuQRsTPORTuQRsTPORSopQRNopQSopQRNopQMNopLMNoKMNopLMNoKIMNJKLMIJIMNJKLMIJKLHIIKGHFKLHII

8、KGHFGHIEFGHDEGHIEFGHDEFGcDEF6cDFGcDEF6cDEABcozABcEABcozABcYzABXYzAwYzABXYzAwXYzwXYzXYzwXYzN NLMNOPQRspQRQRspQRopQNopopQNopMNoMNoFGHWXATU UFGHIB輸入文件名為 vigenere.in。輸入共 2 行。第一行為一個字符串，表示密鑰 k,長度不超過 100,其中僅包含大小寫字母。第二行為一個字符串，表示經(jīng)加密后的密文，長度不超過 1000,其中僅包含大小寫字母?！据敵觥俊据敵觥枯敵鑫募麨?vigenere.out。輸出共 1 行，一個字符串，表示輸入密鑰和密

9、文所對應(yīng)的明文?！据敗据斎胼敵鰳永縱igenere.out【數(shù)據(jù)說明】對于 100%勺數(shù)據(jù)，輸入的密鑰的長度不超過 100,輸入的密文的長度不超過 1000,且都僅包含英文字母。2.聰明的質(zhì)監(jiān)員(qc.cpp)【問題描述】小 T 是一名質(zhì)量監(jiān)督員，最近負(fù)責(zé)檢驗(yàn)一批礦產(chǎn)的質(zhì)量。這批礦產(chǎn)共有 n 個礦石，從 1 到n 逐一編號，每個礦石都有自己的重量 wi以及價值 v%檢驗(yàn)礦產(chǎn)的流程是：1 .給定 m 個區(qū)間Li,R;2.選出一個參數(shù) W;3.對于一個區(qū)間Li,R,計(jì)算礦石在這個區(qū)間上的檢驗(yàn)值 Y Yi:凡旦嗎Wrj是礦石編號這批礦產(chǎn)的檢驗(yàn) Z果 Y 為各個區(qū)間的檢驗(yàn)值之和。即：F=1若這批礦產(chǎn)

10、的檢驗(yàn)結(jié)果與所給標(biāo)準(zhǔn)值 S 相差太多，就需要再去檢驗(yàn)另一批礦產(chǎn)。小環(huán)想費(fèi)時間去檢驗(yàn)另一批礦產(chǎn)，所以他想通過調(diào)整參數(shù) W 的值，讓檢驗(yàn)結(jié)果盡可能的靠近標(biāo)準(zhǔn)彳 1S,即使得 S-Y 的絕對值最小。請你幫忙求出這個最小值?！据斎搿枯斎胛募?qc.in。第一行包含三個整數(shù) n,m,S,分別表示礦石的個數(shù)、區(qū)間的個數(shù)和標(biāo)準(zhǔn)值。接下來的 n 行，每行 2 個整數(shù)，中間用空格隔開，第 i+1 行表示 i 號礦石白重量 wi 和價值 vi。接下來的 m 行，表示區(qū)間，每行 2 個整數(shù)，中間用空格隔開，第 i+n+1 行表示區(qū)間Li,Ri的兩個端點(diǎn) Li 和 Ri。注意：不同區(qū)間可能重合或相互重疊。【輸出】vi

11、genere.inCompleteVictoryYvqgpxaimmklongnzfwpvxmniytmWherethereisawillthereisaway輸出文件名為 qc.out。輸出只有一行，包含一個整數(shù)，表示所求的最小值?！据斎胼敵鰳永縬c.inqc.out5315101525354555152433【輸入輸出樣例說明】當(dāng) W 選 4 的時候，三個區(qū)間上檢驗(yàn)值分別為 20、5、0,這批礦產(chǎn)的檢驗(yàn)結(jié)果為 25,此時與標(biāo)準(zhǔn)值 S 相差最小為 10?！緮?shù)據(jù)范圍】對于 10%的數(shù)據(jù)，有 iwn,mwi0；對于 30%的數(shù)據(jù)，有 iwn,mW500;對于 50%的數(shù)據(jù)，有 iwn,m5,0

12、00;對于 70%的數(shù)據(jù)，有 iwn,mw10,000；對于 i00%的數(shù)據(jù)，有 iwn,m200,000,0w,vwi06,0Si0i2,iwLWRWn。3 .Mayan游戲（mayan.cpp）【問題描述】Mayanpuzzle 是最近流行起來的一個游又游戲界面是一個 7 行 5 列的棋盤，上面堆放著一些方塊，方塊不能懸空堆放，即方塊必須放在最下面一行，或者放在其他方塊之上。游戲通關(guān)是指在規(guī)定的步數(shù)內(nèi)消除所有的方塊，消除方塊的規(guī)則如下：1 .每步移動可以且僅可以沿橫向（即向左或向右）拖動某一方塊一格：當(dāng)拖動這一方塊時，如果拖動后到達(dá)的位置（以下稱目標(biāo)位置）也有方塊，那么這兩個方塊將交換位置

13、（參見輸入輸出樣例說明中的圖 6 到圖 7）;如果目標(biāo)位置上沒有方塊，那么被拖動的方塊將從原來的豎列中抽出，并從目標(biāo)位置上掉落（直到不懸空，參見下面圖 1 和圖 2）;2.任一時刻，如果在一橫行或者豎列上有連續(xù)三個或者三個以上相同顏色的方塊，則它們將立即被消除（參見圖 1 到圖 3）。注意：a）如果同時有多組方塊滿足消除條件，幾組方塊會同時被消除（例如下面圖 4,三個顏色為 1 的方塊和三個顏色為 2 的方塊會同時被消除，最后剩下一個顏色為 2 的方塊）。b）當(dāng)出現(xiàn)行和列都滿足消除條件且行列共享某個方塊時，行和列上滿足消除條件的所有方塊會被同時消除（例如下面圖 5 所示的情形，5 個方塊會同時

14、被消除）。圖53.方塊消除之后，消除位置之上的方塊將掉落，掉落后可能會引起新的方塊消除。注意：掉落的過程中將不會有方塊的消除。上面圖 1 到圖 3 給出了在棋盤上移動一塊方塊之后棋盤的變化。棋盤的左下角方塊的坐標(biāo)圖圖1圖圖2圖圖3為（0,0）,將位于（3,3）的方塊向左移動之后，游戲界面從圖 1 變成圖 2 所示的狀態(tài)，此時在一豎列上有連續(xù)三塊顏色為 4 的方塊，滿足消除條件，消除連續(xù) 3 塊顏色為 4 的方塊后，上方的顏色為 3 的方塊掉落，形成圖 3 所示的局面?！据斎搿枯斎胛募?mayan.in,共 6 行。第一行為一個正整數(shù) n,表示要求游戲通關(guān)的步數(shù)。接下來的 5 行，描述 7*5

15、的游戲界面。每行若干個整數(shù)，每兩個整數(shù)之間用一個空格隔開，每行以一個 0 結(jié)束，自下向上表示每豎列方塊的顏色編號（顏色不多于 10 種，從 1 開始順序編號，相同數(shù)字表示相同顏色）。輸入數(shù)據(jù)保證初始棋盤中沒有可以消除的方塊?！据敵觥俊据敵觥枯敵鑫募麨?mayan.outo如果有解決方案，輸出 n 行，每行包含 3 個整數(shù) x,y,g,表示一次移動，每兩個整數(shù)之間用一個空格隔開，其中（x,y）表示要移動的方塊的坐標(biāo)，g 表示移動的方向，1 表示向右移動，-1 表示向左移動。注意：多組解時，按照 x x 為第一關(guān)健字，y y 為第二關(guān)健字，1 1 優(yōu)先于-1,-1,給出一組字典序最小的解。游戲界面左下角的坐標(biāo)為（0,00,0）。如果沒有解決方案，輸出一行，包含一個整數(shù)-1?！据斎胼敵鰳永?1】may