HDU2147 kiki's game （SG表找规律）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

Recently kiki has nothing to do. While she is bored, an idea appears in his mind, she just playes the checkerboard game.The size of the chesserboard is n*m.First of all, a coin is placed in the top right corner(1,m). Each time one people can move the coin into the left, the underneath or the left-underneath blank space.The person who can't make a move will lose the game. kiki plays it with ZZ.The game always starts with kiki. If both play perfectly, who will win the game?

InputInput contains multiple test cases. Each line contains two integer n, m (0<n,m<=2000). The input is terminated when n=0 and m=0.

OutputIf kiki wins the game printf "Wonderful!", else "What a pity!".
Sample Input

Sample Output

What a pity!

Wonderful!

Wonderful!

题意：

开始棋子在(n,m)，每次可向左，或向上，或左上走一步。走到(1,1)者胜利。

没有什么好的思路，SG函数转移没问题，但是MLE，所以打表找规律。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

int SG[maxn+][maxn+];

int ex[maxn],n,m;

void solve()

{

    int times=;

    for(int i=;i<=maxn;i++)

     for(int j=;j<=maxn;j++)

     {

         if(i==&&j==){

             SG[i][j]=;

             continue;

         }

         times++;

         if(i>) ex[SG[i-][j]]=times;

         if(j>) ex[SG[i][j-]]=times;

         if(i>&&j>) ex[SG[i-][j-]]=times;

         for(int k=;k<;k++){

             if(ex[k]!=times) {

                    SG[i][j]=k; break;

             }

         }

     }

}

int main()

{

    solve();

    for(int i=;i<=;i++){

        for(int j=;j<=;j++){

            if(SG[i][j]) printf("P ");

            else printf("N ");

        }

        printf("\n");

    }

}

N P N P N P N P N P

P P P P P P P P P P

N P N P N P N P N P

P P P P P P P P P P

N P N P N P N P N P

P P P P P P P P P P

N P N P N P N P N P

P P P P P P P P P P

N P N P N P N P N P

P P P P P P P P P P

Process exited normally.

Press any key to continue . . .

发现n和m都为奇数点才是必胜N态。

但是至于证明，我暂时还没想到。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,m;

int main()

{

    while(~scanf("%d%d",&n,&m)){

        if(n==&&m==) return ;

        n%=; m%=;

        if(n==||m==) printf("Wonderful!\n");

        else printf("What a pity!\n");

    } return ;

}

一个小时后，突然想起10000kb的内存，用bool应该没问题，果然。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

bool SG[maxn+][maxn+];

int n,m;

void solve()

{

    for(int i=;i<=maxn;i++)

     for(int j=;j<=maxn;j++)

     {

         if(i==&&j==){

             SG[i][j]=false;

             continue;

         }

         if(i>&&!SG[i-][j]) SG[i][j]=true;

         if(j>&&!SG[i][j-]) SG[i][j]=true;

         if(i>&&j>&&!SG[i-][j-]) SG[i][j]=true;

     }

}

int main()

{

    solve();

    while(~scanf("%d%d",&n,&m)){

        if(n==&&m==) return ;

        if(SG[n][m]) printf("Wonderful!\n");

        else printf("What a pity!\n");

    } return ;

}