联合省选 2026 游记

· · 生活·游记

省流：noip 坠机了，所以仅进行走过场操作。

Day 1：

本土作战，提前 10 min 到，发现大家都到了。

$9:10$ 尝试一个一个子树加进去做，发现无法得到总和。 $9:30$ 想到背包，验证了下样例，感觉没有问题，并且树上背包是 $n^2$ 的，果断开写。 $10:00$ 发现无法去掉其中一个数的贡献，大惊，不会回退背包（我太菜了），无奈写 $n^3$。 $10:30$ 写完发现大样例莫名 TLE+RE，发现数组开爆了，并且清空太慢，改成 vector 并每次使用前 resize。结果我以为 resize 的第二个参数是初值，调了将近半个小时，大怒。 继续测 T1 大样例，发现第六个跑了将近 1s，第七个跑了将近 10s，知道自己是 $n^3$ 并没有纠结，觉得最多 $64$ pts 了。 $11:10$ 终于开始看 T2 & T3，发现 T3 更可做，先打了前三个点，看 $m=2$，结合性质 A，也找不到规律。看性质 B，找到规律并过了大样例。 $12:00$ 写 T2。15 分暴力很轻松，不过听说有人写成了 $4^n$ 就很难绷。看 B 性质，发现前面全是 0 后面写个背包。 $13:00$ 回头试图优化 T1，删掉 $n^3$ 的部分发现跑的很快，发现是类似多项式乘法的东西不会优化了。也没有细究。T2 T3 也没有再细看。 出来后都说 T1 写的 $n^3$，但为啥别人大样例都跑的挺快的？发现自己没有预处理逆元，大惊。原来 $n^3 \rightarrow n^3\log n$，别人基本都过了 qoj 上的水数据，只有我稳稳的 64。 测 T2 $30 \rightarrow 20$，发现 $n=1$ 没有考虑，寄希望与官方数据了。 测 T3 $32 \rightarrow 12$，B 性质挂没了，问号，被水大样例击败了qwq。到底谁家好人大样例 $50$ 个点就三个是 yes 啊。。 ## Day 2： 依旧稳定提前 10 min 到，依旧发现大家都到了。 $8:30$ 开题。等等。“**这是一道交互题。**”头一回出交互了，挺开心的。 $8:35$ 看到同机房的开始敲代码（伏笔），大慌，此时还仅有 $n\log n$ 可能稍微优化的思路。 $9:00$ 看到机房那位上了厕所回来笑嘻了（依旧伏笔），更慌，此时大致有 $kn+\log n，k\in [1,2]$ 的解法，不再纠结，先写再说。 $10:00$ 实测跑出来大致在 $2n$ 以内，加了点小优化大概到了 $1.5n$ 左右，对于 $p_0=0$ 居然刚好 $n$ 次。果断决定先开 T2 T3。 $11:00$ T2 毫无思路，转战 T3。先明确战略，只做 $O_x=0,O_y=0$。前两个点很显然，并且和后面的点不一样，果断开写。 $11:25$ 写完第一个点的分讨。 $11:50$ 写完第二个点的路径查询。 $12:10$ 发现并不会 $O_x=0,O_y=0$，甚至只能得到 $n\le 10$ 的分。难绷，回头做 T2。 $12:25$ 研究出 T2 $k=3$ 的答案。但不太会构造，尝试继续推理其他 $k$ 值的答案，失败。 $12:45$ 无奈写 T3 的 $n\le 10$。回头优化 T1。 $13:00$ 特判了 T1 的 B 性质，并写了类似倍增的东西。基本最差能跑到 $1.3n$ 的样子，稍微随机一点点的数据就能跑到 $\lt n$。 $13:10$ 突然会了 T2 $k=3$ 的构造，开始写。 $13:20$ 写完了，正好听说要延时 $15$ min，大怒（因为饿了）。不过此时发现写挂了，赶紧调。 $13:29$ 这个点调对了，要是没有延时大概率不敢放松的调到这个时候。莫名感激，因为我 T3 只管了特殊性质，甚至没有看一眼样例 2。 出来，同机房的那位说：T1 你秒不掉啊，那你原地退役吧。 我问他：你怎么把找 0 的那个 log 搞掉的？ 他：为什么会有 log 啊，$2n$ 次为啥要找 0 啊。 我：？？？$2n$ 次不是 50 分吗？ 他：？！什么？！ 于是他愉快的以为 $60000$ 次就是满分，并在 $1h$ 内就“切掉”了。最后在 qoj 上愉快的获得了 $60$ pts。 ## 后记： 希望 D1T1 数据强一点，~~我反正过不掉了~~。 希望 D2T1 数据弱一点，多过一点。（是不是太邪恶了qwq）