Chlience

【题解】POJ 2311 Cutting Game
Problem给出一个 $n$ 行 $m$ 列的格子,每次可以切任意对着某一块横着切一刀或者竖着切一刀,谁先切出 ...
扫描右侧二维码阅读全文
20
2019/02

【题解】POJ 2311 Cutting Game

Problem

给出一个 $n$ 行 $m$ 列的格子,每次可以切任意对着某一块横着切一刀或者竖着切一刀,谁先切出 $1*1$ 的格子谁就获胜

Thought

一般的想法:$sg[1][1]=0$ 然后直接按照 $sg$ 函数的定义推出来
然而这样会得到错误的答案

为什么呢?
假设当前状态为 $(2,1)$ ,可以将其切为两块 $(1,1),(1,1)$ ,那么 $sg[2][1]=1$
如果当前状态为 $(2,2)$ ,可以将其切为两块 $(2,1),(2,1)$ ,那么 $sg[2][2]=mex\{sg[2][1]\oplus sg[2][1]\}=1$ 显然是错误的

因为我们不需要所有块都达到 $(1,1)$ 的状态,换句话说,只要有有一个 $(1,1)$ 的块那么就可以结束了

所以两者应该都会尽力避免自己切出 $(n,1)$ 这样的块
也就是说,如果当前 全部 都是 $(2,2),(2,3),(3,3)$ 这样的块,那么下一次只能切出 $(n,1)$ 的块,也就是说,后手必胜

那么只需要将 $(2,2),(2,3),(3,3)$ 的 $SG$ 函数设为 $0$ 即可

Code

#include <vector>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 210;
int sg[N][N];
pair <int, int> bl[N * N];
void getSG(int x, int y) {
    for(int i = 2; i < x - 1; ++ i)
        bl[sg[i][y] ^ sg[x - i][y]] = make_pair(x, y);
    for(int i = 2; i < y - 1; ++ i)
        bl[sg[x][i] ^ sg[x][y - i]] = make_pair(x, y);
    while(bl[sg[x][y]] == make_pair(x, y)) ++ sg[x][y];
}
int n, m;
int main() {
    for(int i = 2; i <= 200; ++ i)
        for(int j = 2; j <= 200; ++ j)
            getSG(i, j);
    while(~scanf("%d %d", &n, &m))
        puts(sg[n][m] ? "WIN" : "LOSE");
    return 0;
}
Last modification:February 20th, 2019 at 02:19 pm

Leave a Comment