PKUWC 邮寄

· · 生活·游记

原来不能写“tang”。

day0

上午下午在摆烂。车上睡觉。

晚上还在摆烂。一题都没看。

day1

不是你四个菜还要选两荤两素啊？？

试机，t1 好像是那个没有场切的题，t2 好像在哪里见过（确实见过），但是忘了怎么做了。

正赛，先随便看一眼，t1 是什么奇怪的数据范围，t3 题面好长，吓都吓死了。t1 苦战一个小时，发现 3 3 我只会 7，n=3 交了一个 \frac{m(m+1)}2+1，发现不对。这时只拿了 10 分。遂开 t2。

考虑了半个小时。你发现 x 增大时是一个类似合并的过程，显然只有 O(n) 次合并。用一个长剖状物维护每次合并的节点，启发式合并。每一个集合的贡献大概在一个阶梯型里面，那合并两个集合相当于删掉这两个阶梯型的交。那就再写一个 CDQ 就好了。这样有点麻烦，写了好大一坨，交上去 WA 了。静态查错，错了好多，但是没有。开始对拍，发现 shell 不会写。倒腾了好久，发现求阶梯交的时候细节写少了。惊恐地发现还剩 20 分钟！赶快改成了每次直接去掉原先的阶梯型，加上若干小矩形的大常数写法，样例一遍过了。交上去 77 分。发现每次会把一些点删掉又加回来，把这个去掉大概能从 6 倍变成 4 倍常数。交上去过了。

这时还剩 9 分钟。开始闭目养神（实在是没绷住，应该就我不会 t1）。

day1 10+100+0 遗憾离场。旁边的老哥 100+100+20，是我的两倍 /jk

发现学校里还有一个人不会 t1！！！赢！

学校好像人均会 t1。。。

day2

讲座有 mc！

没有试机，中午可以多水一会。

立个 flag：day2 翻盘。

考前让我们再检查一下有没有没交的电子产品，旁边的老哥说了声被D然后跑出去了。

开考，t1 怎么是个交互，不会；t2 感觉有点难拿分；t3 一眼不可做，但是 sub124 还是简单的。

但是在 t3 上面浪费了一点时间，主要是 sub4 输入的 l,r 可能是 3e9，会爆 int32。

想 t1，发现我随便选两个点，记链长为 x，则我可以用 n+x 次操作找到一条边，用 n-x 次操作找到直径的一个端点，再用 2n 次操作找到直径的另一个端点，大概有 83 分。

那我现在会个 83+11+36=130 分？说好的 day2 要翻盘的！

想想 t2！

直接从左往右贪心为什么不优：你发现如果一次区间清理没搞满就不一定优。但是手玩发现从左往右，一次区间清理搞满了就绝对很优。那这设计状态 f_{i,j} 表示区间 [i,n] 前面拼上 j 的答案。状态数是 O(n^2) 的，直接记搜。

发现这玩意确实是对的，过了 n^2 的点。数组开大点就过了 c=1 的点，但是后面的点总是过不去。感觉这个状态数跟 c 根本没关系好吧！可能是数据造水了。

看看 t3，sub3 好像可以 O(nr\log\log r) 搞过去。写，对了。

今天突然有时间写暴力了！没去冲正解导致的。

最终得分：10+100+0+83+73+44=310

出考场一问发现 jiazhichen844 虽然 day2 被我翻了 94 分还是比我高 6 分。整天被小两届的大神吊打真不好受吧。

总结：

主要是 day1 爆炸了。以后不要对自己的代码能力太自信，写个比较高的暴力分也不差。

看到可能写不完的数据结构还是优先考虑其他题，不要把大部分时间放在这上面导致其他题目丢太多分。

同时前一天晚上的睡眠质量也比较关键。