251215 图论&网络流选讲 && 251217 字符串选讲

P3295 [SCOI2016] 萌萌哒

使用 st 表套并查集维护，给 st 表上的每一层节点维护一个并查集：两个节点 \(x,y\) 在同一连通块当且仅当 \([x,x+2^k),[y,y+2^k)\) 两个区间对应位置数值相等。每次修改时将原区间拆分成 \(\log\) 个区间，然后在并查集中修改：如果 \(2^k\) 层中两个节点不在一个等价类，那么在并查集中合并并向下递归，否则直接返回。不难发现总共只会合并 \(O(n\log n)\) 次。

qoj9904 最小生成树

仿照上一题的技巧维护 kruskal 的过程即可，还需要记一下区间是否 reverse。

qoj14718 Meeting for Meals

先跑一遍 Dijkstra 求出最短时间 \(mx\)。然后考虑求每个点的答案，枚举会合边 \((u,v)\)，那么我们只关心到会合边另一侧用时最短的那个人。注意到一件事情：如果对方已经走到了 \(u\)，但是我还是没到，那么这条边肯定不是最优会合边。也就是说对于一条边我们也只关心到达 \(u\) 最早的那个人。于是跑一遍多源 Dijkstra，然后做完了。

CF1630F Making It Bipartite

发现不合法当且仅当存在三个数 \(a,b,c\) 满足 \(a|b|c\)。可以理解为每个数要么整除别人要么被整除。因此把每个数拆成两个点表示两种情况，然后再在矛盾的点之间连边，问题转化为最大独立集。发现将连出的边定向，可以形成一个偏序集，然后直接跑最长反链即可。

*qoj4218 Hidden Graph

尝试对每个点问出它的所有邻边。发现如果直接询问 \(x\to V/\{x\}\) 的边，那么交互库可能会返回 \(V/\{x\}\) 内部的边。为了解决这个问题，我们尝试将 \(S\) 划分为若干独立集，显然划分得越少越好。根据题目给出的操作次数估计一下大约是分成 \(k+1\) 个。尝试证明总是能划分为 \(k+1\) 个独立集，考虑删去那个度数 \(\le k\) 的点然后归纳，证毕。所以做完了。

*CF1033E Hidden Bipartite Graph

考虑找到原图的一棵生成树，这样就可以知道染色方案了。于是考虑 bfs 的过程，每条边用 \(O(\log n)\) 的代价二分出来即可。

P8456 「SWTR-8」地地铁铁

根据点双的性质以及一些观察，发现一个点对不合法，当且仅当以下几种情况：

两个点在同一个点双内，并且这个点双只有一种颜色的边；
两个点在同一个点双内，并且这个点双只有这两个点连接了不同颜色的边；（证明考虑枚举转折点，然后发现只要存在非起点和终点的转折点，都是合法的）；
两个点不在一个点双内，并且两个点的路径所经过的所有点双全都只有一种颜色的边；

于是跑一遍 Tarjan 求出每条边所在的点双，然后再把相同颜色的点双拉出来跑一边 dfs 求连通块大小。

P2178 [NOI2015] 品酒大会

对 height 数组从大到小排序，维护 sa 数组上的连续段合并，所以是容易的。

qoj10045 Permutation Recovery

首先将问题转化为：给你一个无向图，将它分解为 \(k\) 个排列置换环。发现因为是无向图的原因，所以直接跑二分图匹配是错的（因为一条无向边可能被用两遍）。于是先跑一遍欧拉回路，将其定向为有向图，此时因为二分图每个点的度数都是 \(k\)，所以一定存在完美匹配，再跑二分图匹配就对了。

P7361 「JZOI-1」拜神

考虑 SAM，考虑等价类对询问的贡献：对于等价类 \(p\) 和它的若干儿子，发现源于同一个儿子中的两个 endpos 是不会在 \(p\) 处产生贡献的，因为儿子的长度更长。因此，我们只需要考虑源于不同儿子的贡献。而且显然我们只关心 endpos 中两个相邻的值，因此支配对可以在线段树合并的时候顺带维护（在 pushup 时找出左右区间最近的两个点进行贡献）。支配对总数是 \(O(n\log n)\) 的，一个支配对产生的贡献形如一条平行于 \(x\) 轴的线段和一条 \(45\) 度的直线，可以用线段树简单维护。

CF1483F Exam

考虑从长串统计贡献，枚举短串的右端点，发现这样支配对只有 \(O(n)\) 个。