NKSWC2024游记
拓扑排序
定义
拓扑排序是对其顶点的一种线性排序，使得对于从顶点 $u$ 到顶点 $v$ 的每个有向边 $u \to v$ ，$u$ 在排序中都在 $v$ 之前。运行此算法需要保证图是DAG。
差分约束
说白了，就是给出一个序列内数与数之间的关系，可能是大小关系，也可能是作差的数值，让我们尝试还原整个序列。
首先，这两种问题都得先转化成图上问题来做。
subtask 1：大小关系
考虑建图：设一条有向边 $u \to v$ 表示 $b_u > b_v$。有解时构建出来的图是一个DAG，并且如果在上面跑拓扑是能够确定所有 $b_i$ 之间的大小关系的；无解时，图上会存在一个环。
例题：数列恢复（半模板题），Pustynia（线段树优化）。
subtask 2：作差数值
这种情况需要使用最短路。鸽一会。
输出方案满足“尽量”关系
首先我对于这个方案有一个谁在谁前面有很多个限制。
大致如下：
在满足所有限制的前提下，$1$ 尽量靠前。
在满足所有限制，$1$ 尽量靠前的前提下，$2$ 尽量靠前。
在满足所有限制，$1$ 和 $2$ 尽量靠前的前提下，$3$ 尽量靠前。
在满足所有限制，$1$ 和 $2$ 和 $3$ 号尽量靠前的前提下，$4$ 尽量靠前。
以此类推。
很多人可能认为这就是字典序，其实不然。考虑这组数据：
1 | 6 4 |
以及
1 | 6 4 |
这里放个结论：最终的序列是满足限制的前提下字典序最大的倒序。
有大佬证明了，在这里贴个链接。
例题：菜肴制作（板）。
二分图的判定
染色。
欧拉路
最灵活的一集。
首先是如何判欧拉通路和欧拉回路以及证明。
Theorem 1 无向连通图中存在欧拉回路当且仅当图中所有顶点的度数为偶数。
充分性：欧拉回路从起点出发对起点产生 $1$ 的度数，而后经过的除终点（也就是起点）外每一个点产生 $2$ 的度数，最后回到起点又对起点产生 $1$ 的度数。
必要性：考虑使用构造法证明。我们每次在图中寻找一条回路，如果这个回路是欧拉回路，那么结论成立；否则删除环上所有的边以及一些孤立点，明显剩下的这个子图的所有点的度数都是偶数但可能不连通，并且这个子图一定和找到的回路有一个公共点，那么再次以这个公共点为起点继续寻找回路并重复以上过程直到找不出来为止。找完后将这些回路串起来就是最终的欧拉回路了。
Theorem 2 连通多重图中存在欧拉通路且不存在欧拉回路当且仅当连通图中有且只有两个顶点的度数为奇数。
证明过程和上面的类似，这里不做阐释。
而如何跑欧拉路，上面证明给出的构造方案已经说得很清楚了。
例题：POLICE（很难看出来这是一道欧拉路的题目），丁香之路（与MST相结合）。
看到图论题不会做就想想能不能欧拉回路。——0htoAi
最小生成树
最小生成树大多数时候用的是它的一个思路，毕竟人家不太可能把板子明摆着让你写。
有两个算法，但是两个算法的本质都是贪心。
Kruskal
将所有边按边权从小到大排序，再依次加边，并用并查集维护是否会出现环，如果加入一条边后有环则不加。正确性显然。
如果有边是必选的话就可以提前在并查集里加边，后续不用做任何更改。
时间复杂度：$O(m \log m)$
谁完全图用这个算法我笑他一辈子。
Prim
从一个点开始每次选择与这个点相邻的最短的一条边，加入这条边和对应的点，再找距离这两个点最近的其他点进行添加，以此类推。
时间复杂度：$O(m \log n)$
图的连通性
这个知识点之前写过，这边建议出门左转二分图与图的连通。
例题：未整理。
耳
这个知识点在NKSWC的第【数据删除】场测试中出现了，因此咕一下（什么逻辑）。
并查集
几个小技巧。
删边倒序处理
如果出现删边类型操作的话，可以将询问离线下来倒着处理。
删点=新点
如果删除一个点之后不会出现任何与这个点有关的操作的话，可以记录一个 $id$ 数组，删点就直接弃用之前的点并建立新点。
撤销操作
注意数据范围。建边时记录操作序列，每次回溯直接重置 $fa_i$ ，这意味着并查集将不能路径压缩或按秩合并。
例题：没有。
单调/优先队列
单调队列优化DP
当状态转移是下面这种形式时，可以使用单调队列进行优化。
$$
f_i=\max_{j=l}^r f_j+val(i,j)
$$
即用单调队列维护 $j$ 的值，最终状态从单调队列的队尾转移。
例题：未整理。
带悔贪心
目前我见过的这种类型的题目用一只手都能数过来。
简单而言，就是把选和不选的情况分开考虑，一个直接贪心，另一个放到单调队列里等待后面取出。而一个不选的状态的代价是扣除选的价值再加上不选的价值。总之就是一个字：抽象。
这种题目应该是做多了才能看的出来吧。
例题：数据备份。
线段树
线段树优化建图
用线段树上的点来凑出一个区间。
如果有区间连点和点连区间同时出现的话要建立两棵树，一个负责入，一个负责出。
要考虑好大区间与小区间是否有关系，如果有也需要建边（目前来看都是有的）。
题目专版
数列恢复
有一个序列 $a$，长度为 $n$，且对于任意一个 $i(1 \leq i \leq n)$ 满足 $|a_i| \leq n$，定义 $s_{i,j} = a_i + a_{i+1} + … + a_j$，现在给定所有 $s_{i,j}(1 \leq i \leq j \leq n)$ 的正负性，输出任意一个合法的 $a$ 序列。
然而这道题给的是每段区间和 $0$ 的大小关系，无法转换到上述模型。因此我们考虑将原式中的 $s_{i,j}$ 转化为前缀和形式：$s_{i,j}=sum_{j}-sum_{i-1}$，这样就能转换了。套用模型，最后能够处理出来每个 $sum_i$ 的大小关系。
有一点细节是当 $s_{i,j}=0$ 时，也就是 $sum_{i-1}=sum_{j}$，跑拓扑更新到这两个点中的任意一个时要同步更新另一个。
Pustynia
给定一个长度为 $n$ 的正整数序列 $a$，每个数都在 $1$ 到 $10^9$ 范围内，告诉你其中 $s$ 个数，并给出 $m$ 条信息，每条信息包含三个数 $l,r,k$ 以及接下来 $k$ 个正整数，表示 $a_l, a_{l+1}, \ldots, a_{r-1}, a_r$ 里这 $k$ 个数中的任意一个都比任意一个剩下的 $r-l+1-k$ 个数大（严格大于，即没有等号）。需要任意构造出一组满足条件的方案，或者判断无解。
这一道题和这道题差不多，都是建图跑差分约束模型，但是此题需要使用线段树优化建图。
菜肴制作
给定 $n$ 个菜肴和 $m$ 条限制条件，对于每个限制条件 $x$ 和 $y$，表示 $x$ 号菜肴必须先于 $y$ 号菜肴。让你求出在满足最小号的菜肴尽量靠前的前提下次小号的菜肴也尽量靠前，次小号的菜肴尽量靠前的前提下次次小号的菜肴也尽量靠前，并以此类推。（注意不是字典序！）以此类推，最优的菜肴制作顺序。如若无解，则输出
Impossible!。
如题。
POLICE
有一个 $n \times m$ 的矩阵，每个位置上有一个数，现在要将这个矩阵通过两种操作还原成初始状态，保证原矩阵里的数和现在的数一致。
- 操作1：交换同行两个相邻位置上的数。
- 操作2：交换任意两个位置上的数。
请求出需要的执行操作2的次数最少是多少，或者输出无解。
先把例题摆着，因为这道题我也没过。
丁香之路
数轴上有 $n$ 个点，表示的数分别是 $1\sim n$，有 $m$ 条连接两个点的边（独立于数轴的），这些边必须走一遍，求 $s$ 到其他点的最短路。
搁置一下。
数据备份
搁置一下。