信息学奥林匹克竞赛复赛试题.doc

《信息学奥林匹克竞赛复赛试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2007衢州一中校庆noip练习第一题阿猫的实验（cat.pas）第二题倒金字塔（purple.pas）第三题打地鼠（yy.pas）第四题工作（Work.pas/exe）第五题又上锁妖塔（tower）阿猫的实验(cat.pas/c/cpp)【问题描述】阿猫很喜欢生物学。他还在今年的全国中学生生物学联赛中获得了一等奖。一天，阿猫在实验室听说了这样一种繁殖能力很强的老鼠。这种老鼠在出生后的第一个月，可以生出a对老鼠；第二个月，可以生出b对老鼠；第三个月及以后的每个月，都可以生出c对老鼠。阿猫对此十分

2、好奇。他很想知道，如果他有一对刚出生的老鼠，按最理想的模式繁殖，且老鼠不死，那么最少需要多少个月它们就可以覆盖整个地球。为了完成这一猜想，阿猫需要知道这种老鼠在第N个月时的数量。【输入文件】输入文件cat.in只有一行，四个数，分别为a，b，c，N（0<=a<=b<=c<=100，N<=3000)，其含义为题目所述。【输出文件】输出文件cat.out只有一个数，为第N个月老鼠的数量。【输入样例】01111【输出样例】144倒金字塔(purple.pas/c/cpp)【问题描述】Purple国的一

3、支科学考察队到达了举世闻名的古埃及金字塔。关于金字塔的建造一直是一个未解之谜,有着“西方史学之父”之称的希罗多德认为，金字塔的建造是人力和牲畜，花费20年时间从西奈半岛挖掘天然的石头运送到埃及堆砌而成。也有不少人认为是外星人修建的。人们发现胡夫金字塔的经线把地球分成东、西两个半球，它们的陆地面积是相等的，这种“巧合”大概是外星人选择金字塔建造地点的用意。法国化学家戴维·杜维斯则认为，建造金字塔的巨石不是天然的，而是人工浇筑的。Purple国科考队的队员们正准备研究戴维·杜维斯提出的假说。为了研究

4、这种假说，他们需要用到“倒金字塔模型”。所谓倒金字塔模型，即金字塔由N层人工浇筑的巨石堆砌而成，非底层的任意一层巨石的长度和宽度都必须要小于等于它下面的一层巨石的长度和宽度。现在，科考队队员们打算用手里仅有N块木板去模拟这个倒金字塔模型。请计算出科考队队员们能够构建的倒金字塔模型的最大高度。【输入文件】输入文件purple.in的第1行，为一个正整数N(N<=)，表示科考队队员们手里一共有N块木板。接下来N行，每行两个数:a，b(a,b<=)，分别表示一块木板的长度与宽度。【输出文件】输出文件p

5、urple.out只有一个正整数，为最多可以堆叠的倒金字塔的高度。所有的木板厚度均为1。【输入样例】3321122【输出样例】3打地鼠yy.pas/c/cppyy.in/outSDyy喜欢游戏。实际上，YY所喜欢的游戏都是很幼稚的。他幼稚地找到你，让你帮他玩这个游戏。YY的游戏名字叫打地鼠。规则很简单。有一个5*5的棋盘，棋盘外边是高速公路，用绿色表示。如果两个格子拥有公共边，这2个格子就是相邻的。左下角的棋盘格为(1,1)，右上角为(5,5)游戏开始，在第1秒钟初，YY随便找了一个格子跳了进去

6、，每当秒针跳一下，YY可以在瞬间完成以下的一种任务：（1）什么也不干（2）从某个格子移动到相邻的格子（3）从某个最外层的格子移动到高速公路上（4）从高速公路上移动到某个最外层的格子。但是，高速公路的管理部门告诉YY，他在任意连续3s内，至多能使用高速公路1s。在某些秒钟，某些格子上会出现可爱的小动物，比如鼠之类的，如果在这一秒钟，YY恰巧也在这个格子里，设坐标为(x,y)那么他就可以得到1分。分数是累加的。已知游戏在第M秒末结束，请帮助YY设计一个路线，使得YY可以获得最大的得分，当然为了你的方

7、便，你只需要计算出这个最大得分就可以了。【输入文件】yy.in第一行N：鼹鼠出现的次数。M：游戏的总时间以下N行，每行包括4个整数，ABCD（1<=A,B<=5，1<=C<=D<=M），表示在第C秒初到第D秒末，在(A,B)格子上会出现鼹鼠。请注意C和D所构成的区间之间可能有交集。【输出文件】yy.out一个整数，即最高分数【样例输入】21011154488【样例输出】6【对样例的说明】在第6s跑到公路上，第7s跑到（5，4），第8s跑到（4，4）【数据范围】对于30%的数据，M<=10对于10

8、0%的数据，M<=3000，N<=1000。每行上的CD的差的绝对值不超过10。工作（Work.pas/exe）【题目描述】这次故事的主角是HG！转眼4年过去了，HG本科毕业了，于是找了份工作。每天HG会收到一份任务清单，清单上列出了n个可能需要他完成的任务。每个任务包含3个信息：Ti、Ai、Bi，Ti表示完成此任务需要的时间，Ai表示此任务的到达时间，Bi表示此任务的最晚完成时间。在某一时刻若HG手上没有任务，那么他可以选择一个已经到达且还能够在Bi时刻之前（或者恰好在Bi时刻）完成的任务来做