张老师的游戏

NC25256. 张老师的游戏

描述

在空闲时间，张老师习惯性地和菜哭武玩起了取石子游戏，这次的游戏规则有些不同，在他们面前有n堆石子，其中，第i堆石子的个数为a[i]，现在制定规则如下：
从张老师开始，两个人轮流取石子，每次可以从任意一堆中取走x个石子，其中x必须严格小于这堆石子的总数并且能够被这堆石子的个数整除，谁先无法继续取走石子就算失败！
例如，只有一堆石子，个数为6，张老师首先可以取走的石子个数为1，2或者3个。
现在给定n堆石子每一堆的石子数，张老师希望你帮他确定在双方最优策略下他能否赢得游戏。

输入描述

    第一行一个整数n(1<=n<=100,000)
    第二行n个整数，分别代表每一堆石头的个数，保证所有数据为小于等于10⁹的正整数

输出描述

输出一行，Win或者Lose，表示张老师能否获得胜利

示例1

输入:

3
2 2 1

输出:

Lose

示例2

输入:

2
2 9

输出:

Win

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

C++14(g++5.4) 解法, 执行用时: 35ms, 内存消耗: 1424K, 提交时间: 2019-04-23 18:46:20

#include <bits/stdc++.h>
using namespace std;
int n,i,x,ans;
int main(){
    scanf("%d",&n);
    for (i=1;i<=n;++i){
        scanf("%d",&x);
        ans^=__builtin_ctz(x);
    }
    puts(ans?"Win":"Lose");
    return 0;
}

C++(clang++11) 解法, 执行用时: 44ms, 内存消耗: 388K, 提交时间: 2020-11-20 15:52:21

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a;
	int ans=0;
	for(int i=0;i<n;i++){
		cin>>a;
		ans^=__builtin_ctz(a); 
	}
	cout<<(ans?"Win":"Lose");
	return 0;
}

Python3 解法, 执行用时: 164ms, 内存消耗: 12712K, 提交时间: 2023-06-11 19:53:27

ans = 0
input()
for x in map(int, input().split()):
    ans ^= len(bin(x & (-x))) - 3
print("Win" if ans else "Lose")