联合省选 2026 游记

lbdontknow · 2026-03-09 13:26:18 · 生活·游记

Day -1

12:00 逃离学校。
15:00 试机，虚拟机里 10^8 次乘法取模跑了 0.3 秒。
16:00 订场羽，工作日一个小时居然只要 35r
晚上进行激烈的 All the mods 10 训练

Day 0

t1 想了想发现可以对每个点算出重链长度分别的概率，然后再一个剔除背包就做完了。
不会多项式除法，只能拆成前后缀多项式乘法做，NTT 多只 log 不敢写，于是直接 O(n^3) 暴力多项式乘法，但是大样例全过了，还跑得飞快，希望不会被菊花图卡。
t2 只会暴力和 s_i = 0，获取 30 分。
t3 没啥时间了，写了 n2^n 次双端队列大粪实现，希望我的 8 分不会被卡。
下午继续羽，晚上继续 ATM。

Day 1

t1 是神秘交互，想了想容易发现 2n+\log_2n 次是好做的，然后考虑怎么把 2n 压掉，发现只要询问前后缀就可以同时判断下一个数在左边还是右边，就有 n + \log_2n 次了，然后发现二分 0 的位置的过程其实可以省掉，直接通过问前后缀的方式可以让后面完全复用，这样次数就是严格 n 次的了。
t2 神秘翻转，想了半天想不到转化，拿不到分，弃了。 t3 神了，对着一群 gunmu 比较字典序，题就读了半个小时，暴力感觉不是很好写，发现前两个点是好写的，菊花图分类讨论就行了，r=1 直接树上两点距离就行了，但是没时间了，分类讨论没过大样例。
总分：[64,100] + 30 + 8 + 100 + 0 + 4 = [206, 242]
拉完了。