5.21
试机赛
B. 朴素计数，写个 dp 算贡献系数就好了。
C. 网路流。建边 \((s,i_0,C),(i_1,t,C),(i_0,j_1,dis_{i,j})\)，跑最大流即可。
5.22
A. 首先分析一下贡献的形式。因为这玩意是凸的，所以我们可以钦定一个选点顺序，优先让第一个最大，其次让第二个最大，以此类推。
很容易猜测选的点是不是一定位于四个角上，但仔细想想就会发现不对。但进一步观察可以发现，只要钦定了选的最多的点是谁，剩下的一定都会选在角上。这是因为去掉了选的最多的点之后，剩下的矩形一定全部有交，通过调整法即可证明上述结论。
B(寻找特殊值构造). 把 \(q\) 转化成 \(1\) 到 \(n\) 的排列，然后连边 \(i \rightarrow p_i\)，不妨猜测一个答案下界，也就是 \(\frac{1}{2}\sum|i-p_i|+C \times num\)。实际上确实不可能更小的，通过打表也能证明这是对的。
然后考虑构造。我们将这玩意刻画在数轴上，不难发现我们只需要每次找到一个这样的操作：交换两个数 \(i,j\)，同时使得 \((p_i,p_j)\) 被少覆盖两次。
其实我们相当于在找二元组 \(i,j\)，满足 \(j < p_i < p_j < i\)，在这种情况下我们一般考虑一些特殊值，比如说最大值。考虑不断从最大值往前跳，直到方向改变为止。不难发现这样我们就找到了一组合法的交换。
C(换角度扫描线). 竖着扫描线，主席树维护之即可。
5.23
A(类欧几里得思想). 先搞点分类讨论，
B. 直接 bitset 优化即可。
C(图论建模). 对于每个大小为 \(2\) 的栈连边 \(s_1 \rightarrow s_2\)，这样图会分为若干环或者链。给每个元素设个状态，\(1\) 所在栈大小为 \(1\)，\(2\) 表示在上面，\(3\) 表示在下面。那么每个值的状态就是个二元组。
这样我们首先肯定优先解决 \((1,1),(1,2)\)，然后对于剩余的链需要一个空栈来解决，对于环则需要两个空栈。当然值得注意的是，对于二元环和顺环其实只需要一个空栈，特判一下就好了。
5.24
5.25
A. 观察到把 \(p\) 映射为 \(1\) 到 \(n\) 的排列后，答案就相当于逆序对个数。然后直接 dp 就行了。预处理子树间的逆序对数可以树上启发式合并。
B. dp of dp 题。先考虑怎么检验一个固定的串。发现只需要扫一遍，分别记录若以 \(A\) 为结尾或以 \(B\) 为结尾最短的串是什么即可。
然后建个 SAM 跑就行了。不难分析出状态其实是 \(O(len)\) 的。
C. 不会
5.26
A. 经典 trick。考虑算出每种颜色到所有点的最短路，对于 \(x,y\)，最短路就是直接走到的答案和跳 \(dis_{C,x}+dis{C,y}+1\) 的最小值的较小值。
容易发现后者不超过 \(2C\)，所以对于小于 \(2C\) 的我们可以暴力算。
对于剩余的，其实我们只需要枚举一个定点 \(x\)，再枚举一个颜色 \(C\)，不难发现对于所有 \(col_y=C\)，经过同一种颜色的答案最大和最小最多差 \(1\)。那么直接预处理一个高为前缀和就好了。
这样直接做是 \(nC+2^CC\) 的。
注意到随机数据下本质不同的元素数量不多，对两两状态间求答案即可。
B.
5.28
A. 随机撒点树分块（子树大小满 \(B\) 就分裂）或者点分治到 \(O(\sqrt n)\) 停止即可。
B. 首先虚树大小可以用经典 trick 算，然后就是经典的按 lca 深度贪心了。
C. 对正方形考虑刻画对角线。发现左一是确定的，那么我们只要锁定左二就能确定上边界。
然后发现从高到低，从左到右贪心就对了。线段树维护一下就好了。
5.29
A. 抽象平衡树题。大力维护即可。
B. 很有 AGC 风格啊。对于固定的方案，首先刻画出 DFA，然后发现相当于要求所有环权值和都为 \(0\)。其实判这个东西只需要对每条边建反向边（权值也取反），看看是否有负环就好了。
然后考虑怎么枚举 lcp 并 check。这样我们发现问题等同于每条边权值固定，或为 \([-1,0]\) 或 \([0,1]\)，查询是否存在一种定权方式没有负环。
这个看起来很难。但我们其实可以把固定方案的问题直接转化为差分约束的形式，然后取并，稍微刻画一下就能做了。
C. 观察到对于 \(1,2,3\) 一定选最前面的 \(1\) 和最后面的 \(3\)，\(3,2,1\) 则与之相反。
于是确定两者个数 \(A,B\) 后方案也是确定的，就是点匹配区间的形式。容易贪心解决。
但其实直接用 Hall 把条件写出来就能解出 \(A,B,A+B\) 的范围，于是就做完了。
注意：范围还和三种数的个数相关。
5.31
A. 如果不限制 \(w\)，最短路的形式显然走环。考虑限制 \(w\) 怎么做。
首先判掉 \(w=0,1,n-1,n\) 之类的边界情况。
考虑调整。发现相当于一个有缺口的环，每个点可以放在上面也可以放在下面。显然如果不想付出额外代价，位于缺口处就随便放，否则就只能放在一边。
注意到有缺口的一边可以卡到下界，也就是 \(2\)，但上界不行。
再进一步观察可以发现，我们总是可以花费将一条边代价乘 \(3\) 的方式使上界加一。
维护优先队列即可。
B. 对于每个咒语，将不知情的两个贤者建边，发现就是最小点覆盖问题。但因为 \(k\) 很小可以每次删最大点去搜。记得特判最大点度数不超过 \(2\)。
C（定根）. 注意到对于固定的区间，一个点会贡献当且仅当子树内有区间内的点，且不包含所有点。容斥掉后者，相当于减掉 \(lca\) 深度，前者可以启发式合并出合法矩形然后去算。
写个历史和就好了。得拆一下矩阵。
6.2
A. 状态间建边。注意到 \(s\) 和 \(t\) 可达当且仅当能到达的最小状态相同（其实也就是位于同一连通块）。
然后问题就是怎么求最小状态。仔细分析一下我们有一种简单的策略可以做到最优（建出克鲁斯卡尔重构树，能证明下面边权比上面小，每次跳下面的）。Xor Hash 一下就好了。
B. 归纳构造。每次取出最小的丢上去就行了，鸽巢原理。
C. 没写完。总之就是二分图最大匹配转最大独立集，然后大力维护。
6.3
6.4
A. 发现其实只有三种方向能走，于是横竖分别扫描线算一下就好了。
标签：广东省,发现,可以,对于,然后,2024,即可,集训,dp From： https://www.cnblogs.com/Hypercube07/p/18242827