取石子游戏 2

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 645 字

N堆石子，两人轮流从某一堆中取任意多颗，取走

一本通
例

正文

/*
原题：T1664「一本通 6.7 例 2」取石子游戏 2
题意：N 堆石子，两人轮流从某一堆中取任意多颗（至少 1 颗），取走最后一颗者胜。
先手胜输出 win，否则输出 lose。
思路：经典的尼姆博弈。把所有堆的石子数做异或，结果为 0 则是必败态（后手胜），
非 0 则是必胜态（先手胜）。因为任何一步都会改变某一堆使异或值变动，
先手总能找到一个取值让异或重新变为 0。
复杂度：时间 O(N)，空间 O(1)
易错点：1) 异或初值必须是 0，且要用 long long 接收可能很大的石子数；
2) 输出字符串是 win/lose，全部小写；
3) 每堆可取任意多颗，而不是指定上限，别套用巴什博弈的结论。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin>>N;
    long long xo=0;
    for(int i=0;i<N;i++){
        long long v;
        cin>>v;
        xo^=v;
    }
    if(xo!=0){
        cout<<"win\n";
    }else{
        cout<<"lose\n";
    }
    return 0;
}

取石子游戏 2

正文

一本通·提高篇的其它内容