题面
首先很明显博弈论
打表SG函数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
using namespace std;
int SG[1010][1010], n;
inline int mex(vector <int> v) {
sort(v.begin(), v.end());
int cnt = unique(v.begin(), v.end()) - v.begin();
for(int i = 0; i < cnt; i++) if(v[i] != i) return i;
return cnt;
}
int main() {
scanf("%d", &n);
SG[1][1] = 0;
for(int sum = 3; sum <= n * 2; sum++) {
for(int i = max(1, sum - n); i <= sum && i <= n; i++) {
int j = sum - i;
vector <int> v;
for(int k = 1; k < i; k++) v.push_back(SG[k][i - k]);
for(int k = 1; k < j; k++) v.push_back(SG[k][j - k]);
SG[i][j] = mex(v);
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) printf("%d%c", SG[i][j], " \n"[j == n]);
return 0;
}
1 | 0 1 0 2 0 1 0 3 0 1 |
???什么玩意儿???
然后把每行最小值提出来1
0 1 0 2 0 1 0 3 0 1
发现都在第一位出现
而且貌似和二进制有关
再感受一下，就是最低的0的位置
于是再看一下，就能看出$SG_{i,j}=f((i-1)bitor(j-1))$,$f(x)$为x最低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
using namespace std;
inline int work(unsigned int x) {
x = ~x;
x = x & (-x);
int ans = 0;
while(x >>= 1) ans++;
return ans;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n, ans = 0;
scanf("%d", &n);
for(int i = 0; i < n; i += 2) {
int a, b;
scanf("%d%d", &a, &b);
ans ^= work((a - 1) | (b - 1));
}
if(ans) puts("YES");
else puts("NO");
}
}