CSP2024游记

· · 生活·游记

久违的 emacs。

snake 打到 68 分边上的同学问我系统登录密码，然后忘了暂停就似了。

尝试了一下 tetris，一开始还行然后越打越唐形成了正反馈调节。

打完缺省源后监考老师说不要打代码，有监控，整得我心里一惊，但转念一想反正就是个 CSP，也无所谓，而且一般也不真管，看了一下摄像头位置感觉我小屏打代码应该看不见。

然后速通 ABC，本来不太想写对拍的但想到已经是最后几次写对拍的机会了还是拍了一下 C，然后调了一会写出了 D 的 O(mT\log n)，拿最后一个大样例询问次数改到 256 跑了 6.6s。还有快 2h，出去上了个厕所喝了口水。

思考了很久怎么优化，发现 dfs 的过程怎么搞都不太能合并或者类似的。最后想到了个给所有询问放一起整体二分的思路，这样每次更新信息都是一个区间，开始改，新写的源代码起名叫 faith.cpp，但写的时候真的不怎么有 faith，就大样例 134 挨个调，人眼比对两个代码实现逻辑上的差异，最后好像是还剩 20 分钟左右的时候调出来了，真的没想到。

跑了一下极限数据稳定在 0.9~0.95s。最后就差一个对区间修改的优化，可以用并查集实现，但没时间写了。尝试改了一下，只优化了一处，发现并没有快多少反而慢了，但还是交上去了。之后又改了一处答案不对了，仔细想想好像合并的时候有些问题，于是又赶紧回退，因为前面的的已经被覆盖了。交上去后发现文件名错了，赶紧改，看了眼时间，还有 40s，稳。之后把一些无关函数和变量删了又在结束前十几秒交了一个，希望没出什么问题，但测了最后两个数据应该是没问题的。总之希望能过吧。

回想了一下，预处理时找断点其实暴力找复杂度是对的，因为保证了深度是 O(\log n)，但当时花时间改了个两头查找的启发式分裂。最后应该给单点修改另设一个数组记录而不是跟差分放到一起来减少常数而不是写并查集。调出来后的那段时间确实很匆忙，好多版本都被覆盖了，这其实是很危险的，以后应该注意。

就这样吧，尽力局。感觉如果把并查集维护连续段加上应该是正解，复杂度也有可能还是有问题，但应该没法卡。

T4 居然评了个黑？但可能确实能算，毕竟我可能还不知道正解。

Upd

CCF 怎么又双叒叕成小丑了，整个密码都能被破解，没绷住。

T4 洛谷民间数据最后两个点不到 0.3s，但前面三个点 RE 了，离谱，找了一下问题发现是在 n 恰好为 2^k 并且询问了 n 的时候会无限递归，前三个点刚好是 n \le 8，就挂了，可能放不过去了。估分 100 + 100 + 100 + 88。

很佩服当时能想到那么真实的比喻（

MX 好像放过去了？不懂。