考场上 \(7\) 题做出来 \(4\) 题，最后几分钟才把 D 题调出来，但还是吃了不少罚时
A. Escalator Conversations
\(O(n)\) 枚举即可，对于每个人计算需要的间隔台阶数是否在 \((0,m)\) 以内以及相差高度是否是 \(k\) 的倍数
B. Parity Sort
显然，偶数和奇数是不可能产生交换操作的，而偶数之间、奇数之间可以交换无数次
那么就可以把偶数与奇数分别排序，并且用两个 set 分别记录每个偶数与奇数在原序列的位置（因为对于一个偶数，所有原序列中为偶数的位置都可以放置这个偶数，奇数同理）
排序以后，就按照储存位置的两个 set 里规定好的奇、偶位置分配来放入数字，如果相邻数为逆序对那么就无解；否则有解
时间复杂度 \(O(n\log n)\)
C. Tiles Comeback
因为只要输出是否存在可行方案，所以中间部分都不用管，只要看开头和结尾是否可行即可（因为题面要求从位置 \(1\) 开始跳，跳到 \(n\) 结束）
所以就直接计算开头块的右边界和结尾块的左边界就行了，如果这两个块相交（边界相等不算），那么无解；否则有解
还有个特判：如果开头、结尾颜色相同，那么就把这两个算成一块，统计时只要统计这一块是否能完整结束就行
时间复杂度 \(O(n)\)
D. Prefix Permutation Sums
因为整个排列是乱序的，所以前缀和不确定；但正因为它是排列，所以所有数的和加起来一定是 \(1+2+\cdots+n=\frac{n(n+1)}{2}\)
所以，对于输入的前缀和序列，如果最后一项的值 不是 \(\frac{n(n+1)}{2}\)，就意味着：
- 如果有解，那么缺少的位置一定是在最后一项后面
- 如果无解，那么在最后一项后面补上 \(\frac{n(n+1)}{2}\) 后，对应的原序列 不合法
于是就可以借助这种方法判断
如果最后一项就是 \(\frac{n(n+1)}{2}\)，那么就在前面寻找不合法的部分，并枚举数字将其变成合法的，但凡有一次无法枚举，即无解；反之有解
时间复杂度 \(O(n^2)\)，能卡过去
E. Nastya and Potions
md我光和 D 题斗智斗勇去了完全没看这道大水题
这玩意儿就是一道贼典型的记忆化搜索
记第 \(i\) 种药水的费用为 \(dp_i\)
对于 \(p_1,p_2,\cdots,p_k\)，这些药水都是可以无限拿的，所以 \(dp_{p_1}=dp_{p_2}=\cdots=dp_{p_k}=0\)
对于其他部分，\(dp_i=c_i\)
然后根据药水混合配方深搜一遍就可以了
F. Lisa and the Martians
还有另一个 0/1-Trie 的做法，但是我没看懂
为了枚举方便，首先要先排个序
设当前答案是 \(a_i,a_j(j-i>1)\)
如果 \(a_i=a_j\)，由于已经排序，所以显然也有 \(a_i=a_i+1\)
否则，它们肯定拥有最长公共前缀
也就是说，在某个位置 \(t\)，\(a_i\) 在第 \(t\) 位上是 \(0\)，\(a_j\) 在第 \(t\) 位上是 \(1\)（还是排序的缘故，所以 \(a_i<a_j\)）
由于 \(j-i>1\)，\(a_{i+1}\) 在这个位置是 \(0\) 还是 \(1\) 都可以，但在第一种情况下选择 \(a_i,a_{i+1}\) 作为答案更有利，在第二种情况下选择 \(a_{i+1},a_j\) 作为答案更有利。
时间复杂度 \(O(n\log n)\)
G. Vlad and the Mountains
又是一道连题面都没看的水题
对于山峰 \(i,j,k\) 考虑路径 \(i\to j\to k\) 的能量消耗：
\((h_j-h_i)+(h_k-h_j)=h_k-h_i\)
这玩意儿是一个极其优美的性质：只要图上结点 \(u,v\) 之间有路径连接，那么总边权就是这两者点权相减
所以直接用并查集来做就可以了