NOIP复赛模拟题(测试数据丢失) [复制链接]

  2005年全国信息学分区联赛模拟赛

编号 名称 时间限制 内存限制 命题 测试数据
1 猫猫的小鱼 1秒 16MB chineselyl 10组
2 创意吃鱼法 1秒 32MB ljch 10组
3 爱心蜗牛 2秒 64MB ljch 10组
4 巧置挡板 1秒 128MB ljch 10组



第一题　猫猫的小鱼

提交文件：catfish.pas/c/cpp
输入文件：catfish.in
输出文件：catfish.out

　　猫猫是丛林里很多动物心中的天使，她为此十分自豪。猫猫最爱吃鱼了，她每天都要去池塘钓鱼吃。猫猫经常吃鱼脑，数学特别强，然而，小女生的性格决定了她的贪玩。
　　一天，猫猫钓到了很多条鱼。她并不想马上就把可怜的鱼儿吃掉，而是先折磨够之后再吃（有句话叫什么来着～最毒不过猫猫心）。
　　猫猫将这很多很多（数不过来）条鱼按照外观的漂亮程度排序，每个鱼的编号依次为1、2、3……N，第i条鱼的美观程度为3^(i-1)。
　　猫猫要把这些鱼放到桶里去。她每次拿的鱼的数目是任意的。中的鱼的“总美观程度”为各条鱼美观程度之和。例如：猫猫这一次拿了第一条鱼和第三条鱼，那么美观程度为1+9=10。
　　猫猫想知道，她可以获得的第k大的“总美观程度”是多少。
　　从文件中读入k，输出猫猫能够获得的，第k大的“总美观程度”。

输入数据：
　　数据包含n+1行，第一行读入n(n≤100)。以下n行每行包含一个k。

输出数据：
　　输出包含n行，每行输出一个对应的结果。

输入样例：
1
7

输出样例：
13

样例说明：
　　猫猫能够拿到的美观程度从小到大为1、3、4、9、10、12、13……所以第7大的美观程度是13。
　　对于50%的输入文件，有k≤5000。
　　对于100%的输入文件，有k≤2^31-1。


第二题　创意吃鱼法


提交文件：meal.pas/c/cpp
输入文件：meal.in
输出文件：meal.out

回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^_*）。她发现，把大池子视为01矩阵（0表示对应位置无鱼，1表示对应位置有鱼）有助于决定吃鱼策略。
在代表池子的01矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“对角线的一端”下口，只一吸，就能把对角线上的那一队鲜鱼吸入口中。
　　猫猫是个贪婪的家伙，所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下，她一口下去，最多可以吃掉多少条鱼？

输入数据：
　　有多组输入数据，每组数据：
　　第一行有两个整数n和m（n,m≥1），描述池塘规模。接下来的n行，每行有m个数字（非“0”即“1”）。每两个数字之间用空格隔开。
　　对于30%的数据，有n,m≤100
　　对于60%的数据，有n,m≤1000
　　对于100%的数据，有n,m≤2500

输出数据：
　　只有一个整数——猫猫一口下去可以吃掉的鱼的数量，占一行，行末有回车。

输入样例：
4 6
0 1 0 1 0 0
0 0 1 0 1 0
1 1 0 0 0 1
0 1 1 0 1 0

输出样例：
3


第三题　爱心蜗牛


提交文件：badnews.pas/c/cpp
输入文件：badnews.in
输出文件：badnews.out

猫猫把嘴伸进池子里，正准备“吸”鱼吃，却听到门铃响了。猫猫擦了擦脸上的水，打开门一看，那人正是她的好朋友——川川。
川川手里拿着一辆玩具汽车，对猫猫说：“这是我的新汽车！”接着，伴随一阵塑料叩击声，玩具汽车的车门竟开了，一只蜗牛慢慢吞吞爬了出来。
“哇！这么大的蜗牛……”猫猫惊讶道。
“这是我的宠物蜗牛，他叫点点。”川川介绍道。
“把他送给我好吗？”猫猫央求道。
“可以让他陪你几天，但是不能送给你……”
点点沿着川川的身体，爬到了地上，又移到了猫猫的池子旁边，只听见猫猫向川川介绍她的“创意吃鱼法”，心里不禁起了一丝凉意：“这个女生太毒了……吃鱼前还要玩鱼……”转眼一看，池中的鱼依旧畅快地游来游去。
“或许这些鱼听不懂猫语吧……好在我会一点儿猫语，也会一点鱼语……阿弥陀佛，善哉善哉。我还是救救这些鱼吧……”点点自言自语，一边费力地移动着身躯。他认识到——单凭自己的力量，把猫猫的阴谋告诉每一条鱼，似乎不太可能——自己底盘太低，走不快，看来只得想其他办法来传达信息。一翻认真思考之后，点点想到，如果把猫猫的计划告诉其中一条鱼，再让鱼们互相传达消息，那么在相对较短的时间内，每条鱼都会得知猫猫的计划。
鱼们的社会等级森严，除了国王菜鱼之外，每条鱼均有且只有一个直接上级，菜鱼则没有上级。如果A是B的上级，B是C的上级，那么A就是C的上级。
绝对不会出现这样两条鱼A、B：A是B的上级，B也是A的上级。
　　最开始的时刻是0，点点要做的，就只是用1单位的时间把猫猫的阴谋告诉某一条“信息源鱼”，让鱼们自行散布消息。在任意一个时间单位中，任何一条已经接到通知的鱼，都可以把消息告诉他的一个直接上级或者直接下属。
现在，点点想知道：
1.到底需要多长时间，消息才能传遍池子里的鱼？
2.使消息传递过程消耗的时间最短，可供选择的“信息源鱼”有那些？

输入数据：
有多组输入数据，每组数据：
第一行有一个数N（N≤1000），表示池中的鱼数，池鱼按照1到n编上了号码，国王菜鱼的标号是1。
第2行到第N行（共N-1行），每一行一个数，第I行的数表示鱼I的直接上级的标号。

输出数据：
　　对于每组输入数据：
　　第一行有一个数，表示最后一条鱼接到通知的最早时间。
　　第二行有若干个数，表示可供选择的鱼F的标号，按照标号从小到大的顺序输出，中间用空格分开。

输入样例：
8
1
1
3
4
4
4
3

输出样例：
5
3 4 5 6 7


第四题　巧置挡板


提交文件：baffles.pas/c/cpp
输入文件：baffles.in
输出文件：baffles.out

猫猫送走了客人，留住了蜗牛点点，晃晃悠悠走到池子边，又打起了鱼的主意。俯瞰池子，猫猫发现鱼阵明显乱了。“难道鱼们故意让我无法下嘴？”猫猫看到正在池边散步的点点，心想：“一定是他告的密……”猫猫愤怒地抓起点点，把他关进了抽屉里。
猫猫想：“好啊，鱼儿啊，你们不就是会传递信息吗？有什么了不起？用挡板把你们隔离开，看你们还怎么交流！”猫猫随即从后花园里拿来若干挡板，打算用这些挡板在水中设立“隔离室”，把鱼们分开。
池塘已经被猫猫抽象成了n行m列小方格，每个小方格中或有鱼，或无鱼。挡板必须沿着小方格的边缘放置。猫猫需要用挡板围出若干个“隔离室”，使得每个隔离室中有且只有一条鱼，而且，每个“隔离室”都必须为矩形（包括正方形）。
那么，将鱼们隔离开来，猫猫最少需要多少个长度单位的木板呢？

　　例如：
　　n=4，m=3时的一种情况（0表示小方格内无鱼，1表示有鱼）。
0 1 0
0 0 0
1 0 1
0 0 0
　　可以这么分：
0 1 0
0 0 0
1 0 1
0 0 0

　　由于池塘边框不需要放置挡板，所以这个分割方案所需的挡板总长度为5。

输入数据：
第一行有两个整数n和m，描述池塘规模。接下来的n行，每行有m个数字（非“0”即“1”）。每两个数字之间用空格隔开。
对于20%的数据，有1≤n,m≤10
对于40%的数据，有1≤n,m≤16
对于70%的数据，有1≤n,m≤24
对于100%的数据，有1≤n,m≤32


输出数据：
对于每组输入数据，输出一行：一个数字，猫猫所需挡板的最短总长度。

输入样例：
4 3
0 1 0
0 0 0
1 0 1
0 0 0

输出样例：
5

有测试数据吗？急需！！！！！！！！！！！！！！！

测试数据~久等了~SORRY

请问这里边题目的解法在哪里讨论啊？

有点无奈

同志们,你们做出来的模拟题,可不可以,给我这样的初学者,贴出来,参考参考,
谢谢了

偶第一题就有三个数据通不过～哭死。

第一题：猫猫的小鱼
本题是一个数学题，主要牵涉到进制转换和高精度计算的知识。
我们注意到题目中所求的递增数列中的每个数都是整数，且每个数字都是由不同的3的整数次幂的和构成的，所以这个数字的三进制表示中只有0或1，我们注意到二进制也是由0和1组成的，结合题目中要我们求第k小的数字，因此不难想到在全体整数与数列之间建立一个一一对应，使得数字k的二进制表示与它所对应的三进制表示相同。举例说明：
K的值 对应的二进制 对应关系 相应的三进制 第k大的美观程度
1 1 1 1
2 10 10 3
3 11 11 4
4 100 100 9
5 101 101 10
6 110 110 12
7 111 111 13
因此我们需要做的就是把k这个数字转换成二进制，然后再把相应的二进制当作三进制转换成十进制就可以了，在k较大的时候需要高精度计算，似乎longint或者是extended可能也可以，但是我当时没有细细看。
时间复杂度：O(logk)

第二题：创意吃鱼法
本题是经典的DP题，题目比较简单。
我们所要求的是一个对角线为1，其余地方都为0的子正方形，考虑到对角线实际上是有左上到右下和从右上到左下这两种方向的，不失一般性，首先考虑左上到右下的方向。记f[i,j]为子正方形的右下角坐标为(i,j)所能产生的最优对角线的长度，left[i,j]为(i,j)的左边有多少个连续的0，up(i,j)表示(i,j)的右边有多少个连续的0，这样状态转移是显然的：
f(i,j)=min{f(i-1,j-1),up(i,j),left(i,j)}+1 if(graph[i,j]==1)
f(i,j)=0 if(graph[i,j]==0)
up[i,j]和left[i,j]的计算方法同一维部分和序列的DP方法相似，在此不再赘述。同样对于对角线从右上到左下的方向也可以同样处理。
上述的算法时间复杂度和空间复杂度都是O(n^2)，考虑到空间的限制，可以用滚动数组来解决MLE的问题，这同样是易于理解的。

呃 7楼转的算法貌似比较巧妙