題目鏈接：J
藍書鏈接：藍書題
題目大意：和藍書上的有向圖剪紙游戲博弈除了獲勝方式不一樣，其他幾乎是一樣，給你一個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("");
// }
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/226308.html
標籤：其他