加油啦！
WC2020 选课
TAGS：背包
WC2019 数树
TAGS：组合意义，多项式
HNOI2022模拟测试二十三 mayoi
TAGS：DP，带区间修改标记的线段树合并
HNOI2022模拟测试二十二 B
TAGS：思维，最短路，DP
首先如果当某条边的答案没取到 $l_i$ 或者 $r_i$ 的时候，一定可以根据谁先到达 $u$ 来调整到区间的端点。
从上面这个结论的证明过程我们可以导出做法，直接 Dijkstra 就行了。
CF708D Incorrect Flow
TAGS：上下界网络流
下面用 $(u,v,l,r,w)$ 来表示一条边连接 $u,v$，流量限制区间为 $[l,r]$，费用为 $w$。
对于 $c\geq f$ 的情况，我们先连一条 $(u,v,f,f,0)$，然后连一条 $(u,v,0,c-f,1)$ 与 $(u,v,0,INF,2)$ 来帮助其提升流量，对于减小流量，连一条反向边 $(v,u,0,f,1)$ 来讲流量从 $v$ 流回 $u$。
对于 $c<f$ 的情况，先连一条 $(u,v,c,c,0)$，然后用 $(u,v,f-c,f-c,1)$ 来强制其一开始先提升流量上限，然后常规的 $(u,v,0,INF,2)$。稍微不一样的是减小流量的部分，对于最开始的 $f-c$ 的流量我们减小的费用是 $0$，因为可以除了减小 $f$ 的花费 $1$，还剩下了提升 $c$ 的花费 $1$。因此连 $(v,u,0,f-c,0)$ 和 $(v,u,0,c,1)$。
最后跑上下界最小费用流即可。
WC2007 剪刀石头布
TAGS：竞赛图的性质，费用流
考虑最小化非三元环三元组的数量，我们知道这个东西等价于 $\sum \binom{outdeg_i}{2}$，然后有凸性，费用流，做完了。
CF429E Points and Segments
TAGS：欧拉回路
设 $A_i$ 为蓝色覆盖次数减红色覆盖次数，考虑 $\left{A_n\right}$ 的差分数组 $\left{D_n\right}$，则覆盖的影响会形如 “$D_l$ 加 $1$，$D_{r+1}$ 减 $1$” 或 “$D_l$ 减 $1$，$D_{r+1}$ 加 $1$”。考虑从 $l$ 连一条边到 $r+1$，然后如果有欧拉回路的话就可以直接构造出一组使得每个 $D_i$ 都等于 $0$ 的方案，这显然是符合题意的。出现奇度点的话，考虑用常见的加一条边的操作，将第 $2i$ 个奇度点和 $2i+1$ 个奇度点连边。然后跑出来的方案中一个等于 $1$ 的 $D$ 后面第一个不为 $0$ 的 $D$ 一定是 $-1$，因此满足要求。
构造方案的时候只要看每条边被如何定向了即可。
HNOI2018 转盘
TAGS：观察，兔队线段树
考虑一组方案会形如走了若干次完整的环，然后走了一段前缀到 $i$ 结束。对于这组方案我们可以调整起点为 $i$，然后等待，便得到了一组等价方案。因此一定存在一组只走了 $n-1$ 步的最优解方案。
先断环成链，然后要维护
$$
\min \limits_{j=1}^n \left{\max\limits_{i=j}^{j+n-1} \left{a_i-j+i\right}\right}
$$
注意到 $\max$ 的上界放宽到 $2n$ 对结果无影响，因此直接上兔队线段树维护即可。
HNOI2022模拟测试二十一 游戏
TAGS：分块
首先显然每个 $a_i$ 只需要关心其奇偶性，其次因为一个奇数的 $a_i$ 可以用来切换先后手因此是一个先手必胜态。
然后考虑一个先手必败态点 $p$，其左侧第一个先手必败态点 $q$ 一定满足 $2|a_q\and p-q-1\geq k$ 且 $q$ 是最大的。有了这个厉害的条件，我们可以考虑从 $t$ 左边的第一个先手必败点开始往左跳，看能不能跳到 $s$。
然后考虑分块，对于每个块中记录每个点之前第一个块内 $0$，记录从当前点往左跳块内最左的必败点。
注意需要讨论 $t$ 是先手必胜还是先手必败态。
2022IOI选拔&精英赛前训练2 mex
TAGS：二分答案，2-sat，辅助图
$\mathcal O(n^2\log n+\dfrac{n^3}{\omega}) $ 的暴力是传递闭包后二分答案，因为对于一种权值其有两种选择，考虑建立 2-sat 模型，两个点有限制当且仅当有一方能够到达另一方。
因为 2-sat 其实只关心变量点之间的连通性，我们可以建正反两张辅助图来传递本来需要传递闭包的信息。
2022IOI选拔&精英赛前训练1 旋转
TAGS：转化，线段树维护单调栈
我们可以做这么一步很牛逼的转换：将这个树看成一个 treap，每次修改一个点的堆权值 $rank$ 为全局最大值，然后将其 rotate 至根来保证堆性质。那么根据笛卡尔树的理论，一个 $y(y>x)$ 是 $x$ 的祖先当且仅当其 $rank[y]=\max\limits_{i=x}^y {rank[i]}$，且一定会贡献一次右旋，$y<x$ 同理。
那么现在问题就变成了单点修改一个值，每次查询以一个点为开头的前缀最大值个数，$2 \log$ 很板。
注意需要离散化。
HNOI2022模拟测试十七 会出对出点
TAGS：组合计数，DP
首先一个比较显然的思路是像 NOI2019冒泡排序 一样每次 fix 一个前缀，然后暴力枚举下一个位置数的选取。得到的是一个不完整的堆，然后要给一些子树填上全部大于某个值的数。显然要先将限制排序使得可选取数集包含，然后数的选取就可以组合数，填数方案可以在一开始用树形 DP 预处理。我们就得到了一个 $\mathcal O(n^3)$ 算法。
我们可以处理的限制是让一个子树的值全部大于某个值，那么补集转化一下为求字典序大于给定排列的合法排列个数，fix 完前缀后就不用枚举下一位的选取了。
HNOI2022模拟测试十七 绝世好题
TAGS：二分答案，网络流
二分答案，拆点网络流判定。
这我为啥不会
HNOI2022模拟测试十七 谢邀
TAGS：乱搞，思维，斯特林数
在判定方案是否合法的问题里，喜欢同一些 idol 的粉丝显然只需要保留一个。那么只需要考虑 $\mathcal O(2^m)$ 个本质不同的粉丝，因此答案可以写成 $\sum\limits F_i \begin{Bmatrix}n\i\end{Bmatrix}$ 的形式。
注意到一定存在一个没有粉丝的 idol 和一个全部人都是他粉丝的 idol，那么我们只需要考虑 $m-2$ 个 idol 的粉丝。对于一个特定的 $m$，我们可以 $2^{2^{m-2}}$ 枚举每种粉丝是否存在，然后 $\mathcal O(m^2)$ 判定是否合法。这样子将所有 $m$ 的系数预处理出来即可。
CF1061E Politics
TAGS：上下界网络流
我们将树按照限制划分成若干个连通块，则限制形如一个点属于两个集合，每个集合有选点数量限制。
然后考虑费用流，建三个部分的点，第一个部分为第一棵树上的集合，向第二个部分中的单点连边，然后第二个部分的单点向表示第二棵树上的集合的点连边。
还需要注意到限制是恰好等于，因此跑上下界网络流。
CmdOI2019 口头禅
TAGS：SAM，自然根号，猫树分治
看到静态区间查询问题，我们首先考虑猫树分治。
先要解决的基本问题是如何查询多个串的最长公共子串，从中选出一个长度最小的串 $S$，对于其他每个串建一个 SAM，然后将 $S$ 放在 SAM 上匹配。最后会得到 $S$ 的每个前缀与其他串的 LCS，合并即可。复杂度是 $\mathcal O(len+|S|)$ 的。
我们可以将猫树分治的复杂度分成几个部分：
- 分割询问数组的复杂度。在分治途中需要分别往子分治区间放询问，以及找出需要在当前区间解决的询问，这个只能单次 $\mathcal O(qcnt)$ 的复杂度。因此我们需要保证分治树的高度不能太大。
- 对于分治到区间 $[l,r]$ 时找到的分割点 $p$，分别计算 $[l,p]$ 后缀与 $[p,r]$ 前缀答案的复杂度。
- 合并前缀后缀答案的复杂度。
我们考虑当前分治到了区间 $[l,r]$。根据前面计算公共子串大小的算法，显然我们要找一个长度较小的串作为分割点。我们尝试一下每次选择一个最小值作为分割点，对于一个长度 $v$，以其为最小值的区间 $[l,r]$ 至多长 $\mathcal O(\dfrac{len}{v})$，则单层分治（若干个同层分治）计算用于合并的信息的复杂度为 $\mathcal O(v\times\dfrac{len}{v})=\mathcal O(len)$。然后我们每次选取所有最小值中中间那个作为划分点就能保证这个最小值只会贡献 $\mathcal O(\log n)$ 层分治。又我们知道至多只有 $\mathcal O(\sqrt{len})$ 个不同的长度，因此这样子的复杂度是 $\mathcal O(len\sqrt{len} \log n)$。对于合并答案的部分，每个询问的复杂度贡献是其区间中的长度最小值，这个在记忆化保证点对不重后就至多是 $\mathcal O(Q\sqrt{len}+len\sqrt{len})$。
上面那个算法劣的原因是分治树过高，但是我们需要保证计算用于合并的信息的复杂度正确的话一定要保证每轮分治里选的划分点是一个 $\mathcal O(minval)$ 的位置。那么考虑倍增，在分治过程中维护一个极小的阈值 $x$，然后将分治区间中的所有在 $[2^x,2^{x+1})$ 里的长度拿出来取中点为划分点，直到不存在 $[2^x,2^{x+1})$ 里的长度后将 $x$ 加 $1$。这样子在分析计算信息的复杂度与单个 $x$ 的分治深度时可以套用上面的过程，因为显然选出来的长度不会超过其中最小值的两倍。不同的是只有 $\mathcal O(\log len)$ 个 $x$，因此复杂度优化为 $\mathcal O(len \log len \log n+(Q+len) \sqrt{len})$。
IOI2018 Meetings
TAGS：DP，笛卡尔树，数据结构
考虑用 DP 来计算答案。设 $f(l,r)$ 表示区间 $[l,r]$ 的答案，容易发现会议位置选在高度最大处一定不优，而最大值处一定有一侧的花费会受到最大值的影响，因此转移考虑是哪一侧收到了影响。设 $p$ 表示最靠左的最大值位置，有
$$
f(l,r)=\min\left{f(l,p-1)+(r-p+1)a_p,f(p+1,r)+(p-l+1)a_p\right}
$$
你会发现这个 $p$ 一定是 $l,r$ 在笛卡尔树上的 LCA 结点的划分点！因此我们只需要维护笛卡尔树上每个结点所代表区间的前缀与后缀的 DP 值。
以前缀的 DP 转移为例。我们有
$$
f(l,i)=\min{f(l,p-1)+(i-p+1)a_p,f(p+1,i)+(p-l+1)a_p}
$$
观察一下可以发现，这个转移实际上是对一个区间的值做加法后，再用一个一次函数去 checkmin。直接李超树可以做到 $\mathcal O(n \log^2 n)$，不太能过，考虑优化。
显然的事实是，随着一个区间右端点增大，其决策点也会跟着右移动。也就是说在上面转移中，会被一次函数 checkmin 的点是区间的一段前缀（其实观察到斜率 $a_p$ 一定比右边的增长率大也能发现这个结论）。因此我们只需要用线段树二分找到这个会被 checkmin 的区间，然后区间覆盖操作即可做到 $\mathcal O(n \log n)$。
CF1404D Game of Pairs
TAGS：构造
我们研究一下 B 选择 $1,2,\cdots,n$ 的决策。记 $s=\dfrac{n(n+1)}{2}$。
当 $n$ 为偶数时，有 $s \equiv \dfrac{n}{2},\dfrac{3n}{2} \pmod{2n}$。那么如果我们作为先手将 $(i,i+n)$ 分一组，后手就必败了。
当 $n$ 为奇数时，有 $s\equiv 0,n \pmod{2n}$。考虑现在先手给出的分组 $(u_i,v_i)$，我们建图，在点 $u_i$ 与 $v_i$ 中连一条无向边。则答案的形式是在这个二分图的唯一完美匹配中，每一对匹配选择一个点。我们尝试选出一组总和为 $s+kn$ 的方案。直接增加限制，限制 $i$ 与 $i+n$ 中只能选一个。然后图中相当于加了一组完美匹配的边进去，可以发现每个连通块的形式一定是一个偶环或者一条偶数长度的链，也就是说可以划分成一个两部分点数相同的二分图。那么我们可以直接选出一组 $s+kn$ 的方案。因为 $\dfrac{2n(2n+1)}{2} \equiv n \pmod{2n}$ 如果 $s+kn$ 模 $2n$ 余 $n$，直接将方案取其补集即可。
这个题真的比较神奇。。。不知道怎么能想到
HNOI2018 游戏
TAGS：势能均摊
首先比较显然要对每个点算出其能拓展到的最远处。
一个比较简单的 $\mathcal O(n \log n)$ 做法：考虑从左到右计算，轮流尝试扩展左端点与右端点。左端点扩展到新点 $i$ 时，可以直接将 $i$ 的能拓展到最远处继承过来，这样子左端点移动的次数是均摊 $\mathcal O(n)$ 的。然后用一个线段树二分来优化拓展右端点的过程即可。
更进一步的 $\mathcal O(n)$ 做法：根据上面做法左端点移动步数均摊分析过程的提示，我们可以获得提示：如果在用某个点做暴力拓展的过程时，能够保证其将要拓展到的点已经被计算过，就能均摊分析。实际上是要设计一个优秀的顺序来保证信息最大的可继承性。我们考虑题目中的关键性质：一扇门的钥匙位置是唯一的，这意味着一扇门实际上是单向的！也就是说，对于一扇门两旁的点，我们一定可以确定只有一方的信息有可能被另一方继承，我们用建图来限制可能被继承的点优先计算，然后这张图拓扑排序后的结果作为拓展顺序就能保证一扇门只被暴力拓展一次了。
注意需要将中间没有门的点缩起来。
HNOI2018 毒瘤
TAGS：枚举，DP，虚树
先考虑拿出一棵生成树，然后会有多出来的 $m-n+1$ 条边。考虑 $2^{m-n+1}$ 枚举每条边第一个端点的钦定是否选择进独立集的情况后然后就有了一个 $\mathcal O(n 2^{m-n+1})$ 的做法，但这不是正解也不能过那出这么小数据范围干嘛。
考虑建出虚树来优化。考虑在暴力转移的时候拿出一个点，发现贡献可以表示为每个儿子的方案乘积再乘上对应的系数，将这个系数预处理出来即可。
USACO21DEC Tickets P
TAGS：线段树优化建图，最短路
先注意到一个事实：从 $i$ 检查点开始到 $1$ 或 $n$ 检查点结束的最优路径一定形如一条链，且只需要考虑最新买的一张票。因为如果要用到老的买的票话，是不比直接在买了老的票后直接去往当前要去的检查点更优的。
那么我们就可以将票也当成一个点，建出一个最短路模型，其中每个检查点向能在它那购买的票连边权为票价的边，每张票向一个检查点区间连边，是容易线段树优化建图的。
考虑最终答案要求的是到 $1$ 与到 $n$ 的和，如果我们直接将最短路加起来的话会将它们的交集算两遍。考虑两条最短路的交集一定形如一段前缀相同然后分叉，那么我们只需要对于前缀相同那部分再跑一遍最短路就行了。
IOI2019 矩形区域
TAG：二维偏序
先考虑如何计算长或宽为 $1$ 的合法区域，注意到这个合法条件等价于中间的最大值小于边界两边值，那么考虑一个最大值至多贡献一个合法矩形，因此每一行的合法矩形是 $\mathcal O(m)$ 的（每一列同理）。
考虑将上面计算的东西合并。朴素的想法是枚举矩阵最上方的行合法区间（因为总数是 $\mathcal O(nm)$ 的），然后枚举上端点在这个区间右端点的列合法区间，能够造成贡献当且仅当他们组成的矩形每一行都存在一个与枚举的合法区间相同的合法区间，列同理。
为了加速计算，我们用桶计算出每个行合法区间向下最多有多少个相同的，列合法区间向右最多有多少个相同的。然后计算的时候限制变成了行区间的长度小于等于列区间的延伸长度且列区间的长度小于等于行区间的延伸长度，这是一个二维偏序问题。