题解还是得写，不能偷懒啊~
多校A层冲刺NOIP2024模拟赛19
图书管理
签到题
考虑最困难的部分是确定中位数，不妨钦定中位数，然后计算其贡献，然后考虑只枚举一个边界，另一个边界可以放桶里。
时间复杂度 \(O(n^2)\)。
两棵树
概率期望
考虑拆贡献，有等式
\[连通块个数=点数-边数 \]证明考虑图原本的形态是一颗树。
记点数为 \(d\)，边数为 \(e\)，则有
\[E(XY)=E((d_x-e_x)(d_y-e_y))=E(d_xd_y)-E(d_xe_y)-E(e_xd_y)+E(e_xe_y) \]-
\(E(d_xd_y)=\frac{1}{4}n(n-1)\)，考虑一个图中每个点的贡献即可计算。
-
\(E(d_xe_y)=\frac{1}{8}n(n-2)\)，同上。
-
\(E(e_xe_y)=\frac{1}{16}\sum_{\{u,v\}\in T}(n-1)-deg_{U,u}-deg_{U,v}+[\{u,v\}\in U]\)，同上。
时间复杂度为 \(O(n\log n)\)，瓶颈在判断 \(T,U\) 中是否有相同的边。
函数
特殊性质，trie，二分
考虑怎么判断答案的存在性，类比实数域上连续函数的零点存在定理，只要异或后的存在大于零的数和小于零的数则一定有解。
并且发现这个解一定在这两个之间，二分即可。
时间复杂度 \(O((n+q)(\log n+\log V))\)。
编辑
值键互换，hash，二分，DP
\(O(n^3)\) 的暴力 DP 是平凡的。
（ 即枚举 \(t\) 串的后缀，设 \(f_{i,j}\) 表示 \(s\) 的 \(i\) 个和 \(t\) 的 \(j\) 匹配上的最小编辑距离 ）
但是这个做法是很没有前途的，无法优化。
考虑一些性质，注意到 \(k\le30\) ，答案限制很小，考虑值键互换，并且两个串的长度之差只会差 \(k\)，所以可以设计一个只有 \(O(k^2)\) 的状态，即 \(f_{i,j}\) 表示编辑距离为 \(i\)，匹配上的 \(|t|-|s|=j\) 时，\(|s|\) 的最长长度。
还是考虑枚举后缀。
考虑如何快速转移，注意到匹配的情况是一个 "修改一个+一段相同+修改一个+一段相同..."，修改只会有 \(k\) 个，瓶颈在转移一段相同的，哈希+二分即可优化至 \(O(\log n)\)。
转移考虑增加，删除，替换，刷表取 \(\max\) 即可（ 注意与状态相匹配 ）。
统计答案时，对于每一个 \(j\)，加上最小合法（ 值等于 \(|s|\) ） \(i\)，即可。
时间复杂度为 \(O(nk^2\log n)\)。
注意转移时的边界问题。