题解：AT_jsc2022_final_e Circular Sushi

2huk · 2026-03-05 09:03:51 · 题解

可以证明答案 t = p/2^l，其中 p 是整数。

那么一个车能贡献当且仅当 a_i+ \dfrac{pv_i}{2^l} \equiv 0 \pmod {2^l}，即 \dfrac{2^la_i + pv_i}{2^l} \equiv 0 \pmod {2^l}，2^l a_i+pv_i \equiv 0 \pmod {2^{2l}}。这样就都是整数了。

然后如果重新设 a'_i=2^l a_i \bmod 2^{2l},t'=p,l'=2l 的话，就变成了有一个长度为 2^{l'} 的环，每个车初始在 a'_i，速度为 v_i，求一个整数 t' 使得此时在原点的车的价值和最大。这就又变成了最初的问题，只不过保证了答案为整数。

于是我们对于每个车，求出它第一次到原点的整数时刻 d_i，以及第二次到原点相较于第一次到原点的时间差 e_i。