NOI 2026 Day 1
2026-08-06 09:02:54
发布于：黑龙江
明天就是 NOI 2026 Day 1，在这里祝我以及参加 NOI 2026 的选手好运，NOI 2026 rp++！
赛后总结帖也许要晚一些发布。
T1 矿车交通
这道题的灵感来源于一道小学数学题：在等车回家的时候，是往车的方向走早点遇到车更快、往家的方向先走一段距离更快，还是原地等待更快？答案是一样快，因为坐的都是同一辆车。
因此可以发现换乘是没有必要的——如果 Steve 最后乘坐的是某辆矿车到达终点，那么他可以选择一直在起点等着这辆矿车并一直坐到终点。因此对于每辆矿车计算乘坐这辆矿车会在什么时候到达终点，并取最小值即可。注意特判只靠步行到达终点和 x=y 的情况。
T2 轮回
考虑第 i 天时 a
0
在原序列中所对应的下标 p
i
，显然当 i 不是 m 的倍数时，p
i
=(p
i−1
+1)modn；否则 p
i
=p
i−1
。将 p 中的元素分为两部分进行计算：
对于 i>0 且 imodm=0 的 p
i
，这些 p
i
的值为 (m−1)−1,2(m−1)−1,… 模 n 意义下的值；
剩下的 p
i
值为 −1,0,1,2,… 模 n 意义下的值。
可以发现，这两部分每一部分每 n 个数都会形成循环，通过计算整个循环带来的贡献，并额外加上剩下的部分即可，时间复杂度 O(n)。
T3 奇迹
考虑将 n 个数排成一个环，此时最近的一对 1 之间的距离不超过 ⌊
x
n
⌋。从小到大枚举两个数的距离 d，将环上所有距离为 d 的 n 对点加入猜测序列中，总猜测次数不超过 ⌊
x
n
2
⌋。
T4 游戏
记 C(x,y)=
k=1
∑
n
[suf
k
(x)=pre
k
(y)]d
k
，其中 suf
k
(x) 为 x 长度为 k 的后缀，pre
k
(y) 为 y 长度为 k 的前缀，[P] 表示当 P 成立时为 1，否则为 0。则子问题一的答案为：
C(s,s)−C(s,t)+C(t,t)−C(t,s)
C(t,t)−C(t,s)
计算 C(x,y) 是简单的：构造字符串 S=y+#+x，S 的每一个 border 都对应一个满足 suf
k
(x)=pre
k
(y) 的 k，使用 KMP 算法计算出 S 的每一个 border 即可。
对于子问题二，一种可能的构造方案是先取 s 为 t 的前 n−1 位，并在 s 的最前方放上任意与 t
2
不同的字符，将 s,t 带入子问题一的公式中很容易证明这是一种合法的构造方案。
下面对子问题一的式子给出证明：先只考虑一个目标串 x，假设有一种下注游戏，在每一轮抛硬币之前，都新来一个下注者，他下注从当前位置开始未来会出现串 x。具体地，他初始时拥有 1 元，下注当前字符为 x
1
，如果猜中，则钱数变成原来的 d 倍，继续下注 x 的下一个字符；否则他的钱数直接变成 0，游戏结束。
不难发现这个游戏是公平的，即每回合结束后每个下注者的期望钱数都仍然是 1，因此若游戏进行了 T 回合，所有下注者拥有的钱数和的期望值也是 T，因此整个游戏所有下注者拥有的钱数和的期望值为 E(T)。
对于原问题，假设每一轮抛硬币之前，都会有两个下注者分别下注 s 和 t。考虑计算游戏以 s 结束时，猜 t 的所有下注者拥有的钱数和：想要结束时有一位连续猜中的 k 次的下注者，这要求 suf
k
(s)=pre
k
(t)，并会带来 d
k
的贡献，这就是式子 C(x,y) 的由来。
设 Steve 获胜的概率为 p，则 Alice 获胜的概率为 1−p，那么对于猜测 s 的所有下注者，其拥有的钱数和的期望值为 pC(s,s)+(1−p)C(t,s)。类似地，对于猜测 t 的所有下注者，其拥有的钱数和的期望值为 pC(t,t)+(1−p)C(s,t)。
按照刚刚的结论，我们发现这两个式子都等于 E(T)，所以 pC(s,s)+(1−p)C(t,s)=pC(t,t)+(1−p)C(s,t)，解方程即可得到上面的结论。
有帮助，赞一个