CSP2025 倒闭记

· · 生活·游记

省流:T2,T3都不会正解。打完回来真生气了。

上午

没去 J。痛失 AK 机会。

注意到 2025 新 NOI 大纲提高组添加了扫描线,bitset,manacher。随便复习了一下。

打了一些模版。还有一道 bitset 题小清新人渣的本愿。唐点解析:得知使用 bitset 之后对着乘积查询瞪了二十分钟才想到可以暴力枚举约数。

然后颓了差不多一个小时。玩了 魔法少女的魔女审判。好玩。

下午

进考场两瓶水被没收了,原因是 撕掉标签后还留有字迹。遂一口灌下大半瓶并且保持饥渴状态打了四个小时。

前几天晚上怕睡不好觉就没戴OK镜。导致视力极差,必须凑到屏幕前面看题。在中后段因为头太晕,几乎无法集中注意力。可能是没有想出 T2 的原因之一。

T1

顺利想到先贪心全部分配到第一志愿,再贪心地把超过半数的按照前两志愿的差排序扔到第二志愿。

调了一小会。过大样例约耗时 30min。

T2

看错题了。。。。

以为改造是把原本的点改成能往外连边的点,没发现是新建点。然后就想到了一个貌似能过的东西。写完之后一直调不对才发现读错题意了。浪费 1h。

这个时候因为视力已经头晕的不行。想到离正解仅差一步的 O(2^km) 做法,已经不敢再耗时间了。半个小时调过。

我为什么没想到只有 n-1 条有效边。天哪我简直是弱智。

分数应该是 [76,100]。加了特判性质 A 以及若干的优化。民间数据获得了 88 分。希望正式数据强度向大样例看齐吧。

做完上述事情还有 2h,去了一下厕所。

T3

简单记述一下我想到的东西。

首先对于一般情况,每个询问找两个 t 的最长公共前缀与后缀。容易证明合法的替换位置必须覆盖这两端东西中间的一段。

基于这个结论,并加上哈希可以使每个询问的复杂度基于 L1,总复杂度 O(qL1)。可以通过性质 A,得到 50 分。

糟糕的精神状态加上低下的码力导致我写/调了很久。写完还打了对拍,正确性应该没问题。问题在于如果我不用 MinGW 编译,连小样例都要 2s,用了就正常了。希望没有问题。

性质 B 也是容易的。按照 b 的偏移量分类所有模式串,然后根据 t 中的 b 偏移量和长度找一系列模式串,最后相当于一个三维数点吧。

没能写出来 B 性质,50 分草草收场。

T4

基于对 S T4 难度的错误预估,完全没动。

赛后~半个小时~ 一个小时左右独立做出来了。我真的完全避开所有翻盘点。

最后即使 T3 不挂分,也只有 [226,250]。无缘 WC 了吧。

赛后

没想到会输这么惨。赛后秒会 T2。

另外,花了一个小时 AK 了 J 组。我如何能至今没有 J 组一等。

希望 noip 能发挥好点吧。