Round screws

· · 题解

有性质 (a \oplus t)+(b \oplus t) \ge a \oplus b，因此每次操作必然将一个数改成和它相邻的某个数。令 a_0=a_{n+1}=0，设 f_i 表示前 i 个数的最小总代价，有转移：

f_i=\min_{0 \le j<i}\{f_j+(i-j-1) \cdot C+a_i \oplus a_j\}

令 g_j=f_j-j \cdot C，则：

f_i=\min_{0 \le j<i}\{g_j+a_i \oplus a_j\}+i \cdot C-C

相当于每次插入 (g,a)，然后按 x 查询 g+x \oplus a 的最小值。直接枚举 a，查 g 的最小值是插入 O(1)，查询 O(V) 的。考虑平衡一下两部分的开销，插入的时候枚举查询的 x 的前九个二进制位，先把这九位的贡献算了，查询的时候就只需要算后九个二进制位的贡献，复杂度 O(n \sqrt{V})。