石子游戏

NC236214. 石子游戏

描述

Alice和Bob在玩取石子游戏。游戏规则如下：有 $n$ 堆石子，每堆石子有 $a_i$ 颗石子。玩家轮流操作，每一次操作可以选择任意一堆非空的石子，从这堆石子中取走任意数量（非0）的石子，当一名玩家不能操作时则视为失败，Alice先手。如果两个人都以最优策略来进行游戏，请问最终谁能获胜。

输入描述

第一行输入一个整数 $n(1\le n \le 5\times 10^5)$ ，表示石子的堆数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1\le a_i \le 10^9)$ ，表示每堆石子的石子个数。

输出描述

输出一行，如果Alice必胜，则输出"Alice"；如果Bob必胜，则输出"Bob"。

示例1

输入:

5
1 2 3 4 5

输出:

Alice

示例2

输入:

3
2 3 1

输出:

Bob

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 207ms, 内存消耗: 412K, 提交时间: 2022-08-25 12:05:08

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+666;
int main()
{
	int n , x , k = 0;
	cin >> n;
	while(n --)
	{
		cin >> x;
		k ^= x;
	}
	if(k == 0)  cout << "Bob" ;
	else  cout << "Alice" ;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 188ms, 内存消耗: 472K, 提交时间: 2023-06-20 11:54:18

#include<bits/stdc++.h>

using namespace std;

int main ()
{
    int n;
    cin>>n;
    int sum=0;
    while(n--)
    {
        int a;
        cin>>a;
        sum^=a;
    }
    puts(sum?"Alice":"Bob");
}