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 发挥还行，至少拿到了大众分，而且每道题的代码都比较好写，有充足的时间思考。

Day 2

上午听讲座，大力宣传了北大计算机系。

考试之前在会议室睡觉，考试之前感觉心情还不错，如果发挥正常的话应该能拿大众分。

然后就发挥失常了……

T1 给定一个队伍，支持三种操作：在编号为 \(x\) 的人后加入一个人；将编号为 \(x\) 的人的前驱改为 \(y\) ；查询编号为 \(x\) 的人的位置。

考试过程中想到了一种感觉正确的做法，写了之后却一直在 WA ，手捏了几组数据都没有问题，然后调了一场也没调出来。

T2 给定 \(n\) 个组，每个组有 \(m\) 件装备可以选择，每件装备有两个属性 \(a,b\) ，每组只能选一件，询问给定 \(A,B\) ，选择的装备会贡献 \(A,B\) 相应的 \(a,b\) ，求解最终最大的 \(A\times B\) ，输出的结果允许与标准答案存在偏差。

只写了暴搜的分。

T3 完全没有思路。

Day 2 简单概括就是心态完全被 T1 搞炸，主要原因可能是我写数据结构的能力不够，然后考场存在一些策略失误，导致 Day 2 几乎保龄。

以后需要调整策略，考试的首要任务是写暴力，暴力分的性价比基本优于正解。

胡言乱语

返程的时候在车上看了《玻璃之花与崩坏的世界》，有些时候，感觉自己就像程序一样，没有喜怒哀乐，如果是以前的我，或许会因为 Day 2 的保龄难过很长时间，但现在，无论是文化课和奥赛，无论是取得成绩还是遇到挫折，都很难动摇心中的情感；如果原因是这些都是人生中微不足道的小事，那么现在我究竟应该追求什么？

但目前来看还是只能把握当下的机会，无法改变清北营寄掉的历史，只能暂时相信即将破灭的幻想和希望。