[普及-]94100题解

题意过于简单，这里不在累赘。

思路

一个很经典的博弈论问题。

我们先考虑什么情况下先手必赢，首先最容易想到的就是 $1,2$ 颗石子的情况，因为只需一步即可拿完。那么，先手必输的情况呢？$3$ 颗石子的时候，先手无论怎么拿，最后一定会剩下 $1,2$ 颗石子到后手时，一步即可拿完。
因为先手和后手是轮流交换的，所以只要先手操作后的石子数是先手必输局面，那么先手必赢（因为后手遇到了必输局面）。
同样的，如果先手无论如何操作都无法到达必输局面。那么先手是必输的（因为后手一定遇到了必赢局面）。依此类推。（可能有点难理解，可以自己尝试一下）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e8;
bool a[N];
signed main(){
	a[0] = 1;
	a[1] = 1;
	a[2] = 1;//1表示先手赢，0表示先手输 
	int n;
	cin >> n;
	for(int i = 3;i <= n;i ++){
		if(a[i - 2] == 0 || a[i - 1] == 0){
			a[i] = 1;
		}else a[i]= 0;
	}
    if(a[n]) cout << "win";
    else cout << "lose";
	return 0;
}
//

由于 $n$ 颗石子下的结果是恒定的，于是我们可以输出从 $1$ 到 $n$ 颗石子的情况。
1 1 0 1 1 0 1 1 0 1 1 0...可以发现，无论 $n$ 为多少，只要 $3 \mid n$ 那么一定是比输局面，否则一定是必赢······