石子 无限拿

给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

思路

若为 2, 3堆, 先手在3堆里拿1个, 为 2 2。
之后只要跟后手拿的数量相同, 后手一定失败。

定理：
$$a_1\wedge a_2\wedge a_3...\wedge a_n=0先手必败$$
证明：
$$\begin{array}{rl}0\wedge 0\wedge 0\wedge \mathrm{0...}\wedge 0=0& \\ a_1\wedge a_2\wedge a_3...\wedge a_n\ne 0& \\ & \end{array}$$
不等于0时, 设结果为 $x$
$x$ 的二进制表示为 $10100100$
$a_i$的二进制表示 $1100100110$
一定存在 $a_i$ 在 $x$ 最高位 $k$ 位上为1。
则 $a_i\wedge x<a_i$ , 那么就拿走 少的那一部分。

此时 $a_i=a_i\wedge x$ 带入到原来式子后得到：
$$x\wedge x=0$$
故先手必赢。

等于0时, 设同样可以拿走一些, 剩下 $a_i^{\prime }$个
$$\begin{array}{r}{a}_1\wedge a_2\wedge a_3...a_i\wedge ..\wedge a_n=0\\ a_1\wedge a_2\wedge a_3...a_i^{\prime }\wedge ..\wedge a_n=0\\ 式子相异或得\\ a_i\wedge a_i^{\prime }=0\\ a_i=a_i^{\prime }\end{array}$$

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int readInt()
{
    int t ;
    scanf("%d", &t);
    return t;
}

int n;
int main()
{
    int x;
    cin >> n;
    cin >> x;
    n -= 1;
    while(n--)
        x ^= readInt();
    if(x) cout << "Yesn";
    else cout << "Non";
    
}

最后

以上就是阔达大门最近收集整理的关于石子 无限拿石子 无限拿的全部内容，更多相关石子内容请搜索靠谱客的其他文章。