【题解】POJ2311 Cutting Game
题目大意
有一 W × H W imes H W×H 的矩阵,两人博弈,每次可以沿网格水平切割或竖直切割,当切割后出现 1 × 1 1 imes 1 1×1 的格子则获胜。给定 W , H ( 1 ≤ W , H ≤ 200 ) W,H(1le W,Hle 200) W,H(1≤W,H≤200),问先手必胜还是必败。
题解
博弈论。
显然必胜还是必败只跟当前矩阵的长宽有关,记忆化直接求 sg 函数值。
s g ( w , h ) = m e x { s g ( i , h ) ⊕ s g ( w − i , h ) , s g ( w , j ) ⊕ s g ( w , h − j ) } sg(w,h)=mex{ sg(i,h)oplus sg(w-i,h),sg(w,j)oplus sg(w,h-j)} sg(w,h)=mex{ sg(i,h)⊕sg(w−i,h),sg(w,j)⊕sg(w,h−j)}
但是直接写会挂。
考虑 1 × 1 1 imes 1 1×1 格子这个胜利条件。显然,当一方出现 1 × x 1 imes x 1×x 或 x × 1 x imes 1 x×1 的矩阵后,一次就能切出 1 × 1 1 imes 1 1×1 从而获胜。所以肯定不会让对方出现这两个局面,也即切割时不能切出长或宽为 1 1 1 的矩阵。注意这点即可 AC.
时间复杂度 O ( n 2 ) O(n^2) O(n2).
代码
#include <cstdio> #include <cstring> using namespace std; int n, m, sg[205][205]; int getsg(int w, int h) { if (w == 1 && h == 1) return sg[w][h] = 0; if (sg[w][h] != -1) return sg[w][h]; int mex[205]; memset(mex, 0, sizeof(mex)); for (int i = 2; i <= w / 2 && w - i >= 2; i++) mex[getsg(i, h) ^ getsg(w - i, h)] = 1;//w/2为了加快速度 for (int i = 2; i <= h / 2 && h - i >= 2; i++) mex[getsg(w, i) ^ getsg(w, h - i)] = 1; for (int i = 0; i <= 200; i++) if (!mex[i]) { sg[w][h] = i; break; } return sg[w][h]; } int main() { memset(sg, -1, sizeof(sg)); while (scanf("%d%d", &n, &m) != EOF) { if (getsg(n, m)) printf("WIN "); else printf("LOSE "); } return 0; }
END
下一篇:
文本文件单词的检索与计数