2022-2023:teams:eager_to_embrace_the_seniors_thigh:7k

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2022-2023:teams:eager_to_embrace_the_seniors_thigh:7k [2022/08/09 18:15]
11231123 [题意]
+++ 2022-2023:teams:eager_to_embrace_the_seniors_thigh:7k [2022/08/09 18:29] (当前版本)
11231123 [题解]
@@ 行 6: / 行 6: @@
 $n,q\le 10^5, a_i\le 10^6$
+==== 题解 ====
+结论：奇数堆时先手必胜，偶数堆时 $\oplus{(a_i-1)} \neq 0$ 时先手必胜。
+证明：考虑数学归纳法。
+堆时显然先手必胜；2堆时双方都不可能进行合并操作，此时被迫拿完一堆的就输了，所以考虑将两堆数量都减1后当作nim游戏。
+对于大于2的偶数，我们仍然按照上面的逻辑，每堆数量都减1后当作nim游戏。
+对于大于2的奇数，我们考虑如何操作能将局面变为先手必败。我们考虑操作数量最多的堆，设该堆有 $x$ 个。设第2大的堆有 $y$ 个，第3大的堆有 $z$ 个。显然除了最大的两堆之外的堆减1后的异或和 $S$ 有 $S\le 2*(z-1)$ ，我们只需要将 $y$ 补至 $S+1$ 即可。注意到 $x+y\ge 2*z\ge S+2$ ，所以在将最大的堆拿走至少1个后仍然可以将次大的堆补至 $S+1$ 。所以对于奇数堆我们有将其变为偶数堆先手必败的情况。
+有了上述结论之后，我们每个询问就变成了求区间内长度为奇数的子段数加减1后异或和不为0的长度为偶数的子段数，这个问题显然可以变为总子段数减去异或和为0的长度为偶数的子段数，然后用莫队求解。

2022-2023/teams/eager_to_embrace_the_seniors_thigh/7k.1660040110.txt.gz · 最后更改: 2022/08/09 18:15 由 11231123