ccpc 江西省赛 博弈论 J Split Game

ccpc 江西省赛 博弈论 J Split Game
蓝书链接：https://www.acwing.com/problem/content/221/

题目大意：和蓝书上的有向图剪纸游戏博弈除了获胜方式不一样，其他几乎是一样，给你一个n×m的纸片，每一次可以将纸片剪成两部分，谁先剪出1×1的格子就必败。
题解思路：其他所有地方都几乎和蓝书上的模板题目相同，主要是如何处理必败态，训练赛中wa的点就是处理的时候简单的把1×1的状态也就是在sg[1][1]中表示的状态简单的划归为必胜态，这是完全不对的，其实稍加思考会发现sg搜索的过程中他是不会枚举1×1的状态的，因为这种状态对于参与游戏的两个人是必败状态，他们是不会主动去选择这种状态，因此枚举的时候不能简单的把这种状态加入到异或值中。笔者在赛后尝试的时候突然发现，如果将sg[1][1]值变为一个很大的数也是同样不会影响后续搜索的状态，但是就是不能变成1或者一些比较小的数，这会影响中间异或值的运算的。训练赛的时候应该尝试提交一下将sg[1][1] = 10000的这个代码的，落泪。
以上提到的是最重要的一点，其他方面就是sg函数搜索时的异或左右两张纸，没有太多坑点了。
第一种：不搜索[1,1]这个状态

#include<bits/stdc++.h>
using namespace std;
#define pb push_back

const int N = 160;
int n , m;
int sg[N][N];
int vis[N*N];
int SG(int n , int m){
    if(sg[n][m] != -1) {
        return sg[n][m];
    }
    unordered_map<int,int>vis;
    //puts("*");
    for(int i = 1 ;i <= n - i ;i ++){
        if(i == 1 && m == 1) continue;
        vis[SG(i, m) ^ SG(n-i , m)] = 1;
    }
    for(int i = 1;i <= m - i ; i ++){
        if(i == 1 && n == 1) continue;
        vis[SG(n , i ) ^ SG(n , m - i)] = 1;
    }
    sg[n][m] = 0;
    while(vis.count(sg[n][m]))sg[n][m] ++ ;
    return sg[m][n] = sg[n][m] ;
}

int main(){
    memset(sg , -1, sizeof sg);
//    SG(150,150);
//    puts("*");
    while(~scanf("%d%d" , &n , &m)){
        if(SG(n, m) > 0) puts("Alice");
        else puts("Bob");
//        for(int i = 1;i <= n ;i ++){
//            for(int j = 1;j <= m ;j ++){
//                printf("%d " , sg[i][j]);
//            }
//            puts("");
//        }
    }
}

第二种：将[1,1]这个状态变为一个不影响后续异或的值。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back

const int N = 160;
int n , m;
int sg[N][N];
int vis[N*N];
int SG(int n , int m){
    if(sg[n][m] != -1) {
        return sg[n][m];
    }
    unordered_map<int,int>vis;
    //puts("*");
    for(int i = 1 ;i <= n - i ;i ++){
//        if(i == 1 && m == 1) continue;
        vis[SG(i, m) ^ SG(n-i , m)] = 1;
    }
    for(int i = 1;i <= m - i ; i ++){
//        if(i == 1 && n == 1) continue;
        vis[SG(n , i ) ^ SG(n , m - i)] = 1;
    }
    sg[n][m] = 0;
    while(vis.count(sg[n][m]))sg[n][m] ++ ;
    return sg[m][n] = sg[n][m] ;
}

int main(){
    memset(sg , -1, sizeof sg);
//    SG(150,150);
//    puts("*");
    sg[1][1] = 10000;
    sg[1][2] = 0;
    sg[2][1] = 0;

    while(~scanf("%d%d" , &n , &m)){
        if(SG(n, m) > 0) puts("Alice");
        else puts("Bob");
//        for(int i = 1;i <= n ;i ++){
//            for(int j = 1;j <= m ;j ++){
//                printf("%d " , sg[i][j]);
//            }
//            puts("");
//        }
    }
}