PKUSC 2023 游记

发布时间 2023-05-06 19:40:18作者: Galetx

Day -inf

THUSC 没过,但是 PKUSC 过了。

Day 0

请了一天假,周五早上就坐飞机去了北京。逛了逛北大,感觉挺大的,骑车骑了 10km。饭堂也还不错。

Day 1

早上开营仪式,见到了许多神仙的名字。然后测试环境,结果试机题好像就我没做出来。这下低能了。

中午浅浅休息了一下,12:40 的时候进了考场。

13:00 准时开题。

T1 白送 54 分,先水了再说。然后想了差不多 1h 没啥思路,就去看 T2。

T2 这个数据范围就很神必,想了想还是一分不会。遂开 T3。

先打了个 12pts 的纯 dp 暴力,随后发现直接动态 dp 就可以拿 52pts。写了差不多 1h,大概 15:15 的时候拿到了 52pts。貌似接着优化可能要高科技了,于是回去看 T1。

想了一会会了一个 \(O(nd)\) 的做法,\(d\) 是失配树的深度,也就是从某一个点一直跳 nxt 数组直到跳到 1 的步数。然后就写写碰碰运气,结果竟然过了。这时差不多 16:40,剩下的时间 T2 还是一分不会。再然后比赛就结束了。最终 100+0+52=152。

zzz T1 和我用同一个复杂度切了,看来数据是真水。lzy 和 zhy 都会 T2 的 23 分,直接状压就可以了,赛时根本没往状压上想,感觉有点寄。oyds 252,恐怖。