kiki‘s game(巴什博奕+PN分析)

发布于 2020-10-29  0 次阅读


题目大意:

kiki‘s game
给你一个棋盘,其大小是n ∗ m,首先,在右上角( 1 , m )放一个硬币。
每次可以选择将硬币移到左侧,下方或左侧下方的空白区域,无法移动的人都会输掉比赛。
Kiki先手

思路:

首先PN点分析,从末状态左下点为必败点,往前推算其他的位置的局势
会发现规律为n或者m中至少一个为偶数时先手必胜

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}

void solve(){
    int n, m;
    while(~scanf("%d%d", &n, &m) && (n||m)){
        if(!(n&1) || !(m&1))    cout<<"Wonderful!"<<endl;
        else                    cout<<"What a pity!"<<endl;
    }
	return ;
}

signed main(){
    solve();
    return 0;
}

平平无奇的大学在读本科生