2022-2023:teams:eager_to_embrace_the_seniors_thigh:7k
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2022-2023:teams:eager_to_embrace_the_seniors_thigh:7k [2022/08/09 18:27] 11231123 [题解] |
2022-2023:teams:eager_to_embrace_the_seniors_thigh:7k [2022/08/09 18:29] (当前版本) 11231123 [题解] |
||
|---|---|---|---|
| 行 19: | 行 19: | ||
| 对于大于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$ 。所以对于奇数堆我们有将其变为偶数堆先手必败的情况。 | 对于大于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.1660040879.txt.gz · 最后更改: 2022/08/09 18:27 由 11231123
