P7413 题解

Meronri_Deng · 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) 的时间复杂度显然不现实。 可以用前缀和维护。