Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：有一串石子，给定一个集合S，每次只能拿连续x个石子，石子必须是在集合S中的数，问先手是否有必赢策略。需要注意石子的位置是不能变化的，也就是说如果一串连续的石子因为中间有石子被取走，那么这段石子就变成不连续的了，也就不能一次取走。
思路：一开始没有读懂题。需要特别强调的是。石子的位置是不能合并的。。
举个例子，如果我有5个石子，S={2},那么我取完一次剩下的情况是 {3,4,5}或者{1},{4,5}或者{1,2},{5}或者{1,2,3} 一共四种。
题意搞清楚以后就好做了。。类似于bomb game那道题。。我们仍然可以把取一次的操作拆分两个子过程，也就是两个区间。我们不关心区间具体的情况，只关心区间的长度。以及，取完只有一个区间的情况不需要特殊考虑，认为是长度为0就可以了，因为sg[0]为0，不影响答案。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月23日 星期六 15时02分17秒
4File Name :code/hdu/2999.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=2005;
34int sg[N];
35bool vis[N];
36set<int>ok;
37set<int>::iterator it ;
38int n;
39int q;
40
41
42void sg_init()
43{
44 ms(sg,0);
45
46 for ( int i = 1 ; i < N ; i++)
47 {
48 ms(vis,false);
49
50 for ( it = ok.begin() ; it!=ok.end() ; it++)
51 {
52 int tmp=*it;
53 tmp = i-tmp;
54 for ( int j = 0 ; tmp-j>= j ; j++)
55 vis[sg[j]^sg[tmp-j]] = true;
56 }
57
58 for ( int k = 0 ; ; k++)
59 if (!vis[k])
60 {
61 sg[i] = k;
62 break;
63 }
64 }
65}
66int main()
67{
68 #ifndef ONLINE_JUDGE
69 freopen("code/in.txt","r",stdin);
70 #endif
71
72 while (~scanf("%d",&n))
73 {
74 ok.clear();
75// int mn = inf;
76 for ( int i = 1 ; i <= n; i++)
77 {
78 int x;
79 scanf("%d",&x);
80 ok.insert(x);
81 // mn = min(x,mn);
82
83 }
84 sg_init();
85// for ( int i = 1; i <= 30 ; i++) cout<<"i:"<<i<<" sg[i]:"<<sg[i]<<endl;
86 scanf("%d",&q);
87 while (q--)
88 {
89 int x;
90 scanf("%d",&x);
91 if (sg[x])
92 {
93 puts("1");
94 }else
95 {
96 puts("2");
97 }
98 }
99 }
100
101
102
103 #ifndef ONLINE_JUDGE
104 fclose(stdin);
105 #endif
106 return 0;
107}