CSP-S 寄

· · 生活·游记

Day 0

按照学校惯例考信心赛。

然后被打爆了。

只切了 T1 然后发现其实后面的题也没啥人过。

这 TM 是信心赛?

然后查出来 T4 是 CF *3500。

这下彻底没有信心了,先叠一层 debuff。

Day 1

睡的不算好,上午在机房复习模板。

中午吃完饭后,再次回到机房,玩了一会 OI 重开模拟器,爽到了,信心又回来了。

下午到达考场,在校门口看同学打农,然后发现他玩战士战绩 2-6-11 看笑了。教练都没有绷住,说他又菜又爱玩。

进入考场,发现旁边就是学短,有点紧张,互相祝福了一下。等了一会有点犯困,直接打开极限魔力,爽!

然后晚上一直睡不着

T1

一眼贪心,发现它只会有一个社团超过 n/2 就做完了,直接贪心加入然后动态调整即可,然后发现本地大样例跑不过,直接吓哭,写了一个快读才跑了 921ms,期望 100pts。

T2

然后开 T2,想了半个小时发现控制查找每个状态时加入的边是突破口,然后想到可以继承之前的状态,这样我们在搜索的时候每一次只用加入一个点这样求一次 MST 的时间复杂度就被缩减到 O(2n \log 2n),然后发现貌似能过,直接写出来。

然后死活过不去样例,发现把题读错了 k 个点是额外的,还好可以调整一下,终于把样例过了。

又跑不过大样例,甚至这个大样例还不是极限数据,又被迫写了个快读,然后还是没跑过,n=1000 的数据跑了 1.2s。

本地还是太慢了,后来在 luogu 上测,极限数据跑了 1.5s,有点悬,但是 64pts 应该是比较稳的。

写完只有 1h10min 了,调试太久了以及电脑太烂了。

T3&&T4

没啥好说的,全是暴力。

T3 先把题看错了,认为不可做,因为认为一个替换对,可以进行多次替换,直接先跳了。

T4 计数DP,有点困难,推了 30min 没推出来,放弃了写了个 8pts 暴力走人。

又回来看 T3,终于发现把题看错了,然后想写 hash。结果发现时间不够了,匆忙写了暴力判断就走了,期望得分 10pts。

后记

woc,我 luogu 上咋 RE 了。

然后发现快读写错了,如果有行末空格或者 \r\n 就直接睡觉了,不过貌似没有。

luogu RE 可能是因为数据是在 Windows 下造的?

100pts+[64pts-100pts]+10pts+8pts=[180pts-218pts]

或者 0pts?