自动搬运

查看原文

来自洛谷，原作者为

	Meronri_Deng 假使lo-lo-lo-lo-lo-ser有具体模样的话，兴许是我的模样。

搬运于2025-08-24 22:29:38，当前版本为作者最后更新于2021-04-07 13:11:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

由题意， $s_{i+1}$ 是$s_i$的倍数。
枚举 $s_1$，假设每次都取走 $s_1$ 个石子，则第 $i$ 堆需要取 $\lfloor \frac{a_i}{s_1}\rfloor$ 次。
设数组 $A=\lbrace2,4,6,8,10\rbrace$,$s_1=3$, 则所需操作次数集合$S=\lbrace0,1,2,2,3\rbrace$。 Bessie的第一回合操作，意味着在集合$B$中选择一个元素 $x$，使 $x$ 变为$x-1$。
第$i$回合的操作，设 $s_i=k\ast s_1$ ，意味着在集合$B$中选择一个元素 $x$ ，使 $x$ 变为 $x-k$ ，同时忽略小于 $k$ 的元素 $x$ 。
若第$i$回合后，$\forall x \in S,x<k$，即下一回合的牛无法取石子，则当前取石子的牛获胜。

Q:在什么条件下必胜？
若操作完之后，任意元素 $x$ 均出现偶数次，则之后重复另一位玩家的操作即可。

Q:要在第一回合使任意元素 $x$ 均出现偶数次，有什么条件？要如何操作？

• 若操作前任意元素 $x$ 均出现偶数次，则该次操作必然会导致存在某个元素$x$出现奇数次，此时 Bessie 先手必败。

• 若操作前有 $1$ 个元素 $x_1$ 出现奇数次，

  • 如果 $x_1>1$ ，
    • 对 $x_1$ 进行操作会导致 $x_1-1$ 出现奇数次,此时 Bessie 先手必败；
    • 对 $x_1$ 以外的元素 $x$ 操作，导致 $x$ 出现奇数次,此时 Bessie 先手必败；
  • 如果 $x_1=1$ ，对 $x_1$ 操作，满足条件,此时 Bessie 先手必胜。

• 若操作前有 $2$ 个元素 $x_1,x_2$ 出现奇数次，设 $x_1<x_2$ ，

  • 如果 $x_1=x_2-1$ ,则对 $x_2$ 操作后, $x_1,x_2$均出现偶数次，此时 Bessie 先手必胜。
  • 如果 $x_1<x_2-1$ ,则对 $x_2/x_1$ 操作后, $x_1/x_2$出现奇数次，此时 Bessie 先手必败。

• 若操作前有 $M(M>2)$ 个元素出现奇数次，则无论怎么操作，都无法使所有元素均出现偶数次，此时 Bessie 先手必败。

Q:请问 Elsie 的后手必胜策略是怎样的？
找到集合 $S$ 中最大的出现奇数次的元素 $x$ ，并把它变成 $0$ ，之后任意元素均出现偶数次。

Q:如何算出集合$S$中每个元素的出现次数？$O(\max(a_i)^2)$ 的时间复杂度显然不现实。 可以用前缀和维护。
$sum_i$ 表示数组 $A$ 中有多少元素 $A_j$ 满足$1 \leq A_j\leq i$。
想要求出 $s_1$ 对应的集合 $S$ 中 $x$ 元素出现的次数$t$， 借助前缀和即可。
需取 $x$ 次的石子堆中，至少包含 $x \ast s_1$ 个石子,至多包含 $(x+1) \ast s_1-1$个石子。
$t=sum_{(x+1) \ast s_1-1}-sum_{x \ast s_1-1}$。

感谢阅读！