全國賽題目NOI2009浙江省省選第二試

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

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

3、的一行包含 n 個整數(shù)，表示最開始桌面邊緣的硬幣擺放情況，第 i 個整數(shù)ai 表示第 i 個硬幣擺放在 2*i-1 個位置上，ai=1 表示正面朝上，ai=2 表示朝上。輸出數(shù)據(jù)輸出數(shù)據(jù)存放在文本文件coins.out 中。文件僅包含一行，為 2n 個整數(shù)，其中第 i 個整數(shù) bi 桌面邊緣的第 i 個位置上硬幣的情況，bi=1 表示正面朝上，bi=2 表示朝上，bi=0 表示沒有硬幣。樣例輸入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)“狼愛上羊啊愛的瘋狂，誰讓他們真愛了一場；狼愛上羊啊并不荒唐，他們說有愛就有方向”O(jiān)rez 聽到這首歌，心想：狼和羊如此和諧，為什么不嘗試羊狼合養(yǎng)呢？說干就干！Orez 的羊狼圈可以看作一個n*m 個矩陣格子，這個矩陣的邊緣已經(jīng)裝上了。Drake 很快發(fā)現(xiàn)狼再怎么也是狼，它們總是對羊垂涎三尺，那首歌只不過是一個動人的來養(yǎng)。而已。所以 Orez 決定在羊狼圈中再加入一些，還是要將羊狼分開通過仔細觀察，Orez 發(fā)現(xiàn)狼和羊都有屬于自己領(lǐng)地，若狼和羊們不能呆在自己的領(lǐng)地，那它們就會變得非常暴躁，不利于他們的成長。Orez 想

5、要添加的盡可能的短。當(dāng)然這個首先得保證不能改變狼羊的所屬領(lǐng)地，再就是 能只修建一部分。必須修筑完整，也就是說必須修建在格子的邊界上并且不輸入數(shù)據(jù)輸入數(shù)據(jù)存放在文本文件ws.in 中。文件的第一行包含兩個整數(shù) n 和 m。接下來 n 行每行 m 個整數(shù)，1 表示該格子屬于狼的領(lǐng)地，2 表示屬于羊的領(lǐng)地，0 表示該格子不是任何一只動物的領(lǐng)地。輸出數(shù)據(jù)輸出數(shù)據(jù)存放在文本文件ws.out 中。文件中僅包含一個整數(shù)ans，代表的最短長度。樣例輸入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)在研究過Nim個是這樣的：及各種變種之后，Orez 又發(fā)現(xiàn)了一種全新的取石子，這有 n 堆石子，將這 n 堆石子擺成一排。由兩個人進行，兩人輪流操作，每次操作者都可以從最左或最右的一堆中取出若干顆石子，可以將那一堆全部取掉，但不能不取，不能操作的人就輸了。Orez 問：對于任意給出一個初始一個局面，是否存在先手必勝策略。輸入數(shù)據(jù)輸入數(shù)據(jù)存放在文本文件stone.in 中。文件的第一行為一個整數(shù) T，表示有 T 組測試數(shù)據(jù)。對于每組測試數(shù)據(jù)，第一行為一個整數(shù) n，表示有 n 堆石子；第二行為 n 個整數(shù) ai，依次表示每堆石子的數(shù)目。輸出數(shù)據(jù)輸出數(shù)據(jù)存放在文本文件stone.out 中

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