ZOJ 2083 Win the Game（SG函数）题解

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：给一端n块的板，两人玩，每次能涂相邻两块没涂过的板，不能涂的人为输，先手赢输出yes

思路：sg函数打表，练习题

代码：

#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define eps 1e-9
typedef long long ll;
const int maxn = + ;
const int seed = ;
const ll MOD = 1e9 + ;
const int INF = 0x3f3f3f3f;
using namespace std;
int sg[], s[];
int main(){
sg[] = , sg[] = , sg[] = ;
for(int i = ; i <= ; i++){
memset(s, , sizeof(s));
for(int j = ; j <= i - ; j++){
int l = j - ;
int r = i - (j + );
s[sg[l] ^ sg[r]] = ;
}
for(int j = ; j < ; j++){
if(!s[j]){
sg[i] = j;
break;
}
}
}
int n;
while(~scanf("%d", &n)){
int ans = ;
int u;
while(n--){
scanf("%d", &u);
ans ^= sg[u];
}
if(ans == ) printf("No\n");
else printf("Yes\n");
}
return ;
}