有n堆苹果， 对于其中的每一堆的x个苹果， 它是放在一条线上的。 你每次可以对一堆苹果进行操作， 可以取y个， 1<=y<=x。 然后如果你是取的一条线上中间的苹果， 那么这一堆苹果将会变成两堆。 问你先手是否必胜。
简单的打一个sg表就可以了。 注意特判全都是1的情况。
#include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> #include <complex> #include <cmath> #include <map> #include <set> #include <string> #include <queue> #include <stack> #include <bitset> using namespace std; #define pb(x) push_back(x) #define ll long long #define mk(x, y) make_pair(x, y) #define lson l, m, rt<<1 #define mem(a) memset(a, 0, sizeof(a)) #define rson m+1, r, rt<<1|1 #define mem1(a) memset(a, -1, sizeof(a)) #define mem2(a) memset(a, 0x3f, sizeof(a)) #define rep(i, n, a) for(int i = a; i<n; i++) #define fi first #define se second typedef complex <double> cmx; typedef pair<int, int> pll; const double PI = acos(-1.0); const double eps = 1e-8; const int mod = 1e9+7; const int inf = 1061109567; const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; int sg[200]; int mex(int x) { if(~sg[x]) return sg[x]; bool vis[500]; memset(vis, false, sizeof(vis)); for(int i = 1; i <= x; i++) { for(int j = 0; j <= x-i; j++) { vis[mex(j)^mex(x-i-j)] = 1; } } for(int i = 0; ; i++) if(!vis[i]) return sg[x] = i; } int main() { int n, x; mem1(sg); for(int i = 1; i <= 100; i++) { mex(i); } while(cin>>n) { int ans = 0, flag = 0; for(int i = 0; i < n; i++) { scanf("%d", &x); if(x > 1) flag = 1; ans ^= sg[x]; } if(!ans) { if(flag) puts("No"); else puts("Yes"); } else { if(flag) puts("Yes"); else puts("No"); } } return 0; }