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 天。

输入格式

　　输入数据的第一行有两个正整数 N 和 h。(1583 ≤ N ≤ 2012, 1 ≤ h ≤200)

输出格式

　　输出数据应当只有一行,包含一个整数,即这棵树在 2013 年 1 月 1 日的高度,单位是厘米。

样例输入

2012 100

样例输出

466

2.贪心或动归

问题描述

　　沿着一条道路有 N 个仓库,相邻两个仓库间距离为 1 公里。假设第 i个仓库存有 X_i 个单位的货物。现在希望将货物重新分配,使得最终每个仓库内的货物量 X_i 相等。
　　假设将 1 个单位的货物运送 1 公里的耗费为 1 个金币。请你计算出为了让各个仓库内的货物相等最少需要花费多少个金币。

输入格式

　　输入第一行有一个数,N (1 ≤ N ≤ 1000) ,表示仓库的个数。
　　第二行为用空格隔开的 N 个正整数,依次表示 X₁ 到 X_N 。假定 X_i 不超过 1000的非负整数。所有 X_i 的和一定为 N 的倍数。

输出格式

　　输出文件只有一行,一个整数,表示最少花费。

样例输入

3
1 6 2

样例输出

3
对样例的解释
先从 2 号仓库运送 2 个单位的货物给 1 号仓库,然后从 2 号仓库运送
1 个单位的货物给 3 号仓库,所以总费用为 2 × 1 + 1 × 1 = 3。

3.有点难，RMQ应该可以吧

问题描述

　　精灵们住在一片矩形树林里,这片树林的边与坐标轴平行,它的西南角坐标是 (0, 0),东北角坐标是 (w, h)。这片树林有 N 棵树,其中第 i 棵树的位置是 (x_i, y_i)。
　　精灵们最近在与矮人的贸易中赚取了一大笔金子,他们希望在这片树林里建造一个金屋子。为了美观,精灵们希望这个屋子是正方形的,并且它的边也要和坐标轴平行。
　　作为一种热爱自然的生物,精灵们可不愿意为了造这个屋子砍掉任何一棵树。因此,造屋子的区域内部不能有树。不过,屋子的边界上可以有树,这样建造屋子并不会伤害到这棵树。
　　精灵们正在给这个屋子进行选址。他们想知道,这个屋子有可能造到多大。

输入格式

　　输入文件的第 1 行有三个正整数 N , w 和 h。 (1 ≤ N ≤ 1000, 1 ≤ w, h ≤ 10000)
　　输入文件的第 2 行到第 (N + 1) 行分别有两个非负整数。其中,第(i + 1) 行的两个整数表示 x_i 和 y_i。 (0 ≤ x_i ≤ w, 0 ≤ y_i ≤ h)

输出格式

　　输出文件只包括一行,其中只有一个整数,即这个屋子可能的最大边长。

样例输入

样例输出

3

样例说明

2012年清华大学计算机系推免保研上机考试

相关推荐