联合省选 2025 游寄

· · 生活·游记

Day -1

复习

晚上到了考点，在考点周围随机游走，发现某不认识校服学校的学生集体在酒店大堂内卷，怎么都这么卷啊 /ll。

SC 是 Windows + NOI Linux VM，不知道 VM 效率如何。

还有以下的运行时间均指 VM 下的用户态时间。

Day 1

教练通知 7:30 到考点门口，然后果不其然被在门口等了半小时才进去。

考场机器是 i5-12500 和 16GiB RAM。

然后似乎后知后觉可以在考前动电脑，于是只写了一个自动化备份，对拍器和 sgt 板子。

密码是 noi-2025-!!! 状物。

开题发现 A 是感觉出烂了的唐，15min 写完，测了下大样例发现 1.1s 左右，把 std::map 换成了离散化就 0.5s 了。

然后看 B 发现我会一个 O(\frac{qn}{B}+qB2^B) 的做法，具体就是先用手写的 w=B 的类 bitset 状物处理出可达点，和按照 a 的分块求出的合法点集取并，对点按照 B 分块，块内处理这个块在 2^B 种情况种分别的最大值，然后单次询问 O(\frac{n}{B}) for 一遍求，取 B=12 看起来很牛有很多分的样子。

写了，调了一会，通过了前两个样例，发现跑 n=6\times 10^4 的数据仅需幽默 10s，看起来期望得分 20，绷。

卡常，循环展开，现在变成了 8s。

把 B 改到 8，这样很多运算都可以位运算解决，变成 6.5s，似乎勉强有 44 了。

然后一拍脑袋发现 O(qB2^B) 部分可以直接 DP 做到 O(q2^B)，然后 6\times 10^4 的数据这下直接 5s 了，然后测一下 8 \times 10^4，幽默 8s。

卡常，继续循环展开，展开二维数组，unsigned char 的应用，if 改三目，针对部分情况做了些特化，其间还把 B 又改回 12 然后发现慢了。

最后是 8 \times 10^4 6.1s \sim 6.7s，感觉这下物理机应该可以过去了。

然后 C 草草写了个 8 分下班，荣获半小时垃圾时间。

出场发现怎么大家都会 C 的 52 但不是 B 的 88，感觉这个 B 的 88 比 C 弱智一万倍。

下午在成都市范围内随机游走。

Day 2

密码是 hello_world，听说有人考前试出来了。

考前写了 sgt 和快速幂板子，还有备份和对拍。

被 A 硬控写了 2h 其间犯下了注入同一个数 odt 删两遍一类的错。

感觉 B 的 C 性质很香啊，发现合法的充要条件之后考虑容斥，因为不会强连通子图计数拼尽全力只会 O(\text{poly}(n)6^n) 容斥被薄纱。

然后草草写了 B 和 C 的搜索暴力收场，甚至没有写 B 的容斥。

话说 C 的搜索到底是 8 还是 32 来着，不过好像大家都按照 32 算的就 32 吧。

然后最后估分: 272+100+88+8+100+24+32=624。

UPD: d1B 被卡成 44 d2C 获得 8 成功翻进 D /ll

希望不挂分还有拿个 E qwq