本页面已浏览29次
Table of Contents
1. Do you know your ABCs?
Farmer John 的奶牛正在 "mooZ" 视频会议平台上举行每日集会。她们发明了一个简单的数字游戏，为会议增添一些乐趣。Elsie 有三个正整数 A、B和 C（\(A\le B\le C\)）。这些数字是保密的，她不会直接透露给她的姐妹 Bessie。她告诉 Bessie 七个范围在\(1-10^9\) 之间的整数（不一定各不相同），并宣称这是 A、B、C、A+B、B+C、C+A和A+B+C 的某种排列。
给定这七个整数，请帮助 Bessie 求出 A、B和C。可以证明，答案是唯一的。
输入格式（从终端/标准输入读入）：
输入一行，包含七个空格分隔的整数。输出格式（输出至终端/标准输出）：
输出 A、B和C，用空格分隔。输入样例：
2 2 11 4 9 7 9输出样例：
2 2 7分析
这道题目不难。不用暴力求解。
首先，7个数字都是正整数（题设），所以，A+B+C一定是最大的，而A、B是最小的两个。只要将这7个数字排序一下，最大的（A+B+C）减去最小的两个（A和B），就可以得到C。然后输出即可。
答案
思考
这道题并不会检测7个数字的合理性。从算法中可以看出，它假定7个数字都是合理的，从而只是简单排序，然后根据题设条件简单计算并输出。
可以进行的额外检查，判定这7个数是否合规。
2. Daisy Chains
每天，作为她绕农场行走的一部分，奶牛Bessie会经过她最喜爱的草地，其中种有N朵花（五颜六色的雏菊），编号为1…N（\(1\le N\le100\)），排列成一行。花i有\(p_i\)朵花瓣（\(1\le p_i\le 1000\)）。
作为一名崭露头角的摄影家，Bessie 决定给这些花拍些照片。具体地说，对于每一对满足\(1\le i\le N\)的花 (i,j)，Bessie 会给从花i到花j 之间的所有花（包括i和j）拍一张照。
后来Bessie查看这些照片时注意到有些照片里存在“平均”的花——一朵恰好有P朵花瓣的花，其中P等于照片中所有花的花瓣数量的平均值。
Bessie的照片中有几张存在平均的花？
输入格式（从终端/标准输入读入）：
输入的第一行包含 N
第二行包含N个空格分隔的整数$p_1 ... p_N$。输出格式（输出至终端/标准输出）：
输出存在平均花瓣数的花的照片数量。输入样例：
4
1 1 2 3输出样例：
6分析
这道题有两种解法。一种是暴力法，一种是贪心法。
暴力法
首先，一些数学基本知识。
如果我们有N朵花，基于这种拍摄方式，那么：
- 从1开始的拍法有N张；从2开始的拍法有N-1张，……从N开始的拍法有1张。
- 因此，总共有\(N+(N-1)+(N-2)+...+1=\frac{N*(N-1)}{2}\)张照片，也就是说时间复杂度是\(O(N^2)\)。
- 对于这\(N^2\)张照片，每次拍摄，我们都要检查这些照片中的每一朵花，看看它的花瓣数是不是这张照片中所有花朵花瓣数的平均数。这是一个\(O(N)\)的操作。
- 所以，这个问题的总复杂度在\(O(N^3)\)。
其次，回到题目。
如果一张照片只有一朵花，那么这张照片肯定算。（一个数的平均数就是它自己。）
同时，在样例输入中：
4
1 1 2 3- (i, j)=(1, 2)，此时花瓣数为(1, 1)，满足条件。
- (i, j)=(2, 4), 此时花瓣数为(1, 2, 3)，满足条件。
所以总共有6张照片符合要求。
暴力法的程序不难写。见如下。
贪心法
对于上面的暴力法，我们继续分析如下。
我们要拍的照片的张数是无法优化的，因为我们不想漏掉任何一种组合。但是，暴力法中的问题在于，每次拍一张照，我们要去遍历所有花的花瓣，看看是否等于平均数。这个过程在复杂度上乘上了一个N，从而使最终的复杂度来到了\(N^3\)。
一个自然的想法是，我们可以记录已经看到的花瓣数。在加入一头新的牛拍照时，更新看到的花瓣数记录，计算平均数，看看这个平均数是否已经出现在了我们的花瓣数记录中。这是可以省时间的。
Bessie这样的拍法也支持这样的做法：一张照片里如果花比较多，一定是由一张去掉最右边的花朵的照片（小照片）加上最右边的那朵花构成的。
我们可以从第i朵花开始，一朵一朵地在右边加入更多的花朵。在这个过程中，我们必须记录：
- 我们看到的花朵有哪些花瓣数？
- 总共看到了多少花瓣？
根据2这个数据，可以得到平均花瓣数，然后回到1中进行查找。
1可以用一个bool类型的数组实现，而数组的查找时间与N无关，是\(O(1)\)的时间复杂度。
整个过程，我们只要用两个循环：一个记录从哪朵花开始拍照，一个记录加上右边多少朵花。所以，基本是一个\(O(N^2)\)的复杂度。
答案
我们先给出暴力法的答案：
然后是贪心法的答案：
思考
我们可以看到，在上述两种方案中，时间复杂度差了一个量级，在数据量很大的时候，这是很关键的。有些题目（比如本题），用暴力法可以解决一些问题，但在一些极端情况下就会超时。但，贪心法在时间上有了缩短，但却有空间上的额外开销（seen这个数组）。在本题中，这个数组还不算大，因为题设规定每一朵花的花瓣数不会超过1000，所以额外开销也不大。
这是一种典型的“以空间换时间”的做法。目前的电脑内存都比较大，空间限制会比较小，所以“以空间换时间”是一种值得推荐的方式。
3. Stuck in a Rut
Farmer John 最近扩大了他的农场，从奶牛们的角度看来这个农场相当于是无限大了！奶牛们将农场上放牧的区域想作是一个由正方形方格组成的无限大二维方阵，每个方格中均有美味的草（将每个方格看作是棋盘上的一个方格）。Farmer John 的N头奶牛（\(1\le N \le 50\)）初始时位于不同的方格中，一部分朝向北面，一部分朝向东面。
每一小时，每头奶牛会执行以下二者之一：
- 如果她当前所在的方格里的草已经被其他奶牛吃掉了，则她会停下。
- 吃完她当前所在的方格中的所有草，并向她朝向的方向移动一个方格。
经过一段时间，每头奶牛的身后会留下一条被啃秃了的轨迹。
如果两头奶牛在一次移动中移动到了同一个有草的方格，她们会分享这个方格中的草，并在下一个小时继续沿她们朝向的方向移动。
请求出每头奶牛吃到的草的数量。有些奶牛永远不会停下，从而吃到无限多的草。
输入格式（从终端/标准输入读入）：
输入的第一行包含N。以下N行，每行描述一头奶牛的起始位置，包含一个字符 N（表示朝向北面） 或 E（表示朝向东面），以及两个非负整数x和y（\(0\le x \le 10^9, 0 \le y \le 10^9\)）表示方格的坐标。所有x 坐标各不相同，所有y坐标各不相同。
为了使方向和坐标尽可能明确，如果一头奶牛位于方格(x,y)并向北移动，她会到达方格 (x,y+1)。如果她向东移动，她会到达方格 (x+1,y)。
输出格式（输出至终端/标准输出）：
输出N行。输出的第i行包含输入中的第i头奶牛吃到草的方格的数量。如果一头奶牛可以吃到无限多的草，为这头奶牛输出"Infinity"。
输入样例：
6
E 3 5
N 5 3
E 4 6
E 10 4
N 11 2
N 8 1输出样例：
5
3
Infinity
Infinity
2
5分析
这道题有一定难度。直觉告诉我们，我们可以暴力求解，但如果牧场过大，数组开销会太大。
我们需要换个思路，对大牧场下的情形进行“模拟”。
我们先定义一个奶牛的结构来保存相关信息：
struct Cow {
int time_stopped; // 什么时候停下的？可以是Infinity
int x, y; // 目前在哪里？
char dir; // 方向：N或者E
};模拟的第一个重点：牛i是否会走到被牛j吃掉的草块（“交叉”）？何时走到？
根据两头牛的初始位置和朝向，假定当前时间是current_time，分别讨论如下：
- 如果两头牛的朝向一致：不可能交叉。
- 如果朝向不一致：一个朝北，一个朝东。不失一般性，我们假定i朝北，j朝东。（如果i朝东而j朝北，我们可以“交换”这两头牛。）
- 一般而言，i交叉到j需要的时间是两者y的差：
j.y-i.y，这时i走了j.y-i.y+current_time。但是，- 如果j在i的更南边：不可能交叉。如下图所示：
- 如果j在i的更南边：不可能交叉。如下图所示：
- 如果j已经停下了，而且是经过若干时间（结构中的
time_stopped）停下，那么如果i在j的右边（i.x>j.x），或者i在j的初始点左边（i.x<j.x-j.time_stopped），也不会交叉。 - 否则（j还在漫游），那么i能继续跑的情况是：如果i在j的初始点左边（如上图中j在第二象限，
i.x<j.x-current_time），或者i比j更快地跑到两者的未来交汇点(x, y)（如上图中j在第四象限），那么i可以继续吃草，而j就会停下来，也就是：i和j的x方向之差大于等于两者的y方向之差，牛i也不会停下来。
模拟的第二个重点：对于每一头牛，如何判定当前状态后的“下一个”状态（停下？漫游？）？
注意到，对于一头牛来说，在第一个模拟中，它可能与其他牛交叉，而一旦模拟中发生多次交叉，那么肯定是在“最早”的交叉发生后，这头牛就停下了。（我们假定，在一开始，所有牛都在漫游，而且永远不会停下。）
答案
完整代码如下：
分析
这道题目有一定的难度。关键在于分析清楚各种情况，并清楚我们的优先级：先要找到两头牛交叉的判定；其次是迅速调整每头牛的状态。
同时，在渐进的过程中，我们对结构的声明会越来越清楚。