CSP2022 暴毙记

Konjac_16 · 2022-10-25 22:31:41 · 个人记录

Day -3：

SN 的疫情愈发严重，好在省内特派员还在拖时间，许是有望保留 csp 的吧。

今日下午考了一场 tsx 大佬出的模拟赛，全场被虐，只会暴力……（怵惕人在群里被反复鞭尸）。

Day -2：

微暗的傍晚，进食归来，突闻：“特派员声称，SN 的 csp 要取消了”，我：“？？？”。

Day -1：

事情正在起变化，机房同学发现，其他省份的报名网页，皆有说因疫情原因取消，而 SN 上却依旧空无一物。遂讨论起了 csp 复活的可能。

下午的信心赛打成了破防赛……

Day 0：

不少人向特派员发的邮件得到了回应，似乎事情已经明朗：SN 的 csp 的确是要取消了。

释然之下，我于是放弃了复习，转而去学 LCT 了。

然而，事情似乎并不想发展的这么简单，它励志要像坚不可摧的马奇诺防线一样，来一次事态的反转：

于是，在下午 4 点时，无论是在卷题、颓圮，亦或是直接摆烂学 LCT 的我，都突然收到这样一条震悚的消息：

一时间，各种言论蜂拥而来。

不少感激 CCF 终于恢复 csp 的；更多的却是被隔离在家无法参赛的，身在考点数百公里外的，他们或是唾骂着、或是无力的祝福着、或是转而将矛头对准了疫情。

毕竟，事情的反转已经够多了，这很有趣，却也并不有趣。在比赛前一天才发布相关的通知，触碰到了多少利益相关，可能我也永远不可得知。

对此，我也无法有太多心理波动，下午打球，晚上颓圮，依旧酣然大睡一场，直至次日 10 点。

Day 1：

提前一小时坐车来到了考点：高新一中沣东中学。与 lkx，lyh，wgx，yql 等互 % 一波，面基了 zzt。

进入考场，我尝试快速打完一段缺省源，只恨键盘的键位很难受，严重降低了打字速度……

打完后进行编译………………蓝屏？？？！！！

好了，这个电脑废了……

我于是找到监考换到了最后一排的电脑上

（Rp 还不错，最后一排较清净且整场再未出现电脑蓝屏现象）。

飞速地打完了缺省源，解压了文件，然后开始了这次 csp 的征程。

花了 10 分钟浏览了一下四道题。

• 感觉 \text{T1} 不太有思路。

算一下大概有 40 + 65 + ? + 52 = 157 的保底。

• 然后开始开 \text{T1}，先无脑 BFS 把每个点能到达的点建出图，接着写了个无脑 O(n^4) 暴力。

这时算上读题，已经过去了 35 分钟。

继续冲 \text{T1} 正解。发现题意相当于有一无向图，找最大权五元环，且 1 为起点。

我 yy 了 Floyd，dp，折半，乱搞等多种做法，终未嘴出正解。

此时时间指向 15:17，我掂量了一下时间，决定再嘴 3 分钟就换题。

灵光一动，这不 sbt 吗？我直接 O(n^2) 维护点 1 往外走两步到达点的权和最大值、次大值、第三大值，和这些值的转移来源，然后不随便 O(n^2) 一下就完了吗？

花了 15 分钟飞速打完，中间打的时候为图省事，感觉前 3 大值有点细节，好像只做最大、次大也没问题?（记住这句话……）在调试的时候还加了句 \text{continue} 判断。（记住这句话……）

去测大样例，过了。去对拍，欸？怎么用不了 fc？试了 5 分钟，发现不是我的问题，似乎考场的电脑有问题。

慌乱下，我想出了把输出文件 freopen 进来，再读入到数组里暴力比对。

此时时间指向 15:40，历时 70 分钟，\text{T1} 对拍 2000 组无误，就不管了。

• 去开 \text{T2}，飞速把 O(n^2q) 的 40 分暴力打完了。

手推一下，发现只要分别求出两方的正负最大最小，然后随便分讨一下就能过。

飞快写完，调试花了不少时间，终于在 16:43 时过掉了 \text{T2}。这时还剩 107 分钟，必须抓紧打暴力了。

1. 每个点的入度为 1
2. 每个点都在一个环内

很显然，我的题意理解错了，正确的题意是每个点都能通向一个环，但是这一点我一直未曾发现。

我按照自己理解的题意打完了 \text{T3} 暴力，过掉了前三个大样例，便不再怀疑，去开 \text{T4}。

时间指向 17:24，仅剩一小时，按当时的估算，已有 240 分收于囊中。

• 飞速打完了 \text{T4} 的指数暴力。

接着迅速打完 k=1 的树剖做法，这样就稳拿 24 分了。

感觉 n<1000 可以随便写个 dijk 草过去，这样能多拿 28 分。

又感觉 k=2 好像可以贪心一下，大概能多草 36 分。

两条路摆在了面前，而我选择了第二条，从此决定了最后 40 分钟的命运。

我死命地尝试调出 k=2，终是无果，在最后 10 分钟发现贪心显然是假的，无奈之下，只好去检查前面的代码。

按这时的估算，分数是 100 + 100 + 40 + 24 =264。

赛后：

问了一下周围的人，momo_li 估 360，yzy 估 272，szp 估 282……总之基本上除了 lzj、whm，基本上都估在 250 以上。

交流之下，他们说 \text{T3} 性质是一个基环内向树，当时我没多想，只当是自己没有看出性质。

同时，吐槽考场的也不在少数，有两个考场的电脑，一编译即蓝屏，致使不少人代码丢失。我所在的考场无法使用 fc 命令，许多人都没有测大样例，lzj 因此爆挂 \text{T1}。

考后的 gxyz，还搁那借机宣传学校？我只能说，这波属实是反向宣传。

晚上到家，我复盘了一下 \text{T1}，发现必须讨论前三大，只有最大次大显然会挂。但是民间数据好像都不太卡这个。

Day2:

拿到代码了。