CSP2024 确有问题记

cyffff

2024-11-04 20:44:23

Life & Travel

奔着 400 分去的。

初赛 96,不会 Linux 和数数。

开题看到 A 是个模拟,B 是个模拟,C 是个神秘 DP,D 没有直接的想法。

先花了 1.5h 过了前三题,2.5h 对线 D,这不稳了?

花了一个小时写出了一个 O(Tn^2\log n) 的东西,又花了大半个小时优化成了 O(Tn\log^2 n),测测能跑 T=64

诶诶,时间不够了,这能线性??

想到了 1\log 的优化方法,开冲,结果没冲出来。

后续就是拿到代码发现 DFS 结束时没有回溯,随便改改就写出了 $O(Tn\log n)$,能跑 $T=128$。 嘛,最后一次 CSP 了,心态也挺平常的。场上确实不会做 D,没调出 $1\log$ 只少了 8pts,没有犯之前同样的错误,也是一种交代了。