51NOD 1069 Nim游戏

时间：2023-02-09 16:01:41
有N堆石子。A B两个人轮流拿，A先拿。每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N及每堆石子的数量，问最后谁能赢得比赛。
例如：3堆石子，每堆1颗。A拿1颗，B拿1颗，此时还剩1堆，所以A可以拿到最后1颗石子。
 
Input
第1行：一个数N，表示有N堆石子。（1 <= N <= 1000)

第2 - N + 1行：N堆石子的数量。(1 <= A[i] <= 10^9)
Output
如果A获胜输出A，如果B获胜输出B。
Input示例
3

1

1

1
Output示例
A

详细见 https://baike.baidu.com/item/Nim%E6%B8%B8%E6%88%8F/6737105?fr=aladdin

如果轮到你的时候，只剩下一堆石子，那么此时的必胜策略肯定是把这堆石子全部拿完一颗也不给对手剩，然后对手就输了。
如果剩下两堆不相等的石子，必胜策略是通过取多的一堆的石子将两堆石子变得相等，以后如果对手在某一堆里拿若干颗，你就可以在另一堆中拿同样多的颗数，直至胜利。
如果你面对的是两堆相等的石子，那么此时你是没有任何必胜策略的，反而对手可以遵循上面的策略保证必胜。

#include <bits/stdc++.h>

using namespace std;

int main ()

{

    int n,ans =;

    scanf("%d", &n);

    for(int i=; i<=n ;i++)

    {

        int x;

        scanf("%d",&x);

        ans ^= x;

    }

    if( ans )

        puts("A");

    else

        puts("B");

    return ;

}

Nim

相关文章