隐藏
「SDOI2009」E&D - 博弈论+SG函数+阿达马矩阵 | Bill Yang's Blog
0%

「SDOI2009」E&D - 博弈论+SG函数+阿达马矩阵

题目大意

    桌子上有$2n$堆石子,第$2i-1$堆与第$2i$堆配对。两个人轮流进行操作,每次一个人可以选择一堆石子移走,然后分割其配对的石子,重新形成两堆,所有堆的石子数必须保证大于$0$。
    若其中一方不能再操作时,即石子数全为$1$,该玩家输掉游戏,询问先手是否有必胜策略。


题目分析

根据SG定理,$2n$堆石子是$n$个子游戏,因此只需要考虑每个子游戏,其SG函数的异或和情况即为胜败态情况。
而SG函数如何计算?
根据其定义,SG函数为后继状态SG函数的mex。
故:

1
2
3
4
5
6
7
8
int SG(int x,int y) {
if(x==1&&y==1)return 0;
if(~f[x][y])return f[x][y];
int vst[1005]= {0};
if(x>1)for(int i=1; i<=(x>>1); i++)vst[SG(i,x-i)]=1;
if(y>1)for(int i=1; i<=(y>>1); i++)vst[SG(i,y-i)]=1;
for(int i=0; ; i++)if(!vst[i])return i;
}

但显然,这样的计算方法会RE,WA,TLE。
因此我们需要寻找更为巧妙的计算方法。

SG函数打个$16\times16$的表:

发现很有规律,是个非常特殊的分形图形,其名字叫做阿达马矩阵。
故可以使用很规律的方法在$\log n$的时间内计算出SG函数。

1
2
3
4
5
6
int SG(int x,int y) {
if((x&1)&&(y&1))return 0;
if(x&1)x++;
if(y&1)y++;
return SG(x>>1,y>>1)+1;
}


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>

using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

int SG(int x,int y) {
if((x&1)&&(y&1))return 0;
if(x&1)x++;
if(y&1)y++;
return SG(x>>1,y>>1)+1;
}

int main() {
int t=Get_Int();
while(t--) {
int n=Get_Int()>>1,ans=0;
for(int i=1; i<=n; i++) {
int x=Get_Int(),y=Get_Int();
ans^=SG(x,y);
}
puts(ans?"YES":"NO");
}
return 0;
}
姥爷们赏瓶冰阔落吧~