游击 CSP-S

Tiffake · 2025-11-01 11:56:54 · 生活·游记

省流，高一老登可以直接打NOIP。
估分：100+[64,80]+[0,75]+8=[172,263]。
实际：100+56+25+8=189，输麻了属于是。

前一天和上午总感觉啥都没干，一直在水讨论。

正文

在本校考的，并且和去年同一个机房，同样有发零食的保留项目。

先开的 T1，5 min 想出来做法，但是实现了一小时，没办法码力太差了。
然后看了看 T2，1 s 会 O(2^km\log m)，然后就没啥思路了，转 T3。
发现 T3 看起来比较撇，但是还只会用 hash 打了个 O(n+qL^2) 的垃圾暴力，然后意识到其实只有中间的一段会变，于是写了个只跑两边相同的剪枝，随机数据下，大概是 16q 左右。
补：忘记判 t 不相等了……
发现这大概率可以骗到不少分，于是想了想特殊性质 B，然而不会。
转 T2，瞪了一会儿，发现其实只需要保留最小生成树上的 n 条边跑就行了，于是有了 O(m\log m+2^knk\log n)。
补：用了 set，除了 luogu 都被卡常了……
看 T4，发现性质 A 其实很好打，但是只剩 10 min，所以只打了 O(n!)。

不管怎么说，-S 考得再好 NOIP 也不一定翻盘。

彩蛋

为了能够进入迷惑行为大赏，我在代码里加了 4 首我喜欢歌的片段，能猜出来的可以私我并获得一个关注。