Problem 1 珠江夜游cruise

题目大意： n+1 艘船，告诉你每艘船距离终点的长度、船身的长度和最高行驶速度。在行驶的过程中不允许超越（即后面的船最多也只能船头贴着前一辆船的船尾，后以同样的速度前进）。问这些船均驶过终点需要多长时间。

第一种方法：把第 i 辆船追上第 i+1 辆船当作一个事件，显然只有 n 个事件，且第 i 辆船追上第 i+1 辆船只可能会对第 i−1 辆船追上第 i 辆船的时间产生影响，且时间一定是变小，因此可以维护船之间的距离和速度来计算事件发生时间，用堆来找出最早发生的事件，不停处理直到距离终点最远的船通过终点。同时还需要记录行驶过程中，以相同速度前进的一系列船的最前面的船的编号，和最后面的船的编号，复杂度为 O(nlogn)。

第二种方法：可以直接二分最终时间，然后从第一辆船开始递推求出每辆船的最终位置。复杂度为 O(nlogC)，也可以过。二分给定一个 mid，进行 check 的时候，我们只需要记录下来前一辆船船头最终能到达的位置-前一辆船的长度的值，然后计算当前这辆船的船头能到达的最远距离（ 在没有船挡路的情况下），然后在两者之间取一个 min 就是该船船头能到达的最终位置。递推计算最远的船能否通过终点即可。（任何一辆船达不到终点即可返回）。

第三种方法：O(n) 的做法，也是最简单的做法。最终通过终点的时候，一定是一个船后面堵着剩余所有的船，那么影响时间的就只有最前面这辆船，所以对于每一辆船，假设是它是和 0 船堵在一起的最靠前的一辆船，那么可以计算出一个值，所有的船的计算值的最大值就是答案。计算的时候一定不要忘了算上这堵在一起的一堆船的船身长度，因为最后一辆船的车头通过终点，才算结束。

Problem 2 旅行计划travelling

题目大意：给定一个任意的无向图， 问最少画几笔， 使得所有的边被画过一次且仅一次。

解法：每个连通块显然是独立的。对于一个连通块（除了单个点的），如果奇度数点个数为 k，那么至少需要 max(k/2,1)条路径。这是因为在一个无向图中，将两个度数为奇数的点连起来，就可以消去两个奇数点。所以如果一个无向图要有欧拉回路(全部点的度数全为偶数)，只要加 k/2 条边就可以了。于是乎，我们只要将一个连通块变成欧拉图，搜一遍得到路径，再将我们人为添加的边删掉，剩下的就是这个连通块的"笔画"了。

这里为什么一定变成欧拉回路而不是欧拉通路，其实这里欧拉回路和欧拉通路都是可以的，得到的答案是一样的。主要是算法实现上的问题，如果变成欧拉通路，就一定得从剩下的两个奇数点出发，终止。至于为什么这里加 k/2 条边后扫出的结果删掉多加的边就是答案，并且这个答案=max(k/2,1)呢？这是因为一个图中，我们从奇数点开始走，停止的也一定是在奇数点，那么再一遍遍不重复地从图中走出一条条类似前面地路径(奇数点开始，奇数点结束)然后我们将这些路径地终点连接下一条路径的起点(多加的边)，这样又因为每一条路径的起止点都为奇数点，一条边删去两个奇数点。所以最终把他们连成欧拉回路所需的边的数量就是 k/2。

Problem 3 基站建设station

题目大意：给你一个 8× 8 的矩阵，你需要遍历上面给定的某些格子。每次从一个点到另一个点的代价两个格子的切比雪夫距离的最大值。求最小总代价。

60分做法：状态压缩动态规划。

100分做法：不妨先考虑一维的情形。也就是说，需要放鹅卵石的格子排成一行。

容易想到，应该“先中间后两边”。更严格地说，现在要把连续的一段格子中的鹅卵石摆放完成，那么把目标位置处于最左边或者最右边的鹅卵石最后放，一定不会更差。下面稍许做些说明：不妨考虑这样一种情况，格子 L~R 中有些格子要放鹅卵石，而且格子L 和 R 一定要放（下面把目标位置为 x 的鹅卵石称为鹅卵石 x）。假如你给我一个方案，鹅卵石 L 和鹅卵石 R 都不是最后放，那么，把这个方案中鹅卵石 L、R 中后放的那一个与最后放的那个鹅卵石交换顺序，答案不会变差。也就是说，让鹅卵石 L 或者鹅卵石 R最后放是不会错过最优解的。（如图 2）

于是，一维的情况就可以使用区间动态规划，每次决策是让最左边还是让最右边的鹅卵石最后放，剩下的部分就变成了一个子问题。

回到原题。由一维的情况，自然地会有如下猜想：放鹅卵石应该“先中间后四周”。或者说，考虑一个矩形区域，$(x_1, y_1)$为左上角，$(x_2, y_2)$为右下角，那么，考虑让某一条边上的鹅卵石最后放，代价不会变大。仔细想想这也不难说明。（如图 3）

这样我们就可以进行动态规划了。枚举把哪一条边上的鹅卵石最后放，余下的便是子问题。

思考：如果题目中的距离变成曼哈顿距离，即$(x_1, y_1)$与$(x_2, y_2)$之间的距离计算公式为$$|x_1 – x_2| + |y_1 – y_2|$$怎么办？

这里稍作提示。 设点 $P_1(x_1, y_1)$， $P_2(x_2, y_2)$，令点 $P_1’$ 为$(x_1 + y_1, x_1 – y_1)$, $P_2’$ 为$(x_2 + y_2, x_2– y_2)$， 则借助恒等式$$max(|a|, |b|) = ( |a + b|, |a – b| ) /2$$可以推出 $$\begin{align*} P_1’ 与 P_2’ 间的切比雪夫距离 &= max(|(x_1– x_2) + (y_1– y_2)|, |(x_1– x_2) – (y_1– y_2)| )\\ &= |x_1 – x_2| + |y_1 – y_2|\\ &= P_1与 P_2间的曼哈顿距离 \end{align*}$$

本质上，我们进行了一次旋转坐标系的操作，可以通过图4直观地理解。

本题的原题中用的就是曼哈顿距离。为了降低难度我直接改成使用切比雪夫距离。这种曼哈顿距离与切比雪夫距离的相互转化的技巧，有时会使用到。

点评：上面采用的分析方法是，先简化问题：先思考一维的简单情形，看看是否能从中得到启发。有时题目的条件很复杂，约束很多，不知如何下手，这时适当想一想“去掉一些条件和约束，我该怎么做” ，有助于找到突破口。

写在最后

感谢 sqy 保佑 酒酿OJ 平稳运转。

OI 千万神，dhw 第一神。

膜 dhw 不规范，爆零两行泪。