2133A. Redstone?
题意
有 $n$ 个齿轮，第 $i$ 个齿轮有 $a_i$ 个齿。
现在将齿轮排成一横排，以每秒 $1$ 圈的速度转动最左侧的齿轮；对于其他齿轮，设该齿轮有 $a_i$ 个齿，它左侧的齿轮有 $a_{i - 1}$ 个齿，左侧齿轮转速为 $rev_{i - 1}$，则该齿轮的转速为 $\frac{a_{i - 1}}{a_i} \cdot rev_{i - 1}$ 圈每秒。
请问存不存在一种排列方式使得最右侧的齿轮每秒转 $1$ 圈？
题解
设第 $i$ 个齿轮的齿的线速度为 $v_i$，则 $v_i = a_i \cdot rev_i$。
根据题中齿轮转速公式，可得：$v_{i + 1} = a_{i + 1} \cdot \frac{a_i}{a_{i + 1}} \cdot rev_i = a_i \cdot rev_i = v_i (i < n)$，即 $v_1 = v_2 = v_3 = \dots = v_n$。
什么时候有 $rev_1 = 1 = rev_n$ 呢？容易证明，当且仅当 $a_1 = a_n$ 时两齿轮转速相等。
那么排列方式就是把任意一对齿数相等的齿轮放在两端，剩余的齿轮在中间任意放置。若没有齿数相等的齿轮，则没有排列方式。
答案显而易见，判断是否有齿数相等的齿轮。
参考代码
O(n^2) 做法
O(n log n) 做法
在 C++ 中，unique() 函数会返回一个迭代器，指向去重后的数组末尾，我们通过这个迭代器可以计算出新数组的长度，进一步我们可以判断数组长度是否有减少，若有减少，则说明有齿数相等的齿轮。
O(n) 做法 1
由于数据范围足够小，所以完全不会产生哈希碰撞，set 的单次操作复杂度为 $O(1)$。
O(n) 做法 2
由于数据范围足够小，所以我们可以记录每个齿数出现的次数。
2133B. Villagers
题意
无向图 $G$ 中有 $n$ 个点，每个点有点权 $g_i$，初始状态下图中没有边。
可以进行以下操作任意次：
- 选取两个点 $i$ 和 $j$；
- 支付操作成本 $max(g_i, g_j)$；
- 使两个点的点权降低 $min(g_i, g_j)$；
- 添加一条边连接 $i$ 和 $j$。
输出使 $G$ 成为连通图所需的最小成本。
题解
发现每次操作后，两个点中点权较小的点的点权会变为 $0$，而连接两个点权为 $0$ 的节点是没有成本的。因此，我们只需要记录所有的点都经过一次操作所需成本，而后续合并是无成本的。
排序 $g$ 数组，可以证明一种最优方案为连接 $n$ 与 $n - 1$、$n - 2$ 与 $n - 3$……
证明：考虑在 $n \geq 4$ 情况下连接 $n$ 与 $x$、$n - 1$ 与 $y$（$x, y \in [1, n - 2]$）：
- 这两组连接的操作成本为 $g_n + g_{n - 1}$；
- 如果换为连接 $n$ 与 $n - 1$、$x$ 与 $y$，操作成本为 $g_n + max(g_x, g_y)$；
- 由于 $max(g_x, g_y) \leq g_{n - 1}$，后者的操作成本小于前者，应当使用后者的连接方式；
- 问题可以无后效性地转移到 $n - 2$。
特别地：
- $n = 3$ 时，连接 $2$ 与 $3$、$1$ 与 $2$，操作成本为 $g_1 + g_3$，为最小值。
- $n = 2$ 时，连接 $1$ 与 $2$，操作成本为 $g_2$，为最小值。
- 转移不到 $n = 1$ 的情况。
最优方案的总成本为 $g_n + g_{n - 2} + g_{n - 4} + \dots$。
参考代码
2133C. The Nether
题意
交互题。
一个未知的有向图有 $n$ 个点，请在至多 $2 \cdot n$ 次查询中，找出图中最长路径。
每次操作时，你需要输出一个点 $x$ 与一个包含任意多点的集合 $S$，满足 $x \in S$，评测机将返回从 $x$ 出发只经过 $S$ 中的点的路径的最大长度。
题解
首先，我们需要找出最长路径的起点，可以通过遍历所有点，查询从该点 $i$ 出发的最长路径长度（记作 $f_i$），记 $f_i$ 最大的 $i$ 为 $ans_1$，最大的 $f_i$ 记作 $len$。
接着，我们要找出最长路径中第 $2$ 个点，这个点显然必须满足 $f_i = len - 1$，而且 $ans_1$ 到 $i$ 必须有连边。所以我们需要遍历所有满足条件的点，并查询从 $ans_1$ 出发只经过 $i$ 的最长路径长度，若是 $2$，则表明 $ans_1$ 到 $i$ 有连边，可以选作 $ans_2$。
循环地找出最长路径中其他的点，最后输出 $ans$ 即可。
因为每个节点至多满足一次 $f_i = len - i + 1$，所以第二部分至多执行 $n - 1$ 次查询。总共至多执行 $2n - 1$ 次查询，满足题目要求。
参考代码
2133D. Chicken Jockey
题意
有 $n$ 个怪物，这些怪物上下叠在一起，其中怪物 $1$ 在最底部，怪物 $n$ 在最顶部，每个怪物有 $h_i$ 的初始生命值。
Steve 可以攻击任意怪物造成 $1$ 点伤害。如果一个怪物的剩余生命值小于等于 $0$，它将会死亡，然后它上方的所有怪物将会摔落成为新的一叠，新的一叠中的最底部的怪物会受到摔落伤害，摔落伤害是可以致命的，因此可能触发连锁反应。
摔落伤害：等同于其在摔落前压着的怪物数（被击杀的那个也算）。
请问最少需要多少次攻击，使得所有怪物都死亡？
题解
发现：
- 一个怪物至多受到一次摔落伤害，因为受到摔落伤害说明它是一叠的最底部，不可能再摔落了；
- 怪物 $i$ 有两种方式死亡：直接击杀或者摔落受到 $i - 1$ 点伤害。
使用 DP 解决：f[i] 表示击杀前 $i$ 个怪物需要多少次攻击。
根据发现的规律，可以得到状态转移方程：
- 让前 $i - 1$ 个怪物全部死亡，然后受到 $1$ 点摔落伤害，最后攻击 $h_i - 1$ 次击杀，
f[i] = f[i - 1] + h[i] - 1； - 击杀第 $i - 1$ 个怪物，然后受到 $i - 1$ 点摔落伤害，并攻击直至击杀，最后让前 $i - 2$ 个怪物死亡，
f[i] = f[i - 2] + h[i - 1] + max(0, h[i] - (i - 1))。