PKUSC2023 游记

· · 个人记录

Day 0

和同学一起请日语酱吃了餐饭，加了花群。

Day 1

和花群网友面基，但没新认识几个人。加了川子好友。

考试。

开一题看一题。

本来像直接写 $\text{exKMP}$，但觉得二分哈希应该也能过，就先写这个。 先暴力实现了哈希比较的部分，交了一发，直接过了？ 检查了几遍，发现是真过了，此时是 $13:25$。 然后开 $\text{T2}$，想了一会儿，想到了容斥。我们枚举存活的时间 $t$，然后钦定一些位置没有被排除。发现贡献形如 $p^t$，那就不用枚举 $t$ 了，直接无穷级数求和就行。 随便写了个多项式做法，可能是 $O(n^6)$ 的。交上去拿到了 $n \leq 50$ 的分。此时是 $14:10$。 然后开始优化，发现枚举预言家是不必要的，钦定就行了。因为一些原因，一开始写的时候两边的 $\text{dp}$ 长得不一样，然后就只在前一半钦定，但对于 $x$ 和 $n-x+1$ 都做一遍。 然后变成了 $O(n^5)$ 的。又优化了若干地方，交上去还是只能过 $50$ 的包。 在本地跑了一下，发现 $n < 135$，$135 \leq n < 140$ 且 $x >10$，$n \geq 140$ 且 $x>35$ 的包都能跑过去。 又卡了很久的常，到 $14:50$ 决定放弃。突然发现可以直接对于跑得慢的部分打个表，就挂上去了。 然后开 $\text{T3}$，很顺利的在 $15:35$ 左右写完了 $52$ 分。表在写的过程中就打好了，拼上去把 $\text{T2}$ 过了。 然后继续看 $\text{T3}$，想到了根号重构，但没想到可以直接做除法。然后想到了 $\text{C}$ 性质的分治套分治法法塔做法，到最后也没调出来。 总分是 $100+100+52$。 ### Day 2 早上听了个讲座，个人感觉比较高效，没有很拖沓。 下午考试，想着能把总分凑上 $400$。 开 $\text{T1}$，想了一会儿会了根号重构。先写了一个暴力，交上去，发现题目读假了。 已经过去半小时了，觉得有点慌。 把暴力改对，又想了个根号重构，写完了，交上去，又发现假了。 一个小时过去了，只有最基础的暴力。 又想了一会儿，才发现可以平衡树维护。但是不会求子树 $\text{size}$ 啊，这是 $\text{LCT}$ 经典题，但我不会 $\text{LCT}$。想着怎么用根号重构来替代，越想越烦，决定不写了。 已经 $15:00$ 了。 赶快去开后面的题。给 $\text{T3}$ 写了个 $15$ 分暴力，却总是 $\text{TLE}$。给 $\text{T2}$ 写了个暴力背包，却总调不对。非常自闭啊。 先把 $\text{T1}$ 的 $45$ 暴力写了。 然后去给 $\text{T3}$ 卡常，结果还没怎么卡就拿到那 $15$ 分了。把之前 $\text{TLE}$ 的代码再交一遍，居然也拿到了，还只跑了 $\text{800ms}$，不懂哦。 给 $\text{T2}$ 写了个爆搜，拿到了第一档分。继续调背包。改了改初值和其它一些细节，又交了几遍，才拿到 $35$ 分。 然后想 $\text{T1}$ 的 $65$ 分，发现会了，很快写了。 剩下大概 $\text{30min}$，会了 $\text{T2}$ 中 $a_{i,j}+b_{i,j}=100$ 的包，却到结束也没写对。 最后只有 $65+35+15$，非常自闭啊。 出考场发现 $\text{T1}$ 不用 $\text{LCT}$，$\text{T2}$ 直接爬山就有 $85$ 分，更加自闭了。 --- 总分没打过去年。