SDOI2025游记

· · 生活·游记

day 0

晚上试机去旁边蜜雪冰城买奶茶，面基 MrPython。

常规测电脑速度。本人考试电脑输入输出的数据如下：

输入 10000000 个 "1000000000"
scanf 用时 5.54s, read() 用时 2.32s，关流 cin 用时 1.57s
输出 10000000 个 "1000000000"
printf 用时 14s, write() 用时 4.13s，关流 cout 用时 2.54s

我也不知道咋记住的，但是 14 秒有点好笑。

键盘的“→”没法用，换了个键盘特别好使。

day1

我咋这么困。

发密码之前先浏览了一遍压缩包，发现 recall 的输入输出量极其巨大，怀疑是数据结构，而 lucky 的输出量很小。

解包，密码中可辨认的字符为 keep dreaming，防伪字符忘了。

通读一遍之后先开 lucky，观察样例解释猜出可行的答案一定位于一段区间内。写个二分求出上下界做完了。诶咋大样例有两个不对。想了一下发现要和原有值域有交，写个离散化改了改过了大样例，遂弃之。此时 9 点。

接下来四个小时和摆烂了一样。recall 把暴力打完后去写 AB 性质，用个 bitset 维护每个点可达的点之后暴力求答案是不是就能做到 O(\frac{nm}w) 来着？遂写之，未能成。

然后视线落到了 AC 性质上，这个部分在刚才 bitset 跑连通性后可以定期重构啊！每 \sqrt q 次进行一次重构，先对于每个点 u 记 val_u 为 u 能到达的点中在之前的 \sqrt q 次操作中没有变化的点中 b 的最大值，然后对每个询问暴力处理操作过的点即可，复杂度 O(\frac{nm}w+(n+q)\sqrt q)，大样例飞快。

然后看到没有 C 的 A 性质，能不能用 bitset 优化区间查询来着？和上面不一样吗。遂弃之。

graperm 没有任何下手点，遂 8 分弃之。

day1 期望得分：100+32+8-\varepsilon_1。

day2

解包，密码中可辨认的字符为 remain loving，防伪字符忘了。

先开了 move。一个显然的贪心策略是按 t 从小到大枚举并将对应的箱子推到对应的位置，并将路上遇到的每个箱子向前推。这样时间复杂度是 O(n^2) 的，考虑用数据结构优化上述过程。用一棵线段树维护每个箱子当前坐标，那么上述过程实际上是找到被推动的箱子之后计算贡献，并将其区间修改为一段公差为 1 的等差数列，而找到被推动的箱子这个问题可以线段树上二分在 O(\log n) 的时间复杂度内得到答案，做完了。

赛后 LA 群被 ODT 占领了，表示不可理解。

\ 赛后被 LA 众神围殴.jpg

调出来的时候正好十点，不放心写了个拍子拍了 5k 组，应该是过了。

接下来三个小时和 day1 处境类似。years 写了爆搜和 B 性质后润了，seal 没有任何下手点，爆搜也不会写，遂爆零。

day2 期望：100+24+0-\varepsilon_2。

day6

出分，\varepsilon_1=\varepsilon_2=0，没挂就是赢。

看来在 SD 排了约 rk30，倒闭。

最后

不比去年两天加起来没到100分好多了可以看到在难题上的差距。还是因为自己太菜。能不能拿个 D 听天由命 /ll /ll /ll

望んだ答がここじゃないのなら

踏み出す理由はそれだけでいい

抗う鼓動が今呼吸への証だ

呼ばい出すと、嘘の様に、愛の歌を