题解 | 算法竞赛进阶指南 Cutting Game

链接：https://ac.nowcoder.com/acm/contest/1029/A
来源：牛客网

题目描述

Urej loves to play various types of dull games. He usually asks other people to play with him. He says that playing those games can show his extraordinary wit. Recently Urej takes a great interest in a new game, and Erif Nezorf becomes the victim. To get away from suffering playing such a dull game, Erif Nezorf requests your help. The game uses a rectangular paper that consists of W*H grids. Two players cut the paper into two pieces of rectangular sections in turn. In each turn the player can cut either horizontally or vertically, keeping every grids unbroken. After N turns the paper will be broken into N+1 pieces, and in the later turn the players can choose any piece to cut. If one player cuts out a piece of paper with a single grid, he wins the game. If these two people are both quite clear, you should write a problem to tell whether the one who cut first can win or not.
输入描述:
The input contains multiple test cases. Each test case contains only two integers W and H(2≤W,H≤200)(2 \leq W, H \leq 200)(2≤W,H≤200) in one line, which are the width and height of the original paper.
输出描述:
For each test case, only one line should be printed. If the one who cut first can win the game, print "WIN", otherwise, print "LOSE".

示例1

输入
复制

2 2
3 2
4 2

输出
复制

LOSE
LOSE
WIN

题意

两个人在玩游戏。游戏规则如下：准备一张分成W x H的格子的长方形纸张，参与游戏的两个人轮流沿着格子的边界线切割纸张，水平或者垂直的奖纸张切割成两个部分。切割了n次之后就得到了n+1张纸，每次都选择切得的某一张纸再次进行切割。首先切出只有一个格子的纸张(1 x 1)的各自组成的纸张）的一方获胜。
每次都选择切得的某一张纸再次进行切割指的是以前全部切得的纸中的的某一个。

简单来说就是：给出一个的纸片，每一次可以把一部分剪成两部分，谁剪出的就赢了

题目分析

这是一道利用函数求解的题目

函数介绍**:https://www.cnblogs.com/DWVictor/p/10235851.html

我们知道，剪出纸片的前提是另一个人剪出或者,当然每个人都很聪明，不会这么做去让对方赢。
所以状态转移方程出来了出来了。

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int maxn=1e5+10;
int sg[206][206];
int flag[1005];
int main()
{
    int w,h;
    memset(sg,0,sizeof(sg));
    for(int i=2; i<=200; i++)//打sg表
    {
        for(int j=2; j<=200;j++)
        {
            memset(flag,0,sizeof(flag));
            for(int k=2; k<=j-2; k++)//横着切 竖着切
            {
                flag[(sg[i][k]^sg[i][j-k])]++;
            }
            for(int k=2; k<=i-2; k++)//横着切 竖着切
            {
                flag[(sg[k][j]^sg[i-k][j])]++;
            }
            for(int k=0; k<1000; k++)//求mex 
            {
                if(!flag[k])
                {
                    sg[i][j]=k;
                    break;
                }
            }
        }
    }
    while(scanf("%d%d",&w,&h)!=EOF)
    {
        if(sg[w][h])//不为0先手胜
            printf("WIN\n");
        else if(sg[w][h]==0)
            printf("LOSE\n");
    }
}