全国赛题目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测试点数目101010

2、10每个测试点分值10101010内存256M比较方式全文比较一、硬币(coins.pas/.c/.cpp ，256M，1s)Orez 很喜欢玩，他最近发明了一款硬币。他在桌子的边缘上划分出 2*n个位置并按顺时针把它们标号为 1，2，2n，然后把n 个硬币放在标号为奇数的位置上。接下来每次按如下操作：在任意两个硬币之间放上一个硬币，然后将原来的硬币拿走；所放硬币的正由它两边的两个硬币决定，若两个硬币均为正面朝上或朝上，则所放硬币为正面朝上，否则为朝上。那么操作T 次之后桌子边缘上硬币的情况会是怎样的呢？输入数据输入数据存放在文本文件coins.in 中。文件的第一行包含两个整数n 和T。接下

3、的一行包含 n 个整数，表示最开始桌面边缘的硬币摆放情况，第 i 个整数ai 表示第 i 个硬币摆放在 2*i-1 个位置上，ai=1 表示正面朝上，ai=2 表示朝上。输出数据输出数据存放在文本文件coins.out 中。文件仅包含一行，为 2n 个整数，其中第 i 个整数 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数据范围30%的数据 n1000T1000100%的数据n100000

4、T260二、狼和羊的故事(ws.pas/.c/.cpp, 256M, 1s)“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向”Orez 听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！Orez 的羊狼圈可以看作一个n*m 个矩阵格子，这个矩阵的边缘已经装上了。Drake 很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的来养。而已。所以 Orez 决定在羊狼圈中再加入一些，还是要将羊狼分开通过仔细观察，Orez 发现狼和羊都有属于自己领地，若狼和羊们不能呆在自己的领地，那它们就会变得非常暴躁，不利于他们的成长。Orez 想

5、要添加的尽可能的短。当然这个首先得保证不能改变狼羊的所属领地，再就是 能只修建一部分。必须修筑完整，也就是说必须修建在格子的边界上并且不输入数据输入数据存放在文本文件ws.in 中。文件的第一行包含两个整数 n 和 m。接下来 n 行每行 m 个整数，1 表示该格子属于狼的领地，2 表示属于羊的领地，0 表示该格子不是任何一只动物的领地。输出数据输出数据存放在文本文件ws.out 中。文件中仅包含一个整数ans，代表的最短长度。样例输入221221样例输出2数据范围10%的数据30%的数据100%的数据n，m3 n，m20 n，m100三、取石子(stone.pas/.c/.cpp, 256M

6、 ,1s)在研究过Nim个是这样的：及各种变种之后，Orez 又发现了一种全新的取石子，这有 n 堆石子，将这 n 堆石子摆成一排。由两个人进行，两人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了。Orez 问：对于任意给出一个初始一个局面，是否存在先手必胜策略。输入数据输入数据存放在文本文件stone.in 中。文件的第一行为一个整数 T，表示有 T 组测试数据。对于每组测试数据，第一行为一个整数 n，表示有 n 堆石子；第二行为 n 个整数 ai，依次表示每堆石子的数目。输出数据输出数据存放在文本文件stone.out 中

7、。对于每组测试数据仅输出一个整数 0 或 1。其中 1 表示有先手必胜策略，0 表示没有。样例输入143 1 9 4样例输出0数据范围对于 30%的数据n55ai10对于 100%的数据T10 n1000 每堆的石子数目109四、对称的正方形(rec.pas/.c/.cpp，256M，3s)Orez 很喜欢搜集一些神秘的数据，并经常把它们排成一个矩阵进行研究。最近， Orez 又得到了一些数据，并已经把它们排成了一个 n 行 m 列的矩阵。通过观察， Orez 发现这些数据蕴涵了一个奇特的数，就是矩阵中上下对称且左右对称的正方形子矩阵的个数。Orez 自然很想知道这个数是多少，序来计算出这个数。矩阵太大，无法去数。只能请你编个程输入数据输入数据存放在文本文件rec.in 中。文件的第一行为两个整数n 和m。接下来 n 行每行包含m 个正整数，表示 Orez得到的矩阵。输入数据输出数据存放在文本文件rec.out 中。文件中仅包含一