8.18

T1

推式题．推式能力不强，消耗了大量时间．

由期望的线性，可以对每个位置分开计算贡献．

每个位置的地位对等．

对于每个位置，考虑进行 \(m\) 次操作后仍在该位置的信封仍在原位置的概率．考虑递推 \(F_i\) 表示 \(i\) 操作后仍在原位置的概率．

\[F_i=(\frac{n^2-(2n-1)}{n^2}+\frac{1}{n^2})F_{i-1}+\frac{2}{n^2}(1-F_{i-1}) \]

可以求出通项．也可以矩阵快速幂求解．

T2

简单树形 DP．

T3

抽象成树模型的题目．当然也可以用字符串 lcp 来理解吧．

考虑已知最终基因 \((A,B)\)，还原到 \((gcd(A,B),gcd(A,B))\) 序列是固定的．这是一个辗转相减的过程：若 \(A>B\) 则上一个操作一定是 \(A+B\rightarrow A\)．否则若 \(B>A\) 则上一个操作一定是 \(A+B\rightarrow B\)．对于 \(n\) 个基因和 \(q\) 个可能的祖先基因都构建出进化序列：若 \(A\) 加，则这一步为 \(0\)，否则这一步为 \(1\)．则问题变为了：对于 \(q\) 个子串查询 \(n\) 个子串中存在多少个是其前缀．

压缩 trie．老师上课提到了，但其实复杂度是错误的．
字典排序法．
考虑一个串 \(S\) 在 \(n\) 个串中作为前缀出现的次数，可以将 \(S+c_{mn}\) 和 \(S+c_{mx}\) 放入 \(n\) 个串中排序．其 \(rk\) 的差值就是中间串的个数．

T4

这种东西真的有用吗？

\(5\) 维偏序下 ploy log 的解法已经没有优势了．KD-Tree 的常数又是极大的．std 给出的是一个较轻量的 \(n^2/\log\) 做法．

将序列按 \(k=\log n\) 分块．对于每个块预处理 \(2^k\) 中比较情况的答案．这部分的复杂度是 \(O(2^kn/k)\)．转移时，块内暴力转移；快外整块整块得转移，我们需要快速知道一个数在这个块内的比较结果，然后我们就可以使用预处理的结果进行转移了．对于每个块，按 \(5\) 维各排一次序，预处理出集合(bitset) \(S_{d,i}\) 表示块内 \(d\) 维前 \(i\) 小的数的集合．求解时对于 \(5\) 维各做一次二分，然后将得到的集合与起来即可．这部分做一次的复杂度是 \(O(\log k)\)（请注意，这里算集合并集的复杂度忽略，其应为 \(O(k/w)\)，在 \(k\) 取到 \(\log n\) 时为 \(O(1)\)）．求解一个点需要的时间是 \(O((n/k)\log k)\)．那么查询的总复杂度为 \(O((n^2/k)\log k)\)．

将 \(k\) 代换成 \(\log n\) 感受一下全局的时间复杂度：

\[O(n^2/\log n+n^2\log\log n/\log n) \]

8.19

Day 3 大失败

T1

非常简单的 DP．

T2

惨剧从 P9120 [春季测试 2023] 密码锁中那个 更具有拓展性的做法 开始．

问题本质上在求最小的值域区间长度 \(\lambda\) 使得存在一个长度为 \(\lambda\) 的区间 \([pos, pos+\lambda]\) 中包含 \(n\) 中不同种类的点．

一种比较顺应思路的做法是值域上双指针．考虑存在一种最优情况的区间端点位于某个节点上，那么我们检查每个节点作为右端点包含 \(n\) 类节点的最短区间即可．

更具有拓展性的做法，本质上是一种数据结构反演．考虑在左端点上判定答案．考虑一个左端点 \(l\)，存在一个节点位置 \(pos\) 使得使得 \(pos\in [l,l+\lambda]\)．那么 \(l\in[pos-\lambda, pos]\)．那么问题变成：是否存在一个左端点被 \(n\) 类区间覆盖．

到此为止两种做法似乎并没有什么区别．第二种似乎还多了一个 \(\log\)——在这一道题上会惨死．

那么其拓展性体现在哪里呢：其在高维情况下较为优秀．如果问题变成：在二维平面上存在 \(n\) 类点，现在每类中选择一个点出来最小化距离极差（定义 \((x_1,y_1),(x_2,y_2)\) 的距离为 \(\max(|x_1-x_2|,|y_1-y_2|)\)）．那么从找到合法区间的方向思考问题就不是那么好做了．而考虑数据结构反演则变成了考虑若干矩形面积并的重叠是否存在重叠 \(n\) 次的地方．这个是容易实现的．

T3

DP．我没有完全理解．

T4

搜索．可以流．考虑每个点需要被覆盖，可以转化为上下界网络流．

8.20

T1

现在当前的决策只需要已知手上盘子的状态．设计 \(F_{i,j\in 0\sim 4, k\in 0\sim 4}\) 表示考虑前 \(i\) 个盘子操作完后，手上的两个盘子状态为 \(j,k\) 的至多得分．可以通过一些转移技巧使其转移次数变成 \(O(状态数)\)．

T2

按题意模拟即可．

T3

很有趣的题目．首先我们需要认同一个观点：\(+1\) 的操作只可能是某些位置的 DP 值 \(+1\)，\(-1\) 类似．这启发我们：对于一个操作，只需要知道所有需要修改的位置，即可以做到快速修改．

不失一般性地考察 \(+1\) 操作的影响范围：

其影响的范围是一个联通块．这是容易知道的．
影响范围中不存在两种类型的折角．为了方便叙述设影响集合为 \(S\)．
1. \((x,y),(x+1,y),(x,y+1)\in S,(x+1,y+1)\notin S\)．
2. \((x,y),(x-1,y),(x,y-1)\in S,(x-1,y-1)\notin S\)．
这是容易证明的．

考虑 \(+1\) 的点为 \((sx,sy)\)．先处理出 \(sx\) 这一行的扩展范围，可以知道这个范围是一个连续区间，不然会违反约束 2．接下来每行也都是区间，并且存在性质：左端点和右端点均单调不减．寻找所有端点后每一行使用 Bit 进行更新．那么单次 \(+1\) 时间复杂度是 \(O(n\log n)\)．