QOJ8824 Slay the Spire
首先可以新建超级源点，把药水和起点的限制去掉。问题变为，选择一些边，支付其边权的代价改变其入点，改完之后使得图存在一个欧拉回路。
然后对于出度大于入度的点，需要把一些出边作为没有贡献的边删掉。可以证明只要删掉上述不合法的边，一定能使得所有点入度等于出度（随便接到出度小于入度的点上面即可）。
现在的问题是图的连通性。把删的边 $(u,v)$ 归到 $v$ 的连通块里，可以证明删完之后，一个联通块如果有删边则其可以和其他连通块联通。现在问题就是内部没有删边的连通块。删掉其内部的一条 $(u,v)$，然后如果有一条边 $(u,v’)$ 先前就被删掉了，则可以把 $(u,v’)$ 接回来 （因为 $u$ 的出度会减少 $1$，原先删掉 $(u,v’)$ 是不必要的）。
感觉写法非常的厉害，通过判断原入度和新出度是否相等来判断一个连通块是否需要新建边。
*QOJ8556 Somewhere Over the Rainbow
显然题意是要求一个不能共线的整点上凸壳，看成要求 $a_i-a_{i-1}$ 严格递减。设 $f(x,y)$ 表示，如果凸壳过 $(0,0),(x,y)$ 两个点，则到 $(x,y)$ 时的最大斜率是多少。设初始斜率为 $v$： \(\begin{aligned} &\frac{(v+(x+v))(x+1)}{2}\geq y\\ &v\geq \lfloor\frac{2y-x-x^2}{2x+2}\rfloor\\ \end{aligned}\) 这是初始斜率的下界，然后初始斜率一定会取这个 $v$。然后此时比 $y$ 高了 $lst=\frac{(v+v+x)(x+1)}2-y$，这个值一定 $\leq x$，所以找到一个点，其后面的斜率整体 $-1$ 即可。
做单调栈的时候，栈内存三元组 $(x,y,d)$，表示当前在 $(x,y)$，此时斜率是 $d$。此时想要加入 $(x_i,y_i)$，先计算能不能加进去，即判断 $y+\frac{(d+(d-(x_i-x))(x_i-x)}{2}\geq y_i$，如果不成立就弹栈顶。
找到了满足的之后，把 $(x_i,y_i,f(x_i-x,y_i-y))$ 扔进栈里面就行了。
addition：一个非常神奇的简化方式是，$a_i$ 对应位减去一个 $h_i$，满足 $2h_i=h_{i-1}+h_{i+1}+1$，这样限制变成了 $2a_i\geq a_{i-1}+a_{i+1}$。可以令 $h_i=-\frac{i(i+1)}{2}$，最后再加上所有 $h_i$ 的和即可。
**QOJ8820 Exchanging Kubic 2
*QOJ9111 Zayin and String
就喜欢这种板板题。
建出来 AC 自动机，分数规划可以二分答案，然后直接 DP。
*P7205 [COCI2019-2020#3] Drvca
从小到大排序，考虑最小值，次小值和次次小值分别属于哪个等差数列，这样可以确定一个。只有 $\mathcal O(1)$ 种情况，可以拿个桶或者 map 啥的支持删数，判断剩下的数能否构成等差数列即可。
### QOJ4630 New Equipments III
最大权匹配，但是点边数都非常多，权值很小。
使用 primal-dual 算法：考虑跑最长路，建出来最长路图，在这上面跑 dinic。
最长路长度一定不超过 $5$，按照上述流程的话，一定是先跑完长度位 $5$ 的，再跑长度为 $4$ 的，再跑为 $3$ 的……这样跑 dinic 复杂度应该是和 dinic 一样的，是 $\mathcal O(Vm\sqrt n)$。
[AGC006C] Rabbit Exercise
是线性变换，但是维护矩阵非常爆炸。
观察 $a_i=\frac{1}{2}(2a_{i+1}-a_i+2a_{i-1}-a_i)=a_{i+1}+a_{i-1}-a_i$，和方差那道题是一样的，可以看成是交换了差分数组。这样只需要维护置换就行了，暴力快速幂 $\mathcal O(n\log V)$。
P3441 [POI2006] MET-Subway
第一种想法：显然叶子会取到 $\min(cnt,2l)$ 个，然后距离叶子为 $1$ 的点也是同理……这样不断剥叶子就行了。
第二种想法：考虑一次覆盖一条最长的链，第一次肯定是覆盖直径，接下来把直径上的每个子树长剖一下，加一次操作就是选两条长链。这玩意也等价于取直径端点然后取 $2l-1$ 条长链。
QOJ3688 保护古迹
暴力枚举子集选择那些古迹进行保护。取补图连边，边权是跨过的原图边权。从源点向最外面的连通块连边，从古迹向汇点连边，跑最小割即可。好像不是很可写。
P3577 [POI2014] TUR-Tourism
取一棵生成树！这样深度 $\leq 10$，直接三进制状压根链状态即可。
QOJ6521 Swapping Operation
典中典了属于是。
前缀 and 只会变化 $\log V$ 次，后缀 and 也是。然后选择两个点进行交换的话有一个点一定选在前缀变化的点。这样第一个点 $i$ 有 $\log V$ 种选法，第二个暴力枚举选哪个 $j$，然后在中间的 $[i+1,j-1]$ 区间内前缀 and 也只会变化 $\log V$ 次，与处理一下暴力做一遍就行了。复杂度 $\mathcal O(n\log^2 V)$。
QOJ6109 Similarity Graph
definieren 太强了。。。
首先可以看成一个完全图，出现的边是黑边，没出现的边是白边。你需要给边定向，满足不出现环，并且把所有白边都反转之后也不出现环。第一遍的拓扑序即为排列 $p$，第二步的拓扑序即为排列 $q$。
考虑这个有什么限制。对于一个三元环 $i,j,k$，三条边颜色不完全相同。假设 $(i,j),(j,k)$ 颜色相同，$(i,k)$ 不同，则要求是，$i\rightarrow j$ 并且 $k\rightarrow j$ 或者是 $j\rightarrow i$ 并且 $j\rightarrow k$，即同色边必须同向。
考虑完全图上有环就一定有三元环，这样定完向之后，没有了三元环就不可能出现环了。再按照拓扑序确定出 $p,q$ 即可。
CF1290E Cartesian Tree
我好菜啊。
考虑 $k$ 从小变大，维护每个点的东西。
第一眼转成深度之和，全错了。
就是摁维护子树和。实际上是维护的当前点在已经激活的子序列上的，左，右边第一个比他大的位置。是个 segbeats 啥的。
CF1580D Subsequence
笛卡尔树上直接背包就行了。
[AGC005C] Tree Restoring
核心性质：距离一个点最远的点一定是直径两端点之一。把直径拎出来就行了。
CF1707D Partial Virtual Trees
真子集的限制可以容斥变成是子集。这样看成一开始所有点都亮着，然后不断有点熄灭，要求如果两个不同子树里面都有点亮着那 $i$ 就不能熄灭。
设 $f_{i,j}$ 表示 $i$ 子树内，经过了 $j$ 个时刻仍然有点亮着，不考虑 $j$ 后面时刻的方案数。首先第 $j$ 时刻如果 $i$ 还亮着：
\[f_{i,j}=\prod_{u\in \mathrm{son}(i)}\sum_{k\leq j}f_{u,k}\]如果 $i$ 在第 $p$ 到 $p+1$ 个时刻熄灭，则在 $[p+1,j]$ 这段时间内，有且仅有一个子树亮着：
\[\begin{aligned} f_{i,j}&=\sum_{p<j}\sum_{u\in \mathrm{son}(i)}f_{u,j}\prod_{v\in\mathrm{son}(i)}^{v\not=u}\sum_{k\leq p}f_{v,k}\\ &=\sum_{u\in \mathrm{son}(i)}f_{u,j}\sum_{p<j}\prod_{v\in\mathrm{son}(i)}^{v\not=u}s_{v,p}\\ &=\sum_{u\in \mathrm{son}(i)}f_{u,j}\prod_{v\in\mathrm{son}(i)}^{v\not=u}ss_{v,j-1}\\ \end{aligned}\]这玩意可以摁前缀和优化的。最后再暴力做一遍二项式反演，总复杂度 $\mathcal O(n^2)$。
P4564 [CTSC2018] 假面
暴力维护 $f_{i,j}$ 表示点 $i$ 还剩 $j$ 滴血的概率，查询先全都乘起来，然后做多项式短除法。
QOJ2552 Points
考虑只有加点怎么做，新加入一个数之后查询与他配对的最优对。分类讨论是 $x$ 还是 $y$ 取到 $\max$。
假设新加入的点对是 $(x_0,y_0)$，如果是 $x$，则要求 $y+y_0\leq x+x_0$ 即 $y-x\leq x_0-y_0$，建一个 $y-x$ 下标的线段树，维护区间 $x,y$ 最小值即可。$y$ 取到最大值的情况同理。
现在有删点，考虑线段树分治，这样加点之后还需要支持撤销。
栈维护当前顶点的 $x,y$ 最小值，再维护前缀最小值就行了。复杂度 $\mathcal O(n\log^2 n)$。
被 definieren 嘲讽了。definieren 表示他两年前就干爆了这种弱智做法。
式子可以变成 $y_i+y_j+\max(x_i-y_i,x_j-y_j)$，这样可以按照 $x-y$ 直接维护，线段树分治合并信息。