2012年清华大学计算机系推免保研上机考试
转载自:https://blog.csdn.net/xqyjack/article/details/8013710Date:2012年9月23日晚6:30-8:30
Place:清华大学东主楼
要求使用C或C++,总共三道题,按通过的测试数据组数给分。
在网上的OJ系统提交代码,不能看到代码是否Accept,只能知道是否编译成功,成绩只有老师知道,我们看不到。
1.简单模拟
问题描述
在公元 N 年 1 月 1 日,一群精灵植下了一棵高度为 h 厘米的树。这棵神奇的树每天都会长高 1 厘米。他们想知道,这棵树到了公元 2013 年 1 月1 日会有多高?
示 所有能被 400 整除的年份,或者不能被 100 整除且被 4 整除的年份都是闰年,而其它年份都不是闰年。一个闰年有 366 天,一个非闰年有 365 天。
示 所有能被 400 整除的年份,或者不能被 100 整除且被 4 整除的年份都是闰年,而其它年份都不是闰年。一个闰年有 366 天,一个非闰年有 365 天。
输入格式
输入数据的第一行有两个正整数 N 和 h。(1583 ≤ N ≤ 2012, 1 ≤ h ≤200)
输出格式
输出数据应当只有一行,包含一个整数,即这棵树在 2013 年 1 月 1 日的高度,单位是厘米。
样例输入
2012 100
样例输出
466
2.贪心或动归
问题描述
沿着一条道路有 N 个仓库,相邻两个仓库间距离为 1 公里。假设第 i个仓库存有 Xi 个单位的货物。现在希望将货物重新分配,使得最终每个仓库内的货物量 Xi 相等。
假设将 1 个单位的货物运送 1 公里的耗费为 1 个金币。请你计算出为了让各个仓库内的货物相等最少需要花费多少个金币。
假设将 1 个单位的货物运送 1 公里的耗费为 1 个金币。请你计算出为了让各个仓库内的货物相等最少需要花费多少个金币。
输入格式
输入第一行有一个数,N (1 ≤ N ≤ 1000) ,表示仓库的个数。
第二行为用空格隔开的 N 个正整数,依次表示 X1 到 XN 。假定 Xi 不超过 1000的非负整数。所有 Xi 的和一定为 N 的倍数。
第二行为用空格隔开的 N 个正整数,依次表示 X1 到 XN 。假定 Xi 不超过 1000的非负整数。所有 Xi 的和一定为 N 的倍数。
输出格式
输出文件只有一行,一个整数,表示最少花费。
样例输入
3
1 6 2
1 6 2
样例输出
3
对样例的解释
先从 2 号仓库运送 2 个单位的货物给 1 号仓库,然后从 2 号仓库运送
1 个单位的货物给 3 号仓库,所以总费用为 2 × 1 + 1 × 1 = 3。
对样例的解释
先从 2 号仓库运送 2 个单位的货物给 1 号仓库,然后从 2 号仓库运送
1 个单位的货物给 3 号仓库,所以总费用为 2 × 1 + 1 × 1 = 3。
3.有点难,RMQ应该可以吧
问题描述
精灵们住在一片矩形树林里,这片树林的边与坐标轴平行,它的西南角坐标是 (0, 0),东北角坐标是 (w, h)。这片树林有 N 棵树,其中第 i 棵树的位置是 (xi, yi)。
精灵们最近在与矮人的贸易中赚取了一大笔金子,他们希望在这片树林里建造一个金屋子。为了美观,精灵们希望这个屋子是正方形的,并且它的边也要和坐标轴平行。
作为一种热爱自然的生物,精灵们可不愿意为了造这个屋子砍掉任何一棵树。因此,造屋子的区域内部不能有树。不过,屋子的边界上可以有树,这样建造屋子并不会伤害到这棵树。
精灵们正在给这个屋子进行选址。他们想知道,这个屋子有可能造到多大。
精灵们最近在与矮人的贸易中赚取了一大笔金子,他们希望在这片树林里建造一个金屋子。为了美观,精灵们希望这个屋子是正方形的,并且它的边也要和坐标轴平行。
作为一种热爱自然的生物,精灵们可不愿意为了造这个屋子砍掉任何一棵树。因此,造屋子的区域内部不能有树。不过,屋子的边界上可以有树,这样建造屋子并不会伤害到这棵树。
精灵们正在给这个屋子进行选址。他们想知道,这个屋子有可能造到多大。
输入格式
输入文件的第 1 行有三个正整数 N , w 和 h。 (1 ≤ N ≤ 1000, 1 ≤ w, h ≤ 10000)
输入文件的第 2 行到第 (N + 1) 行分别有两个非负整数。其中,第(i + 1) 行的两个整数表示 xi 和 yi。 (0 ≤ xi ≤ w, 0 ≤ yi ≤ h)
输入文件的第 2 行到第 (N + 1) 行分别有两个非负整数。其中,第(i + 1) 行的两个整数表示 xi 和 yi。 (0 ≤ xi ≤ w, 0 ≤ yi ≤ h)
输出格式
输出文件只包括一行,其中只有一个整数,即这个屋子可能的最大边长。
样例输入
5 5 5
1 1
4 1
1 4
2 2
4 3
1 1
4 1
1 4
2 2
4 3
样例输出
3
样例说明