hdu 2999 Stone Game, Why are you always there? (sg函数，线性串取石子)
题意：有一串石子，给定一个集合S，每次只能拿连续x个石子，石子必须是在集合S中的数，问先手是否有必赢策略。需要注意石子的位置是不能变化的，也就是说如果一串连续的石子因为中间有石子被取走，那么这段石子就变成不连续的了，也就不能一次取走。
思路：一开始没有读懂题。需要特别强调的是。石子的位置是不能合并的。。
举个例子，如果我有5个石子，S={2},那么我取完一次剩下的情况是 {3,4,5}或者{1},{4,5}或者{1,2},{5}或者{1,2,3} 一共四种。
题意搞清楚以后就好做了。。类似于bomb game那道题。。我们仍然可以把取一次的操作拆分两个子过程，也就是两个区间。我们不关心区间具体的情况，只关心区间的长度。以及，取完只有一个区间的情况不需要特殊考虑，认为是长度为0就可以了，因为sg[0]为0，不影响答案。
/* ***********************************************
Author :111qqz
Created Time :2016年07月23日 星期六 15时02分17秒
File Name :code/hdu/2999.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=2005;
7int sg[N];
8bool vis[N];
9set<int>ok;
10set<int>::iterator it ;
11int n;
12int q;
1void sg_init()
2{
3 ms(sg,0);
1 for ( int i = 1 ; i < N ; i++)
2 {
3 ms(vis,false);
1 for ( it = ok.begin() ; it!=ok.end() ; it++)
2 {
3 int tmp=*it;
4 tmp = i-tmp;
5 for ( int j = 0 ; tmp-j>= j ; j++)
6 vis[sg[j]^sg[tmp-j]] = true;
7 }
1 for ( int k = 0 ; ; k++)
2 if (!vis[k])
3 {
4 sg[i] = k;
5 break;
6 }
7 }
8}
9int main()
10{
11 #ifndef ONLINE_JUDGE
12 freopen("code/in.txt","r",stdin);
13 #endif
1 while (~scanf("%d",&n))
2 {
3 ok.clear();
4// int mn = inf;
5 for ( int i = 1 ; i <= n; i++)
6 {
7 int x;
8 scanf("%d",&x);
9 ok.insert(x);
10 // mn = min(x,mn);
1 }
2 sg_init();
3// for ( int i = 1; i <= 30 ; i++) cout<<"i:"<<i<<" sg[i]:"<<sg[i]<<endl;
4 scanf("%d",&q);
5 while (q--)
6 {
7 int x;
8 scanf("%d",&x);
9 if (sg[x])
10 {
11 puts("1");
12 }else
13 {
14 puts("2");
15 }
16 }
17 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}