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