象屿做核放单的网站江苏省通信建设交易中心网站

POJ 2311 Cutting Game

题目大意

有一张有$w\times h$个格子的长方形纸张，两个人轮流将当前的纸张中选一张，并沿着格子的边界将这张纸剪成两部分。最先切出只有一个格子的纸张（$1\times 1$的纸张）的玩家获胜。当双方都采用最优策略时，问先手必胜还是必败。必胜则输出WIN，必败则输出LOSE。

有多组数据。

数据范围

$2\le w,h\le 200$

题解

令$sg[i][j]$表示$i\times j$的纸张的状态，那么枚举剪的位置$k$，则

sg[i][j]=mex{sg[i][k]⊕sg[i][j−k],sg[i][k]⊕sg[i][j−k]}sg[i][j]=mex\{sg[i][k]\oplus sg[i][j-k],sg[i][k]\oplus sg[i][j-k]\}sg[i][j]=mex{sg[i][k]⊕sg[i][j−k],sg[i][k]⊕sg[i][j−k]}

我们可以预处理出所有$sg[i][j]$。

然后，对于每一组$w,h$，答案即为$sg[w][h]$，可以$O(1)$得出。

时间复杂度为$O(n^3)$。

code

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,z[205],sg[205][205];
int main()
{for(int i=1;i<=200;i++){for(int j=1;j<=200;j++){for(int k=0;k<=200;k++) z[k]=0;for(int k=2;k<i-1;k++){z[sg[k][j]^sg[i-k][j]]=1;}for(int k=2;k<j-1;k++){z[sg[i][k]^sg[i][j-k]]=1;}int x=0;for(;z[x];x++);sg[i][j]=x;}}while(scanf("%d%d",&n,&m)!=EOF){if(sg[n][m]) printf("WIN\n");else printf("LOSE\n");}return 0;
}