HDU-6886 Tic-Tac-Toe-Nim(2020HDU多校第十场T10)

HDU-6886 Tic-Tac-Toe-Nim(2020HDU多校第十场T10)

正如题目名字，这是一个nim游戏

观察题目条件，前两次操作一定会清空两个位置，那么考虑后面得到的状态是否先手必胜即可

对于这两个位置，发现只有两种情况

两个位置共线

此时先手者直接选择同线的另一个即可，必胜

两个位置不共线

此时还剩下一个位置与这两个空位均不共线，其他6个位置均共线

考虑可能存在的结束情况:

1.6个位置中有一个被清空，则下一个人直接清空共线的另一个位置必胜

2.不共线的位置被清空，不影响结局

考虑把这个问题转化为普通的Nim游戏

可以认为如果那6个位置均为1时游戏必败，而不共线的一个位置随意

则转化为 六个共线位置的值-1 与 不共线位置的值 形成的普通Nim游戏，根据常识，直接异或判断即可

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
int rd(){
    int IO,s=0;
    while(!isdigit(IO=getchar()));
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return s;
}

int a[4][4];
int Check(){ // 判断是否必胜
    rep(i,1,3) rep(j,1,3) if(a[i][j]) {
        int fl=1;
        rep(k,1,3) if(j!=k && !a[i][k]) fl=0;
        rep(k,1,3) if(k!=i && !a[k][j]) fl=0;
        if(!fl) continue;
        int x=a[i][j],ans=0;
        a[i][j]=0;
        rep(i,1,3) rep(j,1,3) if(a[i][j]) ans^=a[i][j]-1; // 共线位置
        ans^=x,a[i][j]=x; // 不共线位置
        return ans;
    }
    return '?';
}

int main(){
    rep(kase,1,rd()) {
        rep(i,1,3) rep(j,1,3) a[i][j]=rd();
        int ans=0;
        rep(i,1,3) rep(j,1,3) {
            int t=a[i][j];
            a[i][j]=0;
            int fl=0;
            rep(x,1,3) rep(y,1,3) { // 枚举两次初始操作，注意两次操作不共线!
                if(x==i || y==j) continue;
                int t=a[x][y];
                a[x][y]=0;
                if(!Check()) fl=1;
                a[x][y]=t;
            }
            if(!fl) ans++;
            a[i][j]=t;
        }
        printf("%d
",ans);
    }
}