记录：2025-1-5 讲题
Chenhaoxuan
·
·
算法·理论
linxudong
题目：CF2013E Prefix GCD
贪心。由引理及放缩，可以推出第一位可以选出最小值 minx。
引理：a<b，则 a+\gcd(a,b)\le b。
接下来的有效结果为 \gcd(a_i,minx)。
推广，同理可得，每次应该选取与当前值 \gcd 最小的数字作为下一个数字。容易得出结论。
## [_biLang_](https://www.luogu.com.cn/user/1124929)
题目：[P3731 [HAOI2017] 新型城市化](https://www.luogu.com.cn/problem/P3731)
因为团不超过两个，所以原图是二分图。
在补图上最大团等于最大独立集。为了找到一条边连接使得最大团大小增加，问题转化为删掉一条边使得最大独立集增加，即最大匹配减少。
手模样例，先跑一遍网络流求最大匹配，不难发现：
**假若一条匹配在残量网络流上的一个环中，那么它就是可以被代替的（即在一个强连通分量之中）**。对残量网络进行缩点，两个端点不在同一个强连通分量中的匹配边可以作为答案。
## [s_mayunfeng](https://www.luogu.com.cn/user/216347)
题目：[P4830 选择题](https://www.luogu.com.cn/problem/P4830)
题意简述：有 $N$ 个选项，最开始随机蒙，会进行 $N-2$ 次删除操作，必须在其中 $K$ 次删除操作后更换自己选择的答案，求最优策略下选到正确答案的概率。对 $10^9+7$ 取模。$1\le K,N\le10^5$。
最特殊地，$K=0$ 时，$P=\dfrac1n$。
特殊地，$K=1$ 时，$P=\dfrac{n-1}n$。
推广到 $K\in[2,n]$，不妨钦定是否选中正解的最后一次更换。设最后一次更换时包括当前选择的选项共有 $x$ 个选项，前 $K-1$ 次更换获得错解的概率为 $P$，那么更换后选到正确答案的概率是 $\dfrac{P}{x-1}$。当 $P$ 确定时，$x$ 与概率负相关。所以最后一次更换在最后一次删除后，得到的概率 $P$ 最高。
类似地，设第 $i(i\ge2)$ 次更换时剩下 $x$ 个选项，前 $i-1$ 次更换获得错解的概率为 $C$，那么当前选到错误答案的概率是 $C\times \dfrac{x-2}{x-1} + ( 1-C ) = 1-\dfrac{C}{x-1}$。当 $C$ 确定时，$x$ 与获得错解的概率正相关。
所以最优策略为：在前 $K-1$ 次删除错解后更换，第 $K$ 次更换放在最后一次删除错解之后。利用上述式子可以将概率算出来。
## [Chenhaoxuan](https://www.luogu.com.cn/user/493766)
题目：[CF1976D Invertible Bracket Sequences](https://www.luogu.com.cn/problem/CF1976D)
枚举左端点 $l$，并对区间 $[l,n]$ 的范围进行区间翻转。
> 补充：合法括号串的第二定义：
>
> - 将 `(` 视作 $1$，`)` 视作 $-1$，则整个序列的和为 $0$。
>
> - 原串的任意一个前缀串的和 $\ge 0$。
所以，我们用线段树维护区间最小前缀。一个位置上的点能作为答案，当且仅当以之为前缀的串和与以 $l$ 为前缀的串和相等，且任意一个区间前缀 $\ge0$。这等价于区间最小前缀 $\ge0$。容易发现具有单调性。
具体地，使用 $\log n$ 实现区间翻转，然后可以在线段树上二分，或者二分后在线段树上查询，时间复杂度 $O(n\log n)$ 或 $O(n\log^2 n)$。
当然还有线性做法，见第一篇题解。
## [chuazen](https://www.luogu.com.cn/user/821073)
题目：[P5905 【模板】全源最短路（Johnson）](https://www.luogu.com.cn/problem/P5905)
题意：求全源最短路。$n\le3000,m\le6000$。
Floyd / Bellman_Fold / Spfa 太慢，dijkstra 无法处理负权边。
我们可以先用 Bellman_Fold 判负环，然后采用对边权的一定的改变，使得边权为正，然后 $n$ 轮 dijkstra 求解。直接对每条边加上一个数字的做法显然是错误的。
我们新建一个虚拟节点 $0$。从这个点向其他所有点连一条边权为 $0$ 的边。
接下来用 Bellman-Ford 算法求出从 $0$ 号点到其他所有点的最短路，记为 $dis_i$。
假如存在一条从 $u\to v$，边权为 $w$ 的边，则我们将该边的边权重新设置为 $dis_u-dis_v+w$。
> 证明：见第一篇题解，采用势能分析法可以证明边权与原图是相对等价的；使用三角形不等式证明不存在负权边。
接下来以每个点为起点，跑 $n$ 轮 Dijkstra 算法即可求出任意两点间的最短路了。令转换后 $u,v$ 间的最短路长度为 $Dis(u,v)$，则答案的 $ans(u,v)=Dis(u,v)-dis_u+dis_v
时间复杂度是 O(nm\log m) 。
寒假讲课安排
| LG name |
上课内容 |
上课时间 |
| MengShang |
虚树 |
1.17 |
| chuazen |
树链剖分 |
1.19 |
| linxudong |
LCT |
1.20 |
| s_mayunfeng |
(ex)KMP |
1.21 |
| biLang |
数学，数论 |
2.7 |
| Chenhaoxuan |
二分图相关 |
2.8 |
| youkasgs_wyb |
构造 |
2.9 |
| chuazen |
KDT |
2.10 |
| MengShang |
后缀自动机 |
2.11 |