2 条题解
-
-2wanglongbang (njnu19180103) LV 10 @ 2021-01-26 13:40:12
Nim 游戏
n堆物品,每堆有ai个,两个玩家轮流取走任意一堆的任意个
物品,但不能不取。取走最后一个物品的人获胜。 -
-22019-06-01 11:37:13@
对于n为奇数的情况,去掉所有对子之后,剩下的石子堆数肯定是奇数,且互不相等。这时只要令a[1]=0即可,于是先手必胜(即不论当前是否为奇异局势,先手都能一步将其变成奇异局势,同时让后手无法在一步之内保持局势奇异性不变)。
而对于n为偶数的情况,如果去掉所有对子之后,如果剩下互不相等的偶数堆石子,先手依然能必胜,然而如果去掉所有对子之后,没有任何一堆棋子剩余(即当前局势为奇异局势),那么先手的任何操作都会让这个奇异局势变成非奇异局势,于是只有后手才能必胜。#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<set> #include<map> #include<queue> #include<stack> #include<vector> #include<cstring> #include<cstdlib> using namespace std; typedef long long ll; const int maxn=5000+5; const ll INF=0x3f3f3f3f3f3f3f3fll; int t,n; int main() { ios::sync_with_stdio(false); //freopen("校庆的娱乐.in","r",stdin); cin>>t; while(t--){ cin>>n; int temp,x; cin>>temp; for(int i=2;i<=n;i++){ cin>>x; temp^=x; } if(temp||n&1) cout<<"lolanv"<<endl; else cout<<"Wind"<<endl; //只有全是对子 才会让wind赢 } return 0; }
- 1