每个能够移动的棋子都要移动——Every-SG 游戏

先看一个问题php

HDU 3595 GG and MM (Every_SG博弈)ios

题目有N个游戏同时进行，每一个游戏有两堆石子，每次从个数多的堆中取走数量小的数量的整数倍的石子。取最后一次的获胜。而且N个游戏同时进行，除非游戏结束，不然必须操做。 ide

如今问题变成了，每次都必须在每一个非空石子堆中选择。post

这个问题的核心在于：spa

对于咱们能够赢的单一游戏,咱们必定要拿到这一场游戏的胜利!code

因此,咱们只须要考虑如何让咱们必胜的游戏尽量长的玩下去。blog

可是对手却不但愿他必败的单一游戏玩的过久,这就是 Every-SG 游 戏不一样于其余 SG 游戏的地方:通常的 SG 游戏只有胜与负之间的博弈, 而 Every-SG 游戏又添加了长与短之间的博弈,这使得 Every-SG 游戏更 有嚼头,更有味道。 游戏

 

最后的定理是显然的，最大的单一游戏步数若是是奇数的话那么确定是先手取得进行最后一步。不然必定是对手取走最后一个棋子。ci

 

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 1010

int dp[N][N];

int dfs(int p,int q)
{
    if(p>q) swap(p,q);
    if(p==0)
    {
        dp[p][q] = 0;
        return 0;//必败
    }
    int k = q/p;
    int tp = q-p*k,tq = p;
    int flag = dfs(q-p*k,p);
    if(k==1)
    {
        dp[p][q] = dp[tp][tq]+1;
        return flag^1;
    }
    else
    {
        if(flag == 0)
        {
            dp[p][q] = dp[tp][tq]+1;
        }
        else dp[p][q] = dp[tp][tq]+2;
        return 1;
    }
}

int main() {
    int n;
    memset(dp,-1,sizeof(dp));
    while(cin>>n)
    {
        int mx = -1;
        for(int i=0;i<n;i++)
        {
            int p,q;
            cin>>p>>q;
            dfs(p,q);
            
            mx = max( mx,dp[min(p,q)][max(p,q)] );
        }
        if( (mx&1) ) printf("MM\n");
        else printf("GG\n");
    }
    return 0;
}