学步园

题目：题目链接

题目意思：题目是说两个人给n条线染色，每次可以染的长度是2.A先手，问A是赢还是输？假设双方都采取最好的策略

分析：思路：裸求SG函数，和把一排石子分成若干堆相似，每次把长度为x的线段分成长度为i和x-i-2的线段，然后异或后求出mex值（mex值指不属于这个集合的非负整数），最后把所有子游戏的SG值异或求和

代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
using namespace std;
int n;
int sg[55];
int SG(int m)
{
    if(m < 2)
        return sg[m] = 0;
    if(sg[m] != -1)
        return sg[m];
    bool next[55];
    memset(next, 0, sizeof(next));
    for(int i = m-2; i >= 0; --i)
    {
        int tp = SG(i)^SG(m-i-2);
        next[tp] = 1;
    }
    for(int i = 0;; ++i)
    {
        if(next[i]==0)
            return sg[m] =  i;
    }
}
int main()
{
    memset(sg, -1, sizeof(sg));
    while(scanf("%d", &n)==1)
    {
        int sum = 0;
        int a;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d",&a);
            sum ^= SG(a);
        }
        if(sum)
            puts("Yes");
        else puts("No");
    }
    return 0;
}

努力努力...