一些杂题，主要是贪心（模拟费用流）和构造，以及一些思维题。（部分来自 zzz 课件）
Bohater
有 $n$ 只怪物，为了打败第 $i$ 只怪物，你会下降 $d_i$ 的血量。击败怪物后，会掉落回复 $a_i$ 生命值的血药。任何时刻血量都不能小于等于 $0$。问是否存在一种打怪顺序使得自身不死掉。
数据范围：$n \le 10^5$。
简单贪心，我们把怪物分为两种类型：击败后加血和击败后扣血。对于第一种怪物，我们可以采取先打 $d_i$ 小的，因为我们需要攒血量去打 $d_i$ 大的怪物。对于第二种怪物，我们倒着考虑。我们这样就可以发现，倒着看时，$d_i$ 为血药，$a_i$ 为减小的血量，为了使得血量不小于 $0$，我们需要把减少的血量小的放前面，在原顺序中也就是把 $a_i$ 小的放后面。
不离
有 $2$ 个属性 $x$ 和 $y$ 以及 $n$ 件装备，第 $i$ 件装备需要在 $x \ge a_i, y \ge b_i$ 时才能穿上，穿上后会使 $x$ 加上 $c_i$，使 $y$ 加上 $d_i$。如果想让所有装备都穿上，最初的 $x$ 最小应该是多少。在 $x$ 最小的前提下，$y$ 最小是多少。
数据范围：$n\le 10^5$。
我们先考虑 $x$。我们可以先把装备按 $a_i$ 排序，一件一件穿。当 $x$ 无法达到 $a_i$ 时，我们就提升初始的 $x$，把这段差值补上。这样就求出了最小的初始 $x$。
我们再考虑 $y$。既然有了初始的最小 $x$，我们就可以模拟穿装备的过程。一件一件穿，当力量值大于 $a_i$ 时，我们把这件装备扔到按 $b_i$ 排序的堆里。当力量值小于 $a_i$ 时，我们再从堆里一件一件拿装备穿，过程和求 $x$ 的过程一样。由于 $x$ 是我们求出的最小解，因此一定有解。
专业网络
有 $n$ 个人，可以花费 $b_i$ 元和这个人成为朋友，也可以在朋友数超过 $a_i$ 时和它成为朋友。询问和这些人成为朋友的最小花费。
数据范围：$n\le 2\times 10^5$。
我们考虑能够最多节约多少钱。我们先把所有人按照 $a_i$ 排序，这时我们发现正着考虑不太好，因为我们花钱一定是买 $a_i$ 更大的，因此我们从后往前考虑。我们先认为所有人都是花钱买的，我们遇到一个人先把它扔到堆里，同时把他的钱节约下来，让他成为不通过花钱交上朋友的人。如果我们发现当前 $a_i$ 要大于现在买的人数，那我们就取出堆顶，把他买下来。这样就完成了。
排列鞋子
有 $n$ 双鞋子，分左右鞋，放在编号为 $0\sim 2n-1$ 的位置上。我们要求最终的序列为：编号 $2i$ 位置上的鞋子是左鞋，编号为 $2i+1$ 的位置上的鞋子是右鞋，并且编号 $2i$ 和 $2i+1$ 的位置上的鞋子的大小相等。每次可以交换相邻的两只鞋子，问最少交换多少次可以满足上面的条件。
数据范围：$n\le 10^5$。
我们可以从右往左扫这个序列，遇到没有用过的鞋子就在它左边找到和它配对的，把那只鞋子移过来即可。我们来证明一下这个算法的正确性。
首先，如果我们要把这两只鞋子移动到一起，如果最终移动到的位置在这两个鞋子之间，那么操作次数不变。我们考虑对其他鞋子的影响。首先对左半部分的鞋子不会有影响，它们的位置不变。而对于在这两个鞋子之间的鞋子 $x$，如果与它配对的鞋子在最终移动到的位置的右边，则操作数不变，如果在最终移动到的位置的左边，则操作数会增加。则我们需要尽可能减少这样的情况出现。而移动到最右端时这样的情况就会变为 $0$。因此这样是最优的。
这样就可做了。用一个树状数组统计答案即可。
Buy Low Sell High
已知接下来 $n$ 天的股票价格，每天你可以买进一股股票，卖出一股股票，或者什么也不做。最终最多能赚多少钱。
数据范围：$n\le 3\times 10^5$。
模拟费用流开始
本题很容易建出费用流模型。见下图。
其中源点向每天连流量为 $1$，费用为 $-c_i$ 的边，每天向下一天连流量为 $+\infty$，费用为 $0$ 的边，每天向汇点连流量为 $1$，费用为 $c_i$ 的边。每新加进来一天就会多增加三条边。我们考虑增加了这三条边会对网络产生什么影响。见下图。
（图二中为将负环消掉，也是费用流中的一个算法）
我们可以发现，新一轮增广只会选择之前没有选择的一天来买股票，或者反悔掉之前卖出的一股股票来现在卖。这样就可以开一个堆维护了。
数据备份
长度为 $n$ 的序列，要求选 $k$ 个数，要求这 $k$ 个数不能相邻，求选出的数最大总和。
数据范围：$n\le 10^5$。
本题也是比较经典的模拟费用流例题。我们先把费用流模型建出来，见图一。
我们这里把数字与数字之间的间隙看作点，把数看作边。我们考虑一次增广的情况，见图二。可以发现，单次增广会把一段区间的状态全部取反，同时这段区间必须满足 0 101...101 0，即两边都不选，并且中间选和不选交替。我们还能发现，这样一次增广后，会把三段区间变为一段区间。用堆和链表维护即可。
我们也可以从贪心的角度来说明这个结论。每次的决策必然是选择最小的，或者是最小值的两边的值。我们可以先选择上最小值，然后删除这三个数，加入值为 $a_{i-1}+a_{i+1}-a_i$ 的数。这样如果下次再选择到这个数，就代表着我们反悔了。代码和上面的做法完全一样。
另外，由于本题建出了费用流模型，我们可以用 wqs 二分来解决，这里不再说明。
Olympiad in Programming and Sports
有 $n$ 个学生，每人有两种技能，分别是 $a,b$ 表示编程能力和运动能力。你需要将他们分为两个团队分别参加编程比赛和体育比赛，编程团队有 $p$ 人，体育团队有 $s$ 人，一个学生只能参加其中一项。每个团队的力量是其成员在对应领域能力总和，两个团队的实力和最大是多少。
数据范围：$n\le 3000$。
本题依旧可以建出费用流模型。
图一即为网络。图二、三、四都为单次增广可能的路径，我们可以选择一个没有被选择的人来让他选择编程或者运动，或者是让它顶替掉一个选择过别的运动的人。我们可以按照这个想出反悔贪心策略：开三个堆来维护 $a_i, b_i, b_i-a_i$。一开始先选择编程能力最大的，然后每轮不断取出最大的 $b_i$ 和最大的 $a_i+(b_i-a_i)$，重复 $s$ 轮即可。
Raffles
有 $n$ 个奖池，第 $i$ 个奖池有 $p_i$ 元奖金，已经有 $l_i$ 张彩票押在上面。现在有 $t$ 张彩票，你要把这些彩票押到奖金池中，并且在每个奖金池中你押的彩票数不能超过原有的彩票数。如果你在第 $i$ 个彩票池押了 $t_i$ 张彩票，你中奖的概率就是 $\frac{t_i}{t_i+l_i}$，中奖会获得该彩票池的所有奖金。一共有 $q$ 次事件，每次事件会使一个彩票池中 $l_i$ 加一或减一。每次事件后输出获得奖金的最大期望值。
数据范围：$n, q, t\le 2\times 10^5$。
我们考虑往某个池子里放一个彩票增加的期望钱数。
$$
\begin{aligned}
\frac{t_i+1}{t_i+1+l_i}-\frac{t_i}{t_i+l_i} &=\frac{(t_i+1)(t_i+l_i)-t_i(t_i+1+l_i)}{(t_i+1+l_i)(t_i+l_i)} \
&=\frac{l_i}{(t_i+1+l_i)(t_i+l_i)}
\end{aligned}
$$
我们再考虑如果没有修改操作如何求出答案。我们只需要维护两个堆，一个存放当前的决策，一个存放下一次的决策（就比如当前池子里押了 $x$，下一次决策即为 $x+1$）。每次拿出下次决策收益最大的，循环 $t$ 次即可。
当有修改时，我们可以先将其在堆中的信息更新一遍，然后从下一次决策中取出最大的和当前决策进行比较，如果更大就替换。这样复杂度其实是对的，因为我们每次重新跑一遍只会引起一张彩票的变化。
Cardboard Box
$n$ 个关卡，对每个关卡，你可以花 $a_i$ 代价得到一颗星，也可以花 $b_i$ 代价得到两颗星，也可以不玩。问获得 $w$ 颗星最少代价。
数据范围：$n\le 3\times 10^5$。
我们考虑从有 $i$ 颗星变为 $i+1$ 颗星的方法：
- 直接选一个之前 $0$ 颗星的关卡增加一颗星，代价 $a_i$。
- 选已经选了一颗星的关卡变为两颗星，代价 $b_i-a_i$。
- 让之前一颗星的关卡变为零颗星，一个零颗星的关卡变为两颗星，代价 $b_i-a_j$。
- 让之前两颗星的关卡变为一颗星，一个零颗星的关卡变为两颗星，代价 $b_i-b_j+a_j$。
我们分类讨论完就可以直接开五个堆分别维护 $a_i,b_i, -a_i, b_i-a_i, -b_i+a_i$。每次从上面的决策中选择最大值即可。
序列
给定两个长度为 $n$ 的正整数序列 ${a_i}$ 与 ${b_i}$，确定两个长度为 $K$ 的序列 ${c_i}, {d_i}$，其中 $1 \leq c_1 < c_2 < \cdots < c_K \leq n , 1 \leq d_1 < d_2 < \cdots < d_K \leq n$，并要求 ${c_1, c_2, \cdots , c_K} \cap {d_1, d_2, · · · , d_K}\geq L$。目标是最大化 $\sum^{K}{i=1} a{c_i} +\sum^{K}{i=1} b{d_i}$。
数据范围：$n\le 2\times 10^5$。
我们建出费用流模型。
可以发现，只要弧 CD 有流量，那么一定会去选择流它。当弧 CD 没有流量后，我们有如下选择：
- 选择相同下标的数字。
- 找一个可用的左部点和一个左部点被选择的右部点。
- 上面的对称情况。
模拟即可，同时当我们第二或第三种情况后某个点的左部点和右部点都被选择，则可以为弧 CD 增加一点流量。也就是上图中的图四。
Raper
你需要生产 $k$ 张光盘。每张光盘都要经过两道工序：先在 A 工厂进行挤压，再送到 B 工厂涂上反光层。
你知道每天 A、B 工厂分别加工一张光盘的花费。你现在有 $n$ 天时间，每天可以先送一张光盘到 A 工厂（或者不送），然后再送一张已经在 A 工厂加工过的光盘到 B 工厂（或者不送），每家工厂一天只能对一张光盘进行操作，同一张光盘在一天内生产出来是允许的。我们假定将未加工的或半成品的光盘保存起来不需要费用。求生产出 $k$ 张光盘的最小花费。
数据范围：$n, k\le 5\times 10^5$。
我们建出费用流模型。
我们先用 wqs 二分消去 $k$ 的限制，这时，我们的模型就变为了最小费用可行流（即花费最小的费用跑出来的流，只需要不断增广至单次费用大于 $0$）。我们就可以像前面的一道题一样开始模拟费用流。
所以为什么加个 wqs 二分就能上黑
IIIDX
Konano 接到了一个任务，他需要给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有 $n$ 首曲目，每首曲目都会有一个难度 $d$，游戏内第 $i$ 首曲目会在玩家 Pass 第 $\left\lfloor \frac i k \right\rfloor$ 首曲目后解锁（$\left\lfloor x \right\rfloor$ 为下取整符号）若 $\left\lfloor \frac i k \right\rfloor = 0$，则说明这首曲目无需解锁。Konano 的工作，便是安排这些曲目的顺序，使得每次解锁出的曲子的难度不低于作为条件需要玩家通关的曲子的难度，即使得确定顺序后的曲目的难度对于每个 $i$ 满足 $d_i \geq d_{\left\lfloor \frac ik \right\rfloor}$。同时保证最终字典序最大。
数据范围：$n\le 5\times 10^5$。
本题如果所有数都互不相同，那么很好做，只需要贪心地往最小的子树内放最大的就行。而当有重复时，这个做法就行不通了，我们需要换新的思路。
我们先把 $d$ 排序离散化了，设 $f(x)$ 为大于等于 $x$ 的数的个数，一个位置能被填上 $x$ 当且仅当 $siz_u \ge f(x)$。而当它填上 $x$ 后，$1\sim x$ 这些位置都会减去 $siz_u$，这个操作可以称作预定。由于要求字典序最大，我们可以编号从小到大考虑，每次在线段树上二分出第一个 $siz_u\ge f(x)$ 的位置，将前面的位置全部减去 $1$。
这里有一点要注意，就是进入子树时，我们需要将父亲的更改撤销掉，而再新加上子树的修改。这样也很好理解，就是你的父亲已经给子树全部占了座了，但是到你该坐的时候座位还是被占着的，这样就不行了。
没有题目
大小为 $n$ 的 01 矩阵 $A$，满足 $A^k = 0$，求 $A$ 里面最多有多少个 $1$。
数据范围：$n \le 10^{18}, k \le 1145141919810$
我们可以把矩阵看作邻接矩阵，这样就可以变成一个图论问题。我们思考邻接矩阵的幂次是什么意义：经过 $k$ 条边后从 $i$ 走到 $j$ 的方案数。为了让它全为 $0$，我们只需要构造一张 DAG，其中最长链不超过 $k$ 即可。
具体点说，我们可以把所有点均匀分成 $k$ 部分，部分内部不连边，剩下的边全部连上。这样就满足了边数最多且最长链不超过 $k$。
Complicated Computations
求一个数列的所有连续子序列的 mex 值的 mex。
数据范围：$n\le 10^5$。
考虑枚举 $\mathrm{mex}$，观察是否该值满足在所有不出现它的区间内的 $\mathrm{mex}$ 不为它。如果对于所有的区间都是这样，我们就可以判断它是 $\mathrm{mex}$。
我们可以维护一个 $lst_i$，表示该值在我们扫描的过程中上次出现的位置。当我们扫到 $x$ 时，我们检查是否有 $\min_{i=1}^{x-1}{lst_i }\le lst_x$。如果成立，则证明 $x$ 在该区间不为 $\mathrm{mex}$。这样就能标记出所有的值。
时间复杂度 $O(n\log n)$。
阿狸和桃子的游戏
阿狸和桃子正在玩一个游戏，游戏是在一个带权图 $G=(V, E)$ 上进行的，设节点权值为 $w(v)$，边权为 $c(e)$。游戏规则是这样的：
阿狸和桃子轮流将图中的顶点染色，阿狸会将顶点染成红色，桃子会将顶点染成粉色。已经被染过色的点不能再染了，而且每一轮都必须给一个且仅一个顶点染色。
为了保证公平性，节点的个数N为偶数。
经过 $\frac{n}{2}$ 轮游戏之后，两人都得到了一个顶点集合。对于顶点集合 $S$，得分计算方式为
$$
\sum_{v \in S}w(v) + \sum_{e=(u,v)\in E \land u,v\in S}c(e)
$$
由于阿狸石头剪子布输给了桃子，所以桃子先染色。两人都想要使自己的分数比对方多，且多得越多越好。如果两人都是采用最优策略的，求最终桃子的分数减去阿狸的分数。
数据范围：$n\le 10000, m\le 100000$。
由于最终要求的是分数之差，因此我们可以把边权拆成两半分到点权上。这样做的话，当两个人分别选了一条边的两个点时，做差之后边权下放到的点权就抵消了。而当一个人选了一条边的两个点时，边权由于算到两个点里了，也会加上边权。因此拆边权后贪心模拟即可。
东兴保卫战
有一颗 $n$ 个节点的树，一开始每个节点都没有军队。现在 $A, B$ 两个人轮流选择一个没有放置军队的点放军队，直到所有点被占领。设 $a$ 为 $A$ 人所占领的点形成的连通块数量，$b$ 为 $B$ 所占领的点形成的连通块数量。$A$ 先手，$A$ 想要让 $a-b$ 最大，$B$ 想让 $a-b$ 最小。求都采用最优策略的情况下，$a-b$ 的最小值。
数据范围：$n\le 100000$。
我们考虑一个结论：在树中，设 $t$ 为连通块数，则 $|V|-|S|=t$。有了这个结论，我们就可以按照上一题的思路，点权设为 $1$，边权设为 $-1$ 即可。
Boxes
$n$ 个数字 $a_i$（顺时针给出）构成一个环，每次可以从一个起点出发顺时针给这个环依次 $-1$、$-2$ …. $-n$。问是否存在一种方案使得能把所有数恰好都减成 $0$。
数据范围：$n\le 10^5, a_i\le 10^9$。
我们考虑区间加等差数列这个操作，这样会导致差分数组中有一个数减去 $n-1$，剩下的数全部加 $1$。我们设 $c=\frac{n(n+1)}{2}$，即每次操作减少的值，显然一个存在方案的必要条件是：$\sum a_i \bmod c = 0$。
我们再设 $M=\frac{\sum a_i}{c}$，即一共操作的次数，$m_i$ 为该点进行减 $n-1$ 操作的次数，$d_i$ 为差分数组，则有：
$$
\begin{aligned}
d_i & = (M-m_i)-(n-1)m_i\
m_i&=\frac{M-d_i}{n}
\end{aligned}
$$
当 $m_i$ 为非负整数时有解。
Decrementing
黑板上写着 $n$ 个整数。第 $i$ 个整数是 $a_i$ ，它们的最大公约数为 $1$ 。
A 和 B 将使用这些数来玩一个游戏。A 在这个游戏中是先手，他们将轮流进行以下操作（以下两步相当于一次操作）：
- 选择黑板中大于 $1$ 的一个数，将其减 $1$ 。
- 此后，将黑板上所有数全部除以所有数的最大公约数。
当黑板上的数全部为 $1$ 时，不能再进行操作的人就失败了。两人都选择最好的方式行动，请求出哪边会最终胜利。
数据范围：$1\le n\le 10^5, 1\le a_i\le 10^9$。
首先没有除以 $\gcd$ 的操作时，我们可以通过奇偶性来判断谁胜。而带上除以 $\gcd$ 操作时，可能就会翻盘。由于只有除以偶数的 $\gcd$ 才可能会改变和的奇偶性，我们肯定要对奇数和偶数下手。下面进行一个分类讨论：
- 当出现 $1$ 时，就相当于没有第二个操作了，直接判断奇偶性。如果场上有奇数个偶数，则先手必胜，否则后手必胜。
- 当场上有奇数个偶数时，先手只需要保持住当前的局面即可。先手可以取走一个偶数的 $1$，而后手无论如何取也会使得偶数的数量回归奇数。先手必胜。
- 当场上有偶数个偶数，且奇数的数量大于 $1$ 时，上面的情况就会转到后手，因此后手必胜。
- 而当场上仅有一个奇数，有偶数个偶数时，先手就可能可以翻盘。先手可以取走奇数，这时所有的数都会除去一个偶的 $\gcd$，剩下的摊子就留给后手去管。
这样前三个操作都是直接结束，最后一个操作会使所有数除以至少 $2$，求 $\gcd$ 的复杂度为 $O(\log n)$。因此复杂度为 $O(n\log^2 V)$。
Modulo Matrix
构造一个 $n\times n$ 的矩阵. 要求:
- 所有元素互不相同。
- 满足 $a_{i,j}\leq 10^{15}$。
- 对于任意两个相邻的数字 ，$\max(x,y)\bmod \min(x,y)$ 都相等，且均为正整数。
可以证明方案一定存在。
数据范围：$n\le 500$。
由于是相邻的数字去取模，我们可以先构造斜线中填的数字，最后构造填数字后中间的数字。一个想法是周围四个格子中全部放质数，中间的格子放旁边质数的 $\operatorname{lcm}+1$。但是这样出现的值的级别是 $O(n^8)$，无法通过。
我们考虑优化填数。我们可以这样填：一部分质数从左下到右上填，一部分从右下到左上填，交叉的部分就填乘积。可以看下图：
这样就能把填的数字控制在 $O(n^4)$ 级别，再调整一下质数的顺序即可通过。
Distance Sums
给出 $n$ 个互不相同的数 $d_i$，表示树上的节点 $i$ 到其他所有点的距离和。请判断是否存在这样一棵树，其中每条边的长度均为 $1$。若存在请输出一种方案，否则输出 -1。
数据范围：$1 \leq n \leq 10^5$，$1 \leq d_i \leq 10^{12}$。
显然的一个结论是：$d_i$ 最小的点为重心，$d_i$ 最大的点是叶子。我们就可以从叶子开始构造，首先先找出最大的点，它的 $siz$ 显然是 $1$。根据树形 dp 的公式：$d_v=d_u+n-2siz_v$，我们就可以反推出它父亲的 $d$ 值，查询即可。同时记得给父亲加上它的 $siz$。这样循环 $n-1$ 次即可构建出整颗树。
但是这样我们算的只是 $d$ 的差值，我们还需要检验 $d$ 是否和题目中给出的相同。直接从重心跑一遍 $dfs$ 比较即可。
赶路
给定二维平面内的一些点，要寻找一个排列 $p$ 使得按照这个排列走，形成的线段不会相交。其中 $p_1=1, p_n=n$。
数据范围：$n\le 500$。
有意思的题。
我们假设一定有解。设 $solve(l, r)$ 为走 $[l, r]$ 这段区间的点的方案。我们随机选择一个点 $k$，和 $l$ 连个线，把平面分成两半，我们可以沿着一半走到 $k$，然后再从另一半走到 $r$。而至于怎么走，交给剩下的，因为我们假定一定有解，而分成的两半又不相交。
Double Knapsack
给你两个可重集 $A, B$，$A, B$ 的元素个数都为 $n$，它们中每个元素的大小 $x\in [1,n]$。请你分别找出 $A, B$ 的子集，使得它们中的元素之和相等。
数据范围：$n\leq 10^6$。
北京高考考 *3000 是吧
我们可以把集合中的子集和看作是一段序列的子段和，我们通过下面的证明我们可以证明这样做是一定有解的。
我们设 $A$ 集合的前缀和为 $suma$，$B$ 集合的前缀和为 $sumb$。我们先假设 $sumb_n\ge suma_n$，那么对于所有 $0\le i\le n$，我们都可以找到一个恰好小于等于 $sumb_i$ 的 $suma_{i’}$，这里的恰好小于等于的意思就是 $suma_{i’}\le sumb_i< suma_{i’+1}$。
由于 $a_i$ 都是小于等于 $n$ 的，那么我们就可以得到 $0\le sumb_i-suma_{i’}\le n-1$，一共有 $n$ 种可能，但是我们的 $i$ 的取值一共有 $n+1$ 种。由于鸽巢原理，我们可以得到一定会存在一组 $(i, j)$ 满足 $sumb_i-suma_{i’}=sumb_{j}-suma_{j’}$。
我们移项可以得到 $sumb_{i}-sumb_{j}=suma_{i’}-suma_{j’}$，也就对应着一段区间的和，至此构造完成。
Swedish Heroes
有一个长度为 $n$ 的序列，你要进行恰好 $n-1$ 次操作，每次操作你需要选择连续的两个数 $a_i,a_{i+1}$，然后从序列中删掉这两个数，并将 $-(a_i+a_{i+1})$ 插回到原位置。你需要让所有操作结束后序列剩下的唯一一个数最大，输出这个值。
数据范围：$n\le 10^5$。
一个比较显然的性质是：答案一定是 $a$ 序列所有数加加减减得到的，更严谨地说，$a$ 序列中每个数对答案的贡献取决于它在答案中的正负号。
因此我们可以考虑什么样的正负号排列才是合法的。我们统计一下 - 的数量 $p$, + 的数量 $q$，我们可以发现一个规律：$2p+q \equiv 1 \pmod{3}$。
证明：显然对于 $n=1,2,3$ 的情况都成立，考虑当长度为 $n$ 时的情况：
每个情况一定都是两种合法情况的组合，那么：
$$
\begin{aligned}
-[(2p_1+q_1)+(2p_2+q_2)] &\equiv -(1+1) \pmod{3} \
&\equiv 1 \pmod{3}
\end{aligned}
$$
但是还有一种情况：+-+-+-+-......。这种情况是不合法的。所以我们还要考虑上这点。
想到这个性质之后我们就可以开始 dp 了，我们设 $f[i][j][k][u]$ 表示当前考虑到第 $i$ 个数，$2p+q$ 在模 $3$ 意义下为 $j$，上一个符号为 $k$，是否出现了两个相同符号相邻 $u$。
状态设计出来后就可以开始 dp 了。
$$
f[i+1][(j+2)\bmod 3][0][u|(k==0)]\leftarrow f[i][j][k][u]-a_{i+1}
$$
$$
f[i+1][(j+1)\bmod 3][1][u|(k==1)]\leftarrow f[i][j][k][u]+a_{i+1}
$$
时间复杂度 $O(n)$。
AquaMoon and Wrong Coordinate
有 $n$ 个人和 $k$ 个间隔相同时间的时刻，每个人都向正方向做匀速直线运动。给出每个时刻（$0 \sim k - 1$）的所有人的坐标集合（无序），在这 $nk$ 个数中有一个数是错误的，找出这个错误的数并将其改正。
数据范围：$5 \le n \le 1000$，$7 \le k \le 1000$。
我们可以考虑所有人的速度都是不变的，因此每个时间刻之间的坐标和之差是一定的。形式化的，我们可以写成下面的式子：
设 $f_t=\sum \limits_{i=1}^n(x_i+v_it)$，则
$$
\begin{aligned}
f_{t+1} &= \sum \limits_{i = 1}^n(x_i+v_i(t+1))\
&=\sum \limits_{i=1}^n(x_i+v_it)+\sum \limits_{i=1}^nv_i\
&=f_t+\sum \limits_{i=1}^n v_i
\end{aligned}
$$
我们就可以用这个性质找到哪一列出现了问题。但是这无法定位到哪个数。因此我们需要再次动用人类智慧。
我们设 $s_t=\sum \limits_{i=1}^n (x_i+v_it)^2$。那么我们再次作差，展开就可以得到下面的式子：
$$
s_{t+1}+s_{t-1}-2s_t=\sum \limits_{i=1}^n 2v_i^2
$$
然后枚举即可。时间复杂度 $O(n)$。
Largest Smallest Cyclic Shift
你有 $a$ 个 a，$b$ 个 b，$c$ 个 c。要求用这 $a+b+c$ 个字母拼接成一个字符串，使得这个字符串的最小表示法在所有能拼成的字符串中最大。
数据范围：$a+b+c \le 50$。
算法流程比较简单：
- 将所有字符串存下来。
- 找到这些字符串中最小的和最大的，拼接到一起后插入，然后删除原来的两个字符串。
- 重复 2 操作，直到只剩一个字符串为止。
证明：考虑数学归纳法，假设当你有三个字符串 $s_1, s_2, s_3$（假设 $s_1 < s_2 < s_3$）时，拼接的最优方案为 $s_1 s_2 s_3$ 成立，那么当我们有一个串 $s_1s_2\cdots s_k$ 时，有一个另外的字符串 $s_{k+1}$（$s_1<s_2<\cdots < s_{k+1}$），那么我们把后面 $s_2s_3\cdots s_k$ 看作一个整体，即为 $s$，那么易知 $s<s_{k+1}$。那么我们可以得到最大的字符串即为 $s_1 s_{k+1} s$。
而当最小的情况（$1$ 个 a，b，c）时，易证该情况成立。
因此我们上面的算法正确。
当然这里还有一点漏洞，就是我们必须保证集合中的所有字符串都为最小表示法。而我们的算法中最小和最大拼接的时候就可以保证这一点性质。因此可以这么做。
用 multiset 就可以做。时间复杂度 $O((a+b+c)\log (a+b+c))$。
Strange Sorting
对一个长度至少为 $d$ 的字符串（下标从0开始），定义 d-sorting 的排序方式为，循环 $i$ 从 $0$ 到 $(d-1)$，将字符串中下标 $\bmod\ d$ 为 $i$ 的字符按原顺序取出来依次加到末尾。
给定长度为 $n$ 的字符串，$m$ 次操作，每次将所有长度为 $k$ 的子串按左到右的顺序进行一次 d-sorting，每次操作后输出当前串。
数据范围：$m\times n\le 10^6$。
我们发现一次操作我们相当于是固定一个长度为 $k$ 的滑动窗口向右划，同时在窗口内进行一次 sorting。我们可以把 sorting 的过程看作是一个置换。我们发现每次向右移动窗口太麻烦，我们考虑把窗口固定，让字符串移动。
我们可以再定义一个置换来让字符串向左移动一位。这样我们只需要把 sorting 的置换和这个左移置换复合，然后循环做 $n-k+1$ 次即可。最后别忘了消除左移的影响。
时间复杂度 $O(n\log n)$。
Similar Sets
对于两个序列 $A,B$，如果存在两个不同的整数 $x,y$ 满足 $x,y\in A$ 且 $x,y\in B$，就说 $A,B$ 是“相似”的。
给定 $k$ 个序列，输出一对“相似”序列，或告知无解。
数据范围：$\sum n\le 2\times 10^5$。
我们先从暴力入手。很容易就可以想到两个暴力：
- 固定一个序列，看其他的序列是否有和它有两个相同的元素。时间复杂度 $O(n\times k)$ 。
- 枚举二元组 $(u, v)$，看是否有两个序列会产生相同的二元组。时间复杂度 $O(\frac{n^2}{k})$。
我们直接进行一个根号分治。我们让长度大的序列进行第一个暴力，长度小的序列进行第二个暴力即可。阈值取 $\sqrt n$，时间复杂度 $O(n\sqrt n)$。
Minimum Path
给定一个包含 $n$ 个点，$m$ 条带权无向边的图，保证这个图没有自环与重边。点编号为 $1$ 到 $n$，第 $i$ 条边连接编号为 $u_i,v_i$ 的点，有权值 $w_i$。
我们规定若一条路径所包含的边边集为 $E$，那么这条路径的权值为 $\sum_{i\in E}w_i-\max_{i\in E}w_i+\min_{i\in E}w_i$。
现在你需要求出对于所有整数 $i$ 满足 $2\leq i\leq n$，从编号为 $1$ 的点到编号为 $i$ 的点所有路径权值的最小值。
数据范围：$2\leq n\leq2\times10^5,1\leq m\leq2\times10^5;$
我们发现我们要求的是一个最小值，我们考虑放缩一下。我们把减去 $\max w_i$ 放缩为在这条路径上删去一条边，加上 $\min w_i$ 变为在这条路径上再加上一条边的权值。我们发现如果减去/加上的边不是最大/最小值的话，我们得到的结果一定不是最优的。
因此我们建分层图，一个点 $(u, 0/1, 0/1)$ 表示当前在 $u$ 这个点，是否减去一条边，是否加上一条边，然后跑分层图最短路即可。
k-Maximum Subsequence Sum
长度为 $n$ 的数列，支持两种操作：
- 修改某个位置的值
- 询问区间 $[l,r]$ 里选出至多 $k$ 个不相交的子段和的最大值。
数据范围：$n, m\le 10^5, k\le 20$。
我们先考虑单次询问怎么做。我们建出费用流模型。
我们可以直接开始模拟费用流，每次选出最大的子段，然后将这些边取反即可。就可以直接用线段树来维护，重复 $k$ 轮即可。
维护的东西比较多，可以重定义运算符减少码量。
时间复杂度 $O(nk\log n)$。
Game On Tree
crimson000 和 rain 在玩一个游戏。他们有一棵由 $n$ 个结点组成的树。一开始，rain 有 $k$ 个卡片，其中第 $i$ 个卡片位于结点 $a_i$（注意：所有的结点都是唯一的）。在游戏开始之前，crimson000 将在这棵树的一个结点上放置一个卡片。
这个游戏由一些回合组成。每个回合都将有以下事件发生（完全按照以下顺序）：
- crimson000 可以把她的卡片移到相邻的结点，或者不移动；
- 对于 rain 的每一张卡片，他可以把这张卡片移到相邻的结点，或者不移动。注意：每个卡片的选择都是独立的。
当 crimson000 的卡片与 rain 的任意一张（或多张）卡片在同一结点时，游戏结束。（rain 自己的多张卡片可以置于同一结点上）
crimson000 希望游戏回合越多越好，rain 则相反。
如果某回合中间游戏结束（即 crimson000 把卡片移到了有 rain 卡片的结点上），这回合依然算入总回合数。
对于每个结点，计算 crimson000 一开始将卡片放在该结点时游戏将持续的回合数。
数据范围：$n\le 2\times 10^5$。
我们先让被追者停在原地不动，看在每个点它存活的时间，我们记为 $f_u$。被追者的策略就是：走到一个能走到的 $f_u$ 最大的点，然后停在原地等死。
现在我们就要找到能走到的 $f_u$ 最大的点 $v$。我们考虑点分治。设当前分治中心为 $x$，显然这个点 $v$ 一定满足 $f_v>dep_u+dep_v$，我们稍微推下式子可以得到：$f_v-dep_v-1\ge dep_u$，我们设 $a_i$ 为 $f_v-dep_v-1=i$ 的点的 $f_v$ 的 $\max$，那么当前的决策就是 $\max_{i=dep_u}^{+\infty} a_i$，对 $a$ 做后缀 $\max$ 即可。
时间复杂度 $O(n\log n)$。
Gregor and the Two Painters
给定两个长度分别为 $n,m$ 的序列 $a,b$ 和一个参数 $x$。生成一个 $n\times m$ 的黑白矩阵，$(i,j)$ 为黑当且仅当 $a_i+b_j\leq x$。求矩阵内黑色四连通块数
数据范围：$n,m,a_i,b_i\leq 2\times 10^5$。
我们进行一个钦定代表元。我们钦定一个连通块的代表元为其 $a_i+b_j$ 最小的那一个。我们只需要对这个代表元计数即可。
我们考虑一个点如何成为代表元。只有可能是 $a_i+b_j$ 更小的点与其不连通。我们固定 $j$，考虑 $a$ 如何让它和更小的不连通。我们设 $la_i$ 为 $i$ 左侧第一个小于等于它的位置，$ra_i$ 为 $i$ 右侧第一个小于等于它的位置，那么 $la_i, ra_i$ 和 $i$ 不能连通，也就是 $\min(\max_{j=la_i}^i a_i, \max_{j=i}^{ra_i}a_i)+b_j>x$，我们记前面那堆为 $ma_i$，同理我们对 $b$ 也做相同的事情，就能得到一个点 $(i, j)$ 成为代表元的条件：$a_i+b_j\le x, ma_i+b_j>x, a_i+mb_j>x$。直接二维数点，树状数组即可。
时间复杂度 $O(n\log n)$。