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

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个月老鼠的数量。【输入样例】0 1 1 11【输出样例】144倒金字塔(purple.pas/c/cpp)【问题描述】Purple国的一支科学考察队到达了举世闻名的古埃及金字塔。关于金字塔的建造一直是一个未解之谜，有着“西方史学之父”之称的希罗多德认为，金字塔的 建造是人力和

3、牲畜， 花费 20 年时间从西奈半岛挖掘天然的石头运送到埃及堆砌而成。 也有不少 人认为是外星人修建的。人们发现胡夫金字塔的经线把地球分成东、西两个半球，它们的陆地 面积是相等的，这种“巧合”大概是外星人选择金字塔建造地点的用意。法国化学家戴维杜 维斯则认为，建造金字塔的巨石不是天然的，而是人工浇筑的。Purple国科考队的队员们正准备研究戴维杜维斯提出的假说。为了研究这种假说，他们需 要用到“倒金字塔模型”。所谓倒金字塔模型，即金字塔由 N 层人工浇筑的巨石堆砌而成，非 底层的任意一层巨石的长度和宽度都必须要小于等于它下面的一层巨石的长度和宽度。 现在，科考队队员们打算用手里仅有 N 块木板

4、去模拟这个倒金字塔模型。请计算出科考队队 员们能够构建的倒金字塔模型的最大高度。【输入文件】输入文件purple.in 的第1行，为一个正整数 N(N<=100000)，表示科考队队员们手里一共有 N 块木板。接下来 N 行，每行两个数 :a ， b(a,b<=100000) ，分别表示一块木板的长度与宽度。【输出文件】输出文件 purple.out 只有一个正整数，为最多可以堆叠的倒金字塔的高度。所有的木板厚 度均为 1 。【输入样例】33 21 12 2【输出样例】3打地鼠yy.pas/c/cpp yy.in/outSDyy 喜欢游戏。实际上， YY 所喜欢的游戏都是很幼稚的。

5、他幼稚地找到你，让你帮 他玩这个游戏。 YY 的游戏名字叫打地鼠。规则很简单。有一个 5*5 的棋盘，棋盘外边是高 速公路，用绿色表示。如果两个格子拥有公共边，这 2 个格子就是相邻的。左下角的棋盘 格为 (1,1)，右上角为 (5,5)游戏开始，在第以在瞬间完成以下的一种任务:(1)(2)(3)(4)，每当秒针跳一下，YY可什么也不干从某个格子移动到相邻的格子从某个最外层的格子移动到高速公路上 从高速公路上移动到某个最外层的格子。但是，高速公路的管理部门告诉YY，他在任意连续3s内，至多能使用高速公路 1s。YY在某些秒钟，某些格子上会出现可爱的小动物，比如鼠之类的，如果在这一秒钟， 恰巧也

6、在这个格子里，设坐标为 (x,y)那么他就可以得到1分。分数是累加的。已知游戏在第M秒末结束，请帮助YY设计一个路线，使得YY可以获得最大的得分， 当然为了你的方便，你只需要计算出这个最大得分就可以了。【输入文件】yy.in第一行N：鼹鼠出现的次数。M:游戏的总时间以下N行，每行包括 4个整数，A B C D ( 1V=A,BV=5，1v=C<=D<=M)，表示在第 C 秒初到第D秒末，在(A,B)格子上会出现鼹鼠。请注意 C和D所构成的区间之间可能有交 集。【输出文件】yy.out一个整数，即最高分数【样例输入】2 101 1 1 54 4 8 8【样例输出】6【对样例的说明】在

7、第6s跑到公路上，第7s跑到(5，4)，第8s跑到(4， 4)【数据范围】对于30%的数据，M<=10对于100%的数据，M<=3000，N<=1000。每行上的CD的差的绝对值不超过 10工作( Work.pas/exe)【题目描述】这次故事的主角是 HG !转眼4年过去了，HG本科毕业了，于是找了份工作。每天HG会收到一份任务清单，清单上列出了n个可能需要他完成的任务。每个任务包含3个信息：Ti、Ai 、Bi ， Ti 表示完成此任务需要的时间， Ai 表示此任务的到达时间， Bi 表示此任务的最晚完成 时间。 在某一时刻若 HG 手上没有任务， 那么他可以选择一个已经到

8、达且还能够在 Bi 时刻之前 （或者恰好在 Bi 时刻）完成的任务来做。由于HG有点懒（纯属虚构:D），他想尽量少的减少他的总工作时间，但是他不能在可以做 任务的时候故意不做（这样会被炒鱿鱼的 >_<），那么他该如何挑选任务来做呢？ 你的任务就是求出 HG 的最少工作时间（即总共有多少时间 HG 在做任务）。输入】 第一行一个整数 n 表示任务数。以下 n 行，每行三个整数 Ti,Ai,Bi 。（ n<=1000 ， 0<=Ai,Bi<=1500 ， Ti>=1 ） 【输出】输出仅一个数，即最少工作时间。【样例输入】315 0 2550 0 9045 15

9、70【样例输出】50【数据范围】Ti>=1 ， 0<=Ai,Bi<=1200 ； 30%的数据满足 n<=5； 60的数据满足 n<=500； 100的数据满足 n<=1000 。说明】输入数据保证Bi-Ai要大于等于Ti，且小于2Ti。又上锁妖塔(tower.in/tower .out)题目描述小D在X星买完了想要的东西，在飞往下一个目的地的途中，正无聊的他转头看了看身边的 小A,发现小A正在玩 <仙剑，可是小A很奇怪，他一直在锁妖塔的周围转来转去，可是就是不进去于是小D问他:”你在干什么？怎么不上去？”小A说:”我在想怎么从锁妖塔外面爬上去”倒)锁

10、妖塔的建造很特别，塔总共有n层，但是高度却不相同，这造成了小A爬过每层的时间也不同小A 会用仙术，每用一次可以让他向上跳一层或两层，但是每次跳跃后小 A都将用完灵力，必须爬过至少一层才能再次跳跃(你可以认为小 A需要跳两次一层才休息)，小A想用最短的时间爬到塔顶， 可是他不能找到时间最短的方案，所以请你帮他找到一个时间最短的方案让他爬到塔顶，小A只关心时间，所以你只要告诉他最短时间是多少就可以了你可以最后跳到塔外即超过塔高.输入格式第一行一个数n (n<=10000)，表示塔的层数.接下来的n行每行一个数(<=100),表示从下往上每层的高度.输出格式一个数，表示最短时间样例输入5

11、35184样例输出1数据规模对20%的数据,n<=10对40%的数据,n<=100对60%的数据,n<=5000对 100% 的数据,n<=100004853（样例说明）5771001803090012095 5790368228596330825771001803090012386 5761373997357606965771001803090013594 5780775799025155125771001803090012387 5771649826018180515771001803090012138 5721311921589183265771001803090

12、012359 5790368223610760535771001803090012356 5761352861437917425771001803090012355 57508786970469327917088100343355274 10122994432583337917088100343355275 10186673293883200817088100343356107 10158115250150052217088100343356108 10100018005987173217088100343354295 10107419414268701717088100343356184 10187866086962880217088100343356185 10177583117408667417088100343356109 10108