5.21
口胡了UOJ Easy Round 1，想了大约20min
- UOJ12
考虑到
\(a=a_1g,b=b_1g\)，那么 \(gl=ab=a_1b_1g^2\)，因此 \(g|l\)，设 \(l=l_1g\)，则有 \(a_1b_1=l_1\)，而 \(a+b=g(a_1+b_1)\)，显然 \(a_1+b_1\) 最大值是 \(1+l_1\)，最小值是 \(2\sqrt{l_1}\) （\(l_1\) 也是一个完全平方数）
则 \(a+b\) 最大值为 \(g(1+l_1)=g+l\)，最小值为 \(2g\sqrt{l_1}=2\sqrt{l_1g^2}=2\sqrt{gl}\)
代码 - UOJ13
对每个点维护一个 link，快捷方式就跳 link 即可
代码还没写
5.22
大课间的时候口胡了一下昨天剩的 C 题
- UOJ14
首先边权已经排好序了，因此符合 Kruskal 的过程，如果只有 Add 和 Return 操作，那么可撤销并查集就能维护。
如果只有 Add 和 Delete 操作也是容易的，直接 Delete 即可
问题就是如果 Return 的上一个恰好是 Delete 操作，复杂度就炸了
事实上，当我们遇到一个 Delete 操作时，考虑
如果下一个不是 Return，就真的执行 Delete；
如果下一个是 Return，则只需要看这 \(k\) 条边之前的答案，根据我们的操作规律，这必然是之前某一时刻的情形，直接记录下每次的答案即可。
可撤销并查集：按秩合并，不路径压缩，每次直接撤销。
代码还没写
晚上上数竞课去了，讲了数码相关问题，感觉很适合放在高联 T1/T2
5.23
学whk去了
5.24
- ZROI 1533
先 manacher 维护出每个位置的最大回文半径 \(z_i\)
问题转化为，统计下列点对 \((i,j)\) 数量，满足以下四条限制：
\(i<j\)
\(s_i=s_j=\text{'#'}\)
\(j-z_j\le i+1\)
\(i+z_i \ge j-1\)
第二条是容易的，直接扔掉不满足的
注意到如果 \(i\ge j\)，那么必然满足最后两个条件，于是我们直接统计出满足最后两个条件的点对，最后减去 \(\binom{n}{2}\) 即可。
对于后两个条件，转化一下式子
\(j-z_j-1 \le i\)，\(j \le i+z_i+1\)，令 \(l_j=j-z_j-1,r_i=i+z_i+1\)
则要求 \(l_j \le i\)，\(j \le r_i\)，看做点对 \(A_j(l_j,j)\)，和 \(B_i(i,r_i)\)，则要对所有 \(B\) 类型点统计在它下方的 \(A\) 类型点个数，二维数点即可，复杂度 \(O(n\log n)\)。
代码
做了些期望线性性相关的例题
-
CF 280 C
给定一棵有根树，每次随机选一个未被删除的点，将以它为根的子树删除，求删除整棵树所用的期望步数。
考虑到每个点可能会被所有祖先删掉，设深度为 \(d_i\)，则最终每个点被删的概率是 \(\frac{1}{d_i}\)。
设 \(X_i\) 为每个点期望变量，\(0\) 表示不删 \(i\)，\(1\) 表示删 \(i\)
答案就是 \(E(\sum X_i)=\sum E(X_i)=\sum_{i=1}^{n} \sum_{X_i\in {0,1}} W(X_i)P(X_i)=\sum \frac{1}{d_i}\)。
代码 -
洛谷 P4316
对每条边设出期望变量 \(X_i\)，
答案就是 \(E(\sum X_i)=\sum E(X_i)=\sum \sum_{X_i \in {0,1}} P(X_i)W(X_i)\)。
只有经过这条边时 \(W(X_i)=w_i\)，否则 \(W(X_i)=0\)。
于是答案就是 \(\sum P_iw_i\)，\(P_i\) 是经过这个边的概率，设这条边是 \((u,v)\)，那么 \(P_i=\frac{p_u}{d_u}\)，\(p_u\) 是经过 \(u\) 的概率，\(d_u\) 是 \(u\) 的出度，问题转化为求 \(p\)。
对于 \(p_v\) 有转移方程 \(p_v=\sum_{(u,v)\in E}\frac{p_u}{d_u}\)
代码