PKUSC 2023 游记

Day 0

由于下雨所以火车晚点 \(1\) 个小时，到达北京后几乎一直在摆烂，中间尝试看过杜教筛和 PAM ，然而确实看不下去，实际上考试也没有用到。

Day 1

早上去北大参加开幕式，之后试机写了后缀数组和 NTT 的板子，后缀数组对拍时调了半天才过，感觉下午要寄。

之后去未名湖边散步，心情放松了不少，不过早饭与午饭时间过于紧凑，导致胃不大舒服。

简单叙述一下考试内容的题意：

T1 给定两个长度相等的字符串 \(s,t\) ，对于每个 \(i\) 求解将 \(s_i\) 替换为 \(t_i\) 后整个字符串的 border 。

刚开始以为是魔改 KMP ，但是一直做不出来，断定 T2 和 T3 不可做后去想 T1 的正解，大约 2 个小时后产生了枚举答案的想法，设 \(t_i\) 替换 \(s_i\) 后 \(s\) 串的 border 长度为 \(len\) ，那么 \(s_{1,len}\) 最多与 \(s_{n-len+1,n}\) 有两个位置不匹配，于是大力分类讨论后发现只需要用二分 + Hash 求解 lcp 即可， Delov 说可以使用 Z 函数优化为 \(O(n)\) ，但是 \(O(n\log n)\) 也可以通过。

T2 给定一个长度为 \(n\) 的线段，其中第 \(m\) 段的位置为狼人，剩余位置等概率为预言家，预言家每次等概率选择一段连续的区间后，可以得知这段区间是否为狼人，计算预言家得知狼人位置的期望次数。

不会多项式时间的算法，于是直接写状压 dp ，设 \(f_S\) 为狼人位于集合 \(S\) 时，找到其位置的期望次数，通过枚举下一次选择的区间进行转移。

T3 给定一棵树，树上每个节点有 \(p_i\) 的概率权值为 \(1\) ，剩余概率为 \(0\) ，一个节点的最终状态为当前节点权值与所有儿子状态的众数，保证儿子个数为偶数，求解根节点状态为 \(1\) 的概率。多组询问，每次可以修改一个节点的概率，输出根节点状态为 \(1\) 的概率。

没什么思路，直接写 \(O(n^2)\) 暴力跑路。

其实 Day 1 发挥还行，至少拿到了大众分，而且每道题的代码都比较好写，有充足的时间思考。