[衡阳八中1457 棋盘游戏]【博弈】【SG函数】【NIM和】【任意一子游戏到达终态结束的游戏】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1457
【算法分析】
首先，n个皇后是独立的，于是我们联想到利用SG函数来求解。
但是它与传统NIM游戏又有所不同，它是任意一个子游戏到达终态，那么就结束游戏。
好的，现在两个家伙都是绝顶聪明的。
于是他们肯定不会主动去走这样的一步：走完以后，该皇后x==0 || y==0 || x==y。
因为走完这步以后，对方就赢了，我们定义这种行为为沙茶。
因为他们都不会主动沙茶，那么就只能被沙茶。
也就是说所有的皇后的下一步都是令他沙茶的，那么才会真沙茶。
于是我们可以定义，下一步只能做沙茶的点为终态。
那么如果所有子游戏都到达终态，这时候先手必败。
这又刚好与传统NIM游戏一样了~
于是我们只要在计算SG函数时忽略x==0 || y==0 || x==y的点，那么就可以得我们定义所对应的SG函数值。
然后再利用那个Sprague-Grundy Theorem，再加上暴力计算SG函数，顺利解决本题。
【其它】1WA。注意那个SG函数的值好像是可能超100的= =。。。改大了瞬间AC。
【CODE】
#include #include #include #define flag(x,y) (!(!(x) || !(y) || (x)==(y)))
int SG[100][100];
bool v[100][100][205];

void Cal_SG(){
int i,j,k;
for (i=1;i<100;i++)
for (j=1;j<100;j++)
if (flag(i,j)){
for (k=1;i>=k || j>=k;k++){
if (i>=k && flag(i-k,j)) v[i][j][SG[i-k][j]]=true;
if (j>=k && flag(i,j-k)) v[i][j][SG[i][j-k]]=true;
if (i>=k && j>=k && flag(i-k,j-k))
v[i][j][SG[i-k][j-k]]=true;
}
for (k=0;k<=200;k++)
if (!v[i][j][k]){
SG[i][j]=k;
break;
}
}
}

inline void output(int x){
if (!x) puts("T_T");
else puts("^o^");
}

int main(){
int Tc,n,i,x,y,ans,check;
Cal_SG();
scanf("%d",&Tc);
for (;Tc;Tc–){
scanf("%d",&n);
ans=check=0;
for (i=1;i<=n;i++){
scanf("%d%d",&x,&y);
if (!x && !y) check=2;
if (!flag(x,y) && !check) check=1;
ans^=SG[x][y];
}
switch (check){
case 0:output(ans); break;
case 1:output(1); break;
case 2:output(0); break;
}
}
}