CCO2019 D2 Marshmallow Molecules

首先考虑一种暴力：令 $E_x$ 表示 $x$ 的出边集合，那么我们从小到大扫所有点，并对于 $x\to y$，让 $E_y$ 并上 $E_x$。然后我们发现，我们不需要对于 $x$ 都进行该操作，我们只需要把 $E_x$ 并到出边中最小的点上即可。然后就可以启发式合并了。

AGC007E Shik and Travel

先二分，然后考虑一个朴素的 DP，$f_{u,x}$ 表示 $u$ 子树内第一个点访问的深度是 $x$，最后一个点访问的深度的最小值是多少。然后我们把合并的具体方式写出来后，可以发现（设 $l$ 是重子树）$f_{l,x}\to f_{u,x}$ 的转移时只会有 $O(sz_r)$ 种更新，$f_{r,x}\to f_{u,x}$ 的也只有 $O(sz_r)$ 种。于是可以发现如果我们只维护 $f_u$ 中满足 $x$ 递增且 $f_{u,x}$ 递减的 $(x,f_{u,x})$ 那么 DP 的复杂度是 $O(n\log n)$ 的。于是总复杂度 $O(n\log^2 n)$。

CF1326F2 Wise Men

首先把不相等容斥掉，现在我们相当于划分成了若干个段，每个段中相邻连通。容易想到划分数，$18$ 的划分数只有 $385$，考虑对于每个划分数，令 $g_x$ 表示所有 $|s|=x$ 的 $f_s$ 组合成的集合幂级数，那么我们就是要统计 $[z^V]\prod_{x\in \pi} g_x$，于是我们直接利用子集卷积的技巧，对于每个 $g$ 都提前 fmt 然后转化成点乘，然后最后由于只需要求 $z^V$ 项的系数所以直接求就好了。总复杂度 $O((n^2+p(n))2^n)$。

CF1608F Mex Counting

对于这种 mex 的 DP 类问题，可以考虑先把一些位置空着，等到需要填的时候再填。这里指的是，$>mex$ 的数显然不会对 mex 产生影响，所以如果决定了一个位置大于目前的 mex 那么就先空着不填，等之后再考虑。

一个比较方便的做法是 $f_{i,j,k}$ 表示 $[1,i]$，mex 为 $j$，且没有填的数中一共有 $k$ 种不同的数（这些数都 $>j$）。于是我们从 $f_{i,j,k}$ 转移，可以让 $i$ 不产生影响，既 $(j+k)f_{i,j,k}\to f_{i+1,j,k}$，也可以让 $a_i=j$，并开一个辅助数组 $g_{j,k}$ 表示目前 mex $=j$ 并且仍有 $k$ 种不同的数未填（这些数都 $\ge j$），那么就 $f_{i,j,k}\to g_{j+1,k}$，然后 $g$ 的转移有 $g_{j,k}\to f_{i+1,j,k}$，$kg_{j,k}\to g_{j+1,k-1}$。复杂度 $O(n^2m)$。

CF1396E Distance Matching

猜测在上下界内奇偶性相同的皆可构造。考虑像分析上界那样，统计每条边的贡献，设一条边在匹配中被覆盖了 $c_i$ 次，那么 $c_i$ 需要满足的要求为：对于 $u$，其周围的 $c$ 之和为奇数，且考虑周围的所有 $c$，不存在超过 $1+\frac{\sum c}{2}$ 的 $c$。构造 $c$：考虑从下界往上构造，每次选一个 $c$ $+2$，肯定是对的，然后排序后加速模拟即可。构造匹配：一种比较简单的方法，就是用 stl list 维护一棵子树中未匹配的点，然后对于 $u$，将子树链表合并后，算出在这里要匹配多少个，然后每次取出链首作为第一个匹配的左部点，取出链尾作为最后一个匹配的右部点，即可。

上述实现的一个参考代码：https://codeforces.com/contest/1396/submission/259709356

CF1284F New Year and Social Network

根据样例猜测可以取到上界。考虑归纳构造：我们先有一个想法，就是如果我们删除 $A$ 的一条叶边 $u,v$，那么 $A$ 剩下还是一棵树，那么此时我们可以找到 $B$ 中 $u,v$ 的路径上的一条边，然后把这条边删掉后在 $B$ 中把 $u,v$ 缩在一起，这样 $B$ 还是一棵树。但是这样不好维护 B，考虑删 $B$ 的叶边 $(u,v)$，那么此时在 $A$ 中找到 $u\to v$ 路径上 $u$ 相邻的边 $(u,w)$，在 $A$ 上把这条边缩起来，然后在 $B$ 上由于 $u$ 是叶子所以缩 $u,w$ 不影响结构。由于 $(u,w)$ 是父子边所以维护这个很容易，类似并查集地维护即可。每次找边倍增即可，复杂度 $O(n\log n\alpha)$。

CCO2018 D1 Fun Palace

令 $m=\max a_i+b_i$。那么我们发现，一旦某一个时刻在一个 房间聚集的人数超过了 $m$，那么他们就直接成功了。所以每时每刻每个房间人数一定 $<m$。考虑 DP：$f(i,j)$ 表示考虑 $[1,i]$ 前缀的房间，钦定第 $i$ 个房间在任意时刻的聚集的人数最大值为 $j$，最大化前缀中能放的人数。这个转移是简单的：如果 $j\ge a_i+b_i$ 那么直接 $f(i-1,j)\to f(i,j)$；否则如果 $j\ge a_i$ 可以转移到 $f(i,j-a_i)$，如果 $j<a_i$ 可以转移到 $f(i,j+b_i)$ 且可以多放 $b_i$ 个人。并且还有转移 $f(i-1,[0,a_i-1])\to f(i,[0,b_i-1])$。

CF1242E Planar Perimeter

考虑 $n=2$ 时，答案就是 $y-x+2+[y=x]\times 2$，构造是容易的。而实际上，我们对于 $x,y$，我们可以容易地并出任意不小于这个下界且不大于 $y$ 的任意多边形。也就是说我们的可操作范围是很广的，只要最大的数不要太大就能取到 $3$ 或 $4$（根据总边数的奇偶性决定）。那么根据这样的想法，我们将所有边数从大往小排序，每次合并最大的和次大的，并合并出一个大小 $\ge$ 第三大的一个尽量小的多边形，这样的贪心从数值上一定是最优的，并且也是容易构造的：用一个双端队列维护多边形的顶点，那么每次如果加入 $>3$ 的（或者 $=3$ 且要加入新点时）就直接弹队尾然后补充队尾，然后如果加入 $=3$ 且不加新点就需要找到一个能凹进去的点。显然此时队首一定是能凹进去的（随便安排一下上一步加入的新点即可保证），于是就采用队首与与其相连的两个点作为三角形即可，并把队首给弹掉。复杂度 $O(n\log n)$，瓶颈排序。

CF1305G Kuroni and Antihype

首先对于这种生成树问题，首先先把贡献记到边上，即一条边的代价为 $a_u+a_v$. 然后我们发现除了根的每个点都被多记了一次，于是答案先扣掉 $\sum a_i$。然后我们发现可以通过建立一个 $a_{n+1}=0$ 的虚拟点 $n+1$，最后就解决这个问题了。然后跑 Bruvka 的最小生成树方法，每次用一个类似 fmt 的高维前缀 max 做即可，需要记录最大值以及连通块不同的次大值。

IOI2021 Distributing Candies

首先注意到只要求最终序列，所以按下标从左到右扫，维护操作序列。然后对于一个点，如果我们能够找到其最后一次碰到上下边界的时刻那么就能求出答案。定义折线 $f_x$ 表示 $x$ 时刻处于 $h$ 的折线，$g_x$ 表示处于 $0$ 的折线。对于 $x<y$，如果 $f_x,f_y$ 都分别满足 $x,y$ 时刻后不再触碰边界，那么由于 $f_{x,y}< f_{y,y}=h$，所以 $f_{y,x}>f_{x,x}=h$，所以 $f_y$ 一定是假的，即 $y$ 处不可能触碰边界。$g$ 的分析类似。

于是我们找到最小的 $x,y$ 满足 $f_{x}$ 和 $g_y$ 分别在 $x,y$ 时刻后不再触碰边界。如果有一个找不到那么就结束了，否则继续分析，令 $k=\max(x,y)$，那么一定有 $f_{x,k}>g_{y,k}$，所以 $f_{x,0}>g_{y,0}\ge 0$，所以 $f_x$ 一定是假的，$g_y$ 才是真的。于是就找到了这个时刻。找 $x,y$ 可以直接线段树维护最大/小子段和，然后线段树上二分。

AGC012E Camel and Oases

首先注意到每次跳 $V$ 减半所以不会跳超过 $k=\log V$ 次。

考虑 $V\le 2\times 10^5$ 这个很奇怪的范围，可以猜测做法大概会用到 $O(2^k)$ 的状压，即记录下已经用过了哪些 $v$。

一开始对整个序列建深度为 $k$ 的树形结构然后想树上 DP，但是发现根本无法合并。

于是考虑更简洁的直接从左到右 DP，$f_{s,x,i}$ 表示考虑目前已经用过的 $v$ 的集合是 $s$，目前的 $v=x$，能否到达 $i$。

显然 $f_{s,x,i}$ 的合法是一段前缀，直接记录 $f_{s,x}$ 表示能到达的最远的 $i$ 即可。转移是容易的。（实际上这个 $x$ 没什么用，可以直接省略掉，DP 的复杂度 $O(2^kk)$）。

考虑如何求出每一个点的答案。先求出同样的后缀的 DP 数组 $g_{s}$，那么对于一个点 $i$，其合法当且仅当存在一个 $S$ 不包含初始的 $V$ 且（令全集为 $T$） $f_{S\cup \{V\}}\ge i$ 且 $g_{T-S}\le i$。

那么我们直接枚举 $S$，那么可贡献到的 $i$ 一定是一段区间，直接差分即可。

复杂度 $O(2^kk)$。

AGC013F Two Faced Cards

首先考虑如何计算单组。

这种匹配题容易尝试贪心。先对 $c$ 排序。设 $l_i,r_i$ 为反面正面（显然可以不妨设 $l_i\le r_i$），那么匹配 $r_i$ 会产生一个贡献。考虑在数轴上从左往右扫，扫到 $l_i$ 时将 $l_i$ 塞进堆中，扫到 $r_i$ 时将 $r_i$ 塞进另一个堆中，然后在 $c_i$ 时尝试匹配。

此时如果存 $r$ 的堆仍然留有元素，那么一定是取任意一个 $r$ 是最优的；而如果没有 $r$，那么我们只能取一个 $l$（否则无解），那么由于选了 $l$ 会导致对应的 $r$ 就不能选了，所以我们希望这样的不好的事情越往后发生越好，所以一定是选 $r_i$ 最大的 $l_i$ 来匹配这个 $c$。

然后考虑多组。多组的形式实际上可以讨论新加入的是匹配 $l$ 还是 $r$，总之可以转化成如下的问题：对于每个 $i$，都需要处理出 $c_{[1,i-1]\cup[i+1,n-1]}$ 去匹配原来的 $n$ 个 $(l_i,r_i)$ 所能得到的答案。

考虑既然是把一个中间的点给删了，那么看看能否求出前后缀的答案然后拼一拼。从前往后扫的贪心上面已经讲过了，考虑从后往前的一种贪心。

从后往前扫时考虑在 $l_i$ 处匹配。那么我们就维护尚未匹配的 $c$，每次扫到一个 $l_i$ 就尝试匹配。如果其 $r_i$ 能配，那么我们直接让它配在所有 $c$ 中的 lower bound，显然这个不劣；否则我们就只能让它配所有 $c$ 中的最小值。

然后我们看对于 $i$，做完了 $[1,i-1]$ 的前缀匹配和 $[i+1,n]$ 的后缀匹配后还剩些什么没有匹配：即在前缀中满足 $l_j\le c_i$ 且尚未匹配的 $[l_j,r_j]$ 和后缀中尚未匹配的 $c_k$。

由于这些 $l_j\le c_i<c_k$，所以我们实际上转化成了就是一些 $r_j$ 和一些 $c_k$ 的匹配。并且我们发现，令 $S_i,T_i$ 分别表示计算 $ans_i$ 时尚未匹配的 $r_j$ 集合，以及 $c_k$ 集合，那么 $r_j$ 和 $c_k$ 的存在时间一定都是一段区间。

所以我们只需要支持加入/删除 $r$ 和 $c$，然后维护匹配结果即可。这个直接使用 Hall 定理，加上线段树维护即可。

复杂度 $O((n+q)\log n)$。

CF1864H Asterism Stream

首先进行一些转化：期望操作步数等于到达每个 $<n$ 的点的概率之和（因为每到达这样的一个点就会要走一步）。也就是说，我们对于每一种到达 $x<n$ 的数的方案，算出其概率（即 $1/2$ 的步数次方），然后对于所有这样的方案的概率累加起来就行了。我们先枚举这样的方案中乘了几次，设为 $p$，我们令第 $i$ 次乘法和第 $i+1$ 次乘法进行了 $y_i$ 次加法（$y_0$ 表示第一次乘之前做的加法，$y_p$ 表示最后一次乘之后做的加法），那么这个方案可以用一个 $y_{0},\dots,y_p$ 的序列唯一表示，并且可以知道最终得到的数 $x=2^p+\sum y_i2^{p-i}$，并且概率是 $(1/2)^{p+\sum x_i}$。

令 $x_i=y_{p-i}$，那么也就是说，对于一组 $x_0,\dots,x_p$，如果满足 $\sum x_i2^i< n-2^p$，那么就能产生 $2^{p+\sum x_i}$ 的贡献。这个就是一个和上面一题差不多的问题，只不过有两个地方不一样：

第一个，上一道题没有系数，而这一道题中有贡献系数。具体而言，这道题我们仍然将 $x_i$ 的取值拆成 $2^i,2^{i+1},\dots,2^k$ 的 01 背包，但是 $x_i$ 的 $2^k$ 项有着 $2^{k}$ 的体积以及 $(1/2)^{k-i}$ 的贡献系数。于是我们需要预处理出 $g_{i,j}$ 表示对于体积为 $2^i$ 的所有物品，取出了 $j$ 个物品的所有方案的贡献系数之和是多少，然后再转移的时候用 $g$ 去转移即可。

上一题的等于变成了这题的小于等于。其实也差不多，DP 的时候额外记录一个维度 $0/1$ 表示要求更高的位能否贴着上界，即可。

总复杂度在 $O(T\log^3 n)$，但是有些常数剪枝。