題意：兩個人玩游戲，有 n 塊石頭，初始坐標為（x，y），一次操作可以將一塊石頭移動到（x - u，y），（x，y - u）或者（x - u，y - u），坐標為（0,0）的石子不能移動，問先手贏還是輸。

分析：不是把所有數(shù)都變成（0，0）才贏，所以不是nim博弈，轉(zhuǎn)化一下，如果我把一對數(shù)變成了（x, x）或（x,0）或（0, x）那我必輸，那么我就假設這三種情況不能存在，誰最后無法操作誰輸，這樣就變成nim博弈了。也可以說是把終態(tài)當成（1，2）和（2，1）。參考https://blog.csdn.net/ccsu_cat/article/details/86760911。對nim博弈和sg函數(shù)還是理解的不夠深入。

代碼：

#include<bits/stdc++.h> using namespace std; const int N=105; int n,x,y,ans,fg,sg[N][N],vis[N*10];void init() {for(int i=1;i<N;i++)for(int j=1;j<N;j++) {if(i==j)continue;memset(vis,0,sizeof(vis));for(int k=1;k<i;k++) if(k!=j) vis[sg[k][j]]=1;for(int k=1;k<j;k++) if(k!=i) vis[sg[i][k]]=1;for(int k=1;k<min(i,j);k++) vis[sg[i-k][j-k]]=1;for(int k=0;;k++)if(!vis[k]) {sg[i][j]=k;break;}} }int main() {init();scanf("%d",&n);while(n--) {scanf("%d%d",&x,&y);ans^=sg[x][y];if(x==y) fg=1;}if(fg || ans) printf("Y\n");else printf("N\n");return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的博弈论总结（题目合集）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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