【Acwing 219. 剪紙游戲】

題意：

給定一張 N×M 的矩形網(wǎng)格紙，兩名玩家輪流行動(dòng)。
在每一次行動(dòng)中，可以任選一張矩形網(wǎng)格紙，沿著某一行或某一列的格線，把它剪成兩部分。
首先剪出 1×1 的格紙的玩家獲勝。
兩名玩家都采取最優(yōu)策略行動(dòng)，求先手是否能獲勝。

提示：開始時(shí)只有一張紙可以進(jìn)行裁剪，隨著游戲進(jìn)行，紙張被裁剪成 2,3,… 更多張，可選擇進(jìn)行裁剪的紙張就會(huì)越來越多。

題解：

常規(guī)的博弈論做法，用記憶化搜索來求每個(gè)狀態(tài)的后繼狀態(tài)的sg值，利用mex求出本狀態(tài)的值
本題與常規(guī)的博弈論不同點(diǎn)在于，一般博弈論是一方無法操作時(shí)結(jié)束比賽，而本題是達(dá)到某一狀態(tài)時(shí)結(jié)束比賽。常規(guī)來說我們要將紙裁成兩部分，循環(huán)應(yīng)該從1開始到n，但是本題不行，因?yàn)轭}目說了先剪除1 * 1的獲勝，也就是說如果我們?nèi)绻覀兿燃舫粋€(gè)邊為1，那么對(duì)手就可以借此剪除1 * 1，所以本題的最終狀態(tài)是無論怎么操作都會(huì)剪除一個(gè)邊為1，即除了1其他都不能剪除則輸，所能減的范圍是2,n-1，如果不能操作，則必?cái)?/p> for ( rg int i = 1; i <= n; ++i ){ vis [ sG ( i, c ) ^ sG ( n-i, c ) ] = true; }

本題巧妙的將最終狀態(tài)進(jìn)行定義，方便了代碼的實(shí)現(xiàn)

代碼：

#pragma GCC optimize("Ofast") #include<bits/stdc++.h> #define MAXN 205 using namespace std; typedef long long ll;int N,M; int sg[MAXN][MAXN];int dfs(int n, int m){if(n > m) swap(n,m);if(sg[n][m]!=-1) return sg[n][m];if(n==1 && m==1) return sg[n][m] = 0;//cerr<<"dfs: "<<n<<" "<<m<<endl;int vis[MAXN];memset(vis, 0, sizeof(vis));int ans;for(int x=2;x<n-1;x++){ans = dfs(x,m)^dfs(n-x,m);vis[ans] = 1;}for(int y=2;y<m-1;y++){ans = dfs(n,y)^dfs(n,m-y);vis[ans] = 1;}for(int i=0;i<=2*M;i++){if(!vis[i]) return sg[n][m] = i;} }int main(){memset(sg, -1, sizeof(sg));while(cin>>N>>M){if(N > M) swap(N, M);if(dfs(N,M)==0) puts("LOSE");else puts("WIN");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【Acwing 219. 剪纸游戏】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。