poj 2311
题意：有一张$n \times m$的格子，两个玩家轮流每次可以剪下一行/一列，第一个剪下$1\times 1$的玩家获胜。两个玩家都采用最优决策，求先手是否必胜。
考虑将一张格子定义为一个有向图游戏，最终游戏的$\text{SG}$值即为所有有向图游戏的异或和
考虑这个$1\times 1$获胜不符合我们有向图游戏的定义，我们做一些转化。
考虑到我们剪下$1 \times x, x \times 1$会使得当前的玩家必败。那么我们可以将局面
$(2,3), (3,2), (2,2)$设为必败局面，然后
$$
\text{SG}(x,y)=\text{mex}(\text{SG}(x - i,y) ⊕ \text{SG}(i,y) \cup \text{SG}(x ,y- i) ⊕ \text{SG}(x,i))
$$
注意多组询问完全可以将之前的$\text{SG}$函数值保留。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
int w, h, sg[205][205];
int dfs(int x, int y) {
if (sg[x][y] >= 0) return sg[x][y];
int mex[205];
ms(mex, 0);
for (int i = 2; i <= x - 2; ++i)
mex[dfs(i, y) ^ dfs(x - i, y)] = 1;
for (int i = 2; i <= y - 2; ++i)
mex[dfs(x, i) ^ dfs(x, y - i)] = 1;
for (int i = 0; ; ++i)
if (!mex[i]) return sg[x][y] = i;
}
void clean() {
}
int solve() {
clean();
if (dfs(w, h) == 0) puts("LOSE");
else puts("WIN");
return 0;
}
}
using flyinthesky::sg;
using flyinthesky::w;
using flyinthesky::h;
int main() {
ms(sg, -1);
sg[2][2] = 0, sg[2][3] = 0, sg[3][2] = 0;
while (scanf("%d%d", &w, &h) == 2) flyinthesky::solve();
return 0;
}
/*
*/
