全國(guó)賽題目NOI2009浙江省省選第二試

1、NOI2009 浙江省省選第二試競(jìng)賽時(shí)間：2009 年 6 月 13 日上午 8:00 13:00提交源程序名：對(duì)于Pascal 語(yǔ)言coins.pasws.passtone.pasrec.pas對(duì)于C語(yǔ)言coins.cws.cstone.crec.c對(duì)于C+語(yǔ)言coins.cppws.cppstone.cpprep題目名稱硬幣狼和羊的故事取石子對(duì)稱的正方形程序文件名(文件夾名)coinswsstonerec輸入文件名coins.inws.instone.inrec.in輸出文件名coins.outws.outstone.outrec.out每個(gè)測(cè)試點(diǎn)時(shí)限1s1s1s3s測(cè)試點(diǎn)數(shù)目101010

2、10每個(gè)測(cè)試點(diǎn)分值10101010內(nèi)存256M比較方式全文比較一、硬幣(coins.pas/.c/.cpp ，256M，1s)Orez 很喜歡玩，他最近發(fā)明了一款硬幣。他在桌子的邊緣上劃分出 2*n個(gè)位置并按順時(shí)針把它們標(biāo)號(hào)為 1，2，2n，然后把n 個(gè)硬幣放在標(biāo)號(hào)為奇數(shù)的位置上。接下來(lái)每次按如下操作：在任意兩個(gè)硬幣之間放上一個(gè)硬幣，然后將原來(lái)的硬幣拿走；所放硬幣的正由它兩邊的兩個(gè)硬幣決定，若兩個(gè)硬幣均為正面朝上或朝上，則所放硬幣為正面朝上，否則為朝上。那么操作T 次之后桌子邊緣上硬幣的情況會(huì)是怎樣的呢？輸入數(shù)據(jù)輸入數(shù)據(jù)存放在文本文件coins.in 中。文件的第一行包含兩個(gè)整數(shù)n 和T。接下

3、的一行包含 n 個(gè)整數(shù)，表示最開(kāi)始桌面邊緣的硬幣擺放情況，第 i 個(gè)整數(shù)ai 表示第 i 個(gè)硬幣擺放在 2*i-1 個(gè)位置上，ai=1 表示正面朝上，ai=2 表示朝上。輸出數(shù)據(jù)輸出數(shù)據(jù)存放在文本文件coins.out 中。文件僅包含一行，為 2n 個(gè)整數(shù)，其中第 i 個(gè)整數(shù) bi 桌面邊緣的第 i 個(gè)位置上硬幣的情況，bi=1 表示正面朝上，bi=2 表示朝上，bi=0 表示沒(méi)有硬幣。樣例輸入10 52 2 2 1 1 1 1 1 1 2樣例輸出0 1 0 1 0 1 0 1 0 2 0 1 0 2 0 1 0 1 0 1數(shù)據(jù)范圍30%的數(shù)據(jù) n1000T1000100%的數(shù)據(jù)n100000

4、T260二、狼和羊的故事(ws.pas/.c/.cpp, 256M, 1s)“狼愛(ài)上羊啊愛(ài)的瘋狂，誰(shuí)讓他們真愛(ài)了一場(chǎng)；狼愛(ài)上羊啊并不荒唐，他們說(shuō)有愛(ài)就有方向”O(jiān)rez 聽(tīng)到這首歌，心想：狼和羊如此和諧，為什么不嘗試羊狼合養(yǎng)呢？說(shuō)干就干！Orez 的羊狼圈可以看作一個(gè)n*m 個(gè)矩陣格子，這個(gè)矩陣的邊緣已經(jīng)裝上了。Drake 很快發(fā)現(xiàn)狼再怎么也是狼，它們總是對(duì)羊垂涎三尺，那首歌只不過(guò)是一個(gè)動(dòng)人的來(lái)養(yǎng)。而已。所以 Orez 決定在羊狼圈中再加入一些，還是要將羊狼分開(kāi)通過(guò)仔細(xì)觀察，Orez 發(fā)現(xiàn)狼和羊都有屬于自己領(lǐng)地，若狼和羊們不能呆在自己的領(lǐng)地，那它們就會(huì)變得非常暴躁，不利于他們的成長(zhǎng)。Orez 想

5、要添加的盡可能的短。當(dāng)然這個(gè)首先得保證不能改變狼羊的所屬領(lǐng)地，再就是 能只修建一部分。必須修筑完整，也就是說(shuō)必須修建在格子的邊界上并且不輸入數(shù)據(jù)輸入數(shù)據(jù)存放在文本文件ws.in 中。文件的第一行包含兩個(gè)整數(shù) n 和 m。接下來(lái) n 行每行 m 個(gè)整數(shù)，1 表示該格子屬于狼的領(lǐng)地，2 表示屬于羊的領(lǐng)地，0 表示該格子不是任何一只動(dòng)物的領(lǐng)地。輸出數(shù)據(jù)輸出數(shù)據(jù)存放在文本文件ws.out 中。文件中僅包含一個(gè)整數(shù)ans，代表的最短長(zhǎng)度。樣例輸入221221樣例輸出2數(shù)據(jù)范圍10%的數(shù)據(jù)30%的數(shù)據(jù)100%的數(shù)據(jù)n，m3 n，m20 n，m100三、取石子(stone.pas/.c/.cpp, 256M

6、 ,1s)在研究過(guò)Nim個(gè)是這樣的：及各種變種之后，Orez 又發(fā)現(xiàn)了一種全新的取石子，這有 n 堆石子，將這 n 堆石子擺成一排。由兩個(gè)人進(jìn)行，兩人輪流操作，每次操作者都可以從最左或最右的一堆中取出若干顆石子，可以將那一堆全部取掉，但不能不取，不能操作的人就輸了。Orez 問(wèn)：對(duì)于任意給出一個(gè)初始一個(gè)局面，是否存在先手必勝策略。輸入數(shù)據(jù)輸入數(shù)據(jù)存放在文本文件stone.in 中。文件的第一行為一個(gè)整數(shù) T，表示有 T 組測(cè)試數(shù)據(jù)。對(duì)于每組測(cè)試數(shù)據(jù)，第一行為一個(gè)整數(shù) n，表示有 n 堆石子；第二行為 n 個(gè)整數(shù) ai，依次表示每堆石子的數(shù)目。輸出數(shù)據(jù)輸出數(shù)據(jù)存放在文本文件stone.out 中

7、。對(duì)于每組測(cè)試數(shù)據(jù)僅輸出一個(gè)整數(shù) 0 或 1。其中 1 表示有先手必勝策略，0 表示沒(méi)有。樣例輸入143 1 9 4樣例輸出0數(shù)據(jù)范圍對(duì)于 30%的數(shù)據(jù)n55ai10對(duì)于 100%的數(shù)據(jù)T10 n1000 每堆的石子數(shù)目109四、對(duì)稱的正方形(rec.pas/.c/.cpp，256M，3s)Orez 很喜歡搜集一些神秘的數(shù)據(jù)，并經(jīng)常把它們排成一個(gè)矩陣進(jìn)行研究。最近， Orez 又得到了一些數(shù)據(jù)，并已經(jīng)把它們排成了一個(gè) n 行 m 列的矩陣。通過(guò)觀察， Orez 發(fā)現(xiàn)這些數(shù)據(jù)蘊(yùn)涵了一個(gè)奇特的數(shù)，就是矩陣中上下對(duì)稱且左右對(duì)稱的正方形子矩陣的個(gè)數(shù)。Orez 自然很想知道這個(gè)數(shù)是多少，序來(lái)計(jì)算出這個(gè)數(shù)。矩陣太大，無(wú)法去數(shù)。只能請(qǐng)你編個(gè)程輸入數(shù)據(jù)輸入數(shù)據(jù)存放在文本文件rec.in 中。文件的第一行為兩個(gè)整數(shù)n 和m。接下來(lái) n 行每行包含m 個(gè)正整數(shù)，表示 Orez得到的矩陣。輸入數(shù)據(jù)輸出數(shù)據(jù)存放在文本文件rec.out 中。文件中僅包含一