【SG+打表】E&D

博弈

传送门：BZOJ1228

思路：

  • 考虑直接求出$SG(i,j)$，空间似乎已经是$O(S_{max}^2)$，时间就不用说了；
  • 然后就打表找规律

打表代码如下：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
LL n,t,x,y,ans,sg[100][100],mex[1000];
void getsg(){
	LL index=0;
	for (LL l=2;l<=60;l++){
		for (LL i=1;i<l;i++){
			LL j=l-i; ++index;
			for (LL k=1;k<i;k++) mex[sg[k][i-k]]=index;
			for (LL k=1;k<j;k++) mex[sg[k][j-k]]=index;
			for (LL k=0;mex[k]==index;k++) sg[i][j]=k+1;
		}
	}
	for (LL i=1;i<=30;i++){
		for (LL j=1;j<=30;j++) printf("%d ",sg[i][j]);
		puts("");
	}
}
int main(){
	getsg();
	return 0;
}

AC代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
LL n,t,x,y,ans;
LL getint(){
	char ch; LL sum=0;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
	return sum;
}
LL sg(LL x,LL y){
	x--; y--; int p=0;//取模后范围是[0,???]，所以要x--,y--
	while (x%(1LL<<(p+1))>=1LL<<p || y%(1LL<<(p+1))>=1LL<<p) p++;
	return p;
}
int main(){
	t=getint();
	//getsg();
	while (t--){
		n=getint(); ans=0;
		for (LL i=1;i<=n/2;i++){x=getint(); y=getint(); ans^=sg(x,y);}
		if (ans) puts("YES"); else puts("NO");
	}
	return 0;
}