1、全國信息學(xué)奧林匹克聯(lián)賽（NOIP2015）復(fù)賽 提高組 day1CCF 全國信息學(xué)奧林匹克聯(lián)賽（NOIP2015）復(fù)賽提高組 day1（請選手務(wù)必仔細(xì)閱讀本頁內(nèi)容）一題目概況中文題目名稱神奇的幻方信息傳遞斗地主英文題目與子目錄名magicmessagelandlords可執(zhí)行文件名magicmessagelandlords輸入文件名magic.inmessage.inlandlords.in輸出文件名magic.outmessage.outlandlords.out每個(gè)測試點(diǎn)時(shí)限1 秒1 秒2 秒測試點(diǎn)數(shù)目101020每個(gè)測試點(diǎn)分值10105附加樣例文件有有有結(jié)果比較方式全文比較（過濾行末空格

2、及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)運(yùn)行內(nèi)存上限128M128M1G二提交源程序文件名對于 C+語言magic.cppmessage.cpplandlords.cpp對于 C 語言magic.cmessage.clandlords.c對于 pascal 語言magic.pasmessage.paslandlords.pas三編譯命令（不包含任何優(yōu)化開關(guān)）對于 C+語言g+ -o magicmagic.cpp -lmg+ -o messagemessage.cpp -lmg+ -o landlordslandlords.cpp -lm對于 C 語言gcc -o magicmagic.c -lmgcc

3、 -o messagemessage.c -lmgcc -o landlordslandlords.c -lm對于 pascal 語言fpc magic.pasfpc message.pasfpc landlords.pas注意事項(xiàng)：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。2、C/C+中函數(shù) main()的返回值類型必須是 int，程序正常結(jié)束時(shí)的返回值必須是 0。 3、全國統(tǒng)一評測時(shí)采用的機(jī)器配置為：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz，內(nèi)存 4G，上述時(shí)限以此配置為準(zhǔn)。 4、只提供 Linux 格式附加樣例文件。5、特別提

4、醒：評測在當(dāng)前最新公布的 NOI Linux 下進(jìn)行，各語言的編譯器版本以其為準(zhǔn)。第 6頁 共 6頁1神奇的幻方(magic.cpp/c/pas)【問題描述】幻方是一種很神奇的 N*N 矩陣：它由數(shù)字 1,2,3, , N*N 構(gòu)成，且每行、每列及兩條對角線上的數(shù)字之和都相同。當(dāng)N為奇數(shù)時(shí)，我們可以通過以下方法構(gòu)建一個(gè)幻方： 首先將 1 寫在第一行的中間。之后，按如下方式從小到大依次填寫每個(gè)數(shù)K(K= 2,3, , N*N )：1. 若 (K1) 在第一行但不在最后一列，則將K填在最后一行，(K 1) 所在列的右一列；2. 若 (K 1) 在最后一列但不在第一行，則將K填在第一列，(K 1)

5、所在行的上一行；3. 若 (K 1) 在第一行最后一列，則將K填在 (K 1) 的正下方；4. 若 (K 1) 既不在第一行，也不在最后一列，如果 (K 1) 的右上方還未填數(shù)， 則將K填在(K 1)的右上方，否則將K填在 (K 1) 的正下方現(xiàn)給定N，請按上述方法構(gòu)造 N*N 的幻方?！据斎敫袷健枯斎胛募麨?magic.in。輸入文件只有一行，包含一個(gè)整數(shù)N，即幻方的大小?！据敵龈袷健枯敵鑫募麨?magic.out。輸出文件包含N行，每行N個(gè)整數(shù)，即按上述方法構(gòu)造出的N*N的幻方。相鄰 兩個(gè)整數(shù)之間用單個(gè)空格隔開?！据斎胼敵鰳永?1】magic.inmagic.out38 1 63 5

6、74 9 2見選手目錄下的 magic/magic1.in 和 magic/magic1.ans?！据斎胼敵鰳永?2】見選手目錄下的 magic/magic2.in 和 magic/magic2.ans?！緮?shù)據(jù)規(guī)模與約定】對于 100% 的數(shù)據(jù)，1 N39 且N為奇數(shù)。2信息傳遞(message.cpp/c/pas)【問題描述】 有 n 個(gè)同學(xué)（編號為 1 到 n）正在玩一個(gè)信息傳遞的游戲。在游戲里每人都有一個(gè)固定的信息傳遞對象，其中，編號為 i 的同學(xué)的信息傳遞對象是編號為 Ti 的同學(xué)。 游戲開始時(shí)，每人都只知道自己的生日。之后每一輪中，所有人會同時(shí)將自己當(dāng)前所知的生日信息告訴各自的信息傳

7、遞對象（注意：可能有人可以從若干人那里獲取信息，但是每人只會把信息告訴一個(gè)人，即自己的信息傳遞對象）。當(dāng)有人從別人口中得知自己的生日時(shí)，游戲結(jié)束。請問該游戲一共可以進(jìn)行幾輪？【輸入格式】輸入文件名為 message.in。輸入共 2 行。第 1 行包含 1 個(gè)正整數(shù) n ，表示 n 個(gè)人。第 2 行包含 n 個(gè)用空格隔開的正整數(shù)T1,T2, ,Tn，其中第Ti個(gè)整數(shù)表示編號為 i 的同學(xué)的信息傳遞對象是編號為 Ti 的同學(xué)，Ti n 且Ti i。數(shù)據(jù)保證游戲一定會結(jié)束?！据敵龈袷健枯敵鑫募麨?message.out。輸出共 1 行，包含 1 個(gè)整數(shù)，表示游戲一共可以進(jìn)行多少輪。 【輸入輸出樣

8、例 1】message.inmessage.out52 4 2 3 13見選手目錄下的 message/message1.in 與 message/message1.ans。【輸入輸出樣例 1 說明】游戲的流程如圖所示。當(dāng)進(jìn)行完第 3 輪游戲后，4 號玩家會聽到 2 號玩家告訴他自己的生日，所以答案為 3。當(dāng)然，第 3 輪游戲后，2 號玩家、3 號玩家都能從自己的消息 來源得知自己的生日，同樣符合游戲結(jié)束的條件?！緲永斎胼敵?2】見選手目錄下的 message/message2.in 與 message/message2.ans?！緮?shù)據(jù)規(guī)模與約定】對于 30%的數(shù)據(jù) n 200； 對于 60

9、%的數(shù)據(jù)，n 2500； 對于 100%的數(shù)據(jù)，n 200000。3. 斗地主（landlords.cpp/c/pas)【問題描述】牛牛最近迷上了一種叫斗地主的撲克游戲。斗地主是一種使用黑桃、紅心、梅花、 方片的 A 到 K 加上大小王的共 54 張牌來進(jìn)行的撲克牌游戲。在斗地主中，牌的大小關(guān)系根據(jù)牌的數(shù)碼表示如下：3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不對牌的大小產(chǎn)生影響。每一局游戲中，一副手牌由 n 張牌組成。游戲者每次可以根據(jù)規(guī)定的牌型進(jìn)行出牌，首先打光自己的手牌一方取

10、得游戲的勝利?，F(xiàn)在，牛牛只想知道，對于自己的若干組手牌，分別最少需要多少次出牌可以將它們打光。請你幫他解決這個(gè)問題。需要注意的是，本題中游戲者每次可以出手的牌型與一般的斗地主相似而略有不同。具體規(guī)則如下：牌型牌型說明牌型舉例照片火箭即雙王（雙鬼牌）。炸彈四張同點(diǎn)牌。如四個(gè) A。單張牌單張牌，比如 3。對子牌兩張碼數(shù)相同的牌。三張牌三張碼數(shù)相同的牌。三帶一三張碼數(shù)相同的牌 + 一張單牌。例如：三張3+單4三帶二三張碼數(shù)相同的牌 + 一對牌。例如：三張3+對4單順子五張或更多碼數(shù)連續(xù)的單牌（不包括 2點(diǎn)和雙王）例如：單 7+單 8+單 9+單 10+單 J。另外，在順牌（單順子、雙順子、三順子）中

11、，牌的花色不要求相同。雙順子三對或更多碼數(shù)連續(xù)的對牌（不包括 2點(diǎn)和雙王）。例如：對3+對4+對5。三順子二個(gè)或更多碼數(shù)連續(xù)的三張牌（不能包括 2 點(diǎn)和雙王）。例如：三張 3+三張 4+三張 5。四帶二四張碼數(shù)相同的牌+任意兩張單牌（或任意兩對牌）例如：四張 5+單 3+單 8 或 四張 4+對 5+對 7【輸入格式】輸入文件名為 landlords.in。第一行包含用空格隔開的2個(gè)正整數(shù)T,n,表示手牌的組數(shù)以及每組手牌的張數(shù)。接下來T組數(shù)據(jù)，每組數(shù)據(jù)n行，每行一個(gè)非負(fù)整數(shù)對ai,bi，表示一張牌，其中ai表示牌的數(shù)碼，bi表示牌的花色，中間用空格隔開。特別的，我們用 1 來表示數(shù)碼 A，1

12、1 表示數(shù)碼 J，12 表示數(shù)碼 Q，13 表示數(shù)碼 K；黑桃、紅心、梅花、方片分別用 1-4 來表示；小王的表示方法為 0 1，大王的表示方法為 0 2?！据敵龈袷健枯敵鑫募麨?landlords.out。共 T 行，每行一個(gè)整數(shù)，表示打光第i組手牌的最少次數(shù)。 【輸入輸出樣例 1】landlords.inlandlords.out1 87 48 49 110 411 15 11 4113見選手目錄下的 landlords/landlords1.in 與 landlords/landlords1.ans?！据斎胼敵鰳永?1 說明】共有 1 組手牌，包含 8 張牌：方片7，方片8，黑桃9，方片10，黑桃J，黑桃5，方片A 以及黑桃A?？梢酝ㄟ^打單順子（方片7，方片8，黑桃9，方片10，黑桃J），單張牌（黑桃5）以及對子牌（黑桃A 以及方片A）在3次內(nèi)打光?！据斎胼敵鰳永?2】landlords.inlandlords.out1 1712 34 32 35 410 23 312 20 11 310 16 212 111 35 212 42 27 26見選手目錄下的 landlords/landlords2.in 與 landlords/landlords2.ans?！緲永斎胼敵?3】見選手目錄下的 landlords/landlords3.in 與 landlor