There are stones!
在 IOICamp2017 解過的題目
堆石頭，每 個排成一列，編號從 1~ ，兩人輪流拿，每次可以從某一堆拿取一顆石頭，或是任意相鄰的兩個石頭，最後不能拿的人輸。給定盤面，假設兩人都以最佳策略玩遊戲，判定先手或後手贏。
第一行一個正整數 ，代表測資筆數。每筆測資兩行， 第一行一個整數 ，第二行 個正整數 ，代表有幾顆石頭排成一列。
輸出一行。若先手贏，輸出 F ，若後手贏，輸出 S 。
總之先算 SG 值吧，算出 SG 值後列個一千筆看看，一定能找到規律的。 SG 值都求出來後，直接將每堆 xor 起來，若不等於 0 則先手贏，反之則後手贏。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ULL;
const int MAXN=500;
int sg[MAXN]={0,1,2,3,1};
set<int> s, l, t;
ULL input[10010];
void build(){
l.insert(3);l.insert(2);
for(int i=5; i<MAXN; ++i) {
s.clear();
for(int j=i-1, k=0; k<=j; --j, ++k) {
s.insert(sg[j]^sg[k]);
}
t=s;
s.insert(l.begin(), l.end());
l=t;
int maxval = *s.rbegin();
int j;
for(j=0; j<=maxval && s.count(j); ++j);
sg[i]=j;
}
}
int getsg(ULL n) {
if(n>=200uLL) return sg[200uLL+(n-200uLL)%12uLL];
return sg[n];//n<200
}
int main(void) {
ios::sync_with_stdio(false);cin.tie(0);
int T, n;
build();
cin >> T;
while(T--) {
cin >> n;
ULL ans=0uLL;
for(int i=0; i<n; ++i) {
ULL temp;
cin >> temp;
ans^=getsg(temp);
}
cout<<(ans?'F':'S')<<'\n';
}
return 0;
}