1. 首页
2. 博弈
3. 本页

HDU 5754 Life Winner Bo (博弈)

题目链接：点我~~

题意：~~

思路：

我们依次分析每一种棋子。

①王。

首先注意一个3*3的棋盘，开始在(1,1)，问走到(3,3)谁有必胜策略。

穷举所有情况，容易发现这是后手赢。

对于N和M更大的情况，我们把横坐标每隔3、纵坐标每隔3的点都画出来，这些点都是符合后手胜的。
（因为无论先手怎么移动，后手都能重新移动到这些格子，直到到了终点）

如果初始点不在这些点上，就必然是先手胜。因为先手可以立刻移动到上述的点。

②车。

注意到，如果目前的位置距离终点的$x$和y坐标差相等，一定是后手胜。
（因为先手只能向下或者向右走一段路；无论他往哪里走，后手往另一维走相同的步数，依然保持这一样一种状态。）

反之，先手必然能走到一处相等的位置，转化为上述问题，所以一定是先手胜。

③马。

同样还是画图可以得到规律。

在大多数情况下都是平局。在模3域下，某些地方会存在先后手赢。

④皇后。

画画图后，我们可以将问题转化为：

“有两堆石子，每次可以在一堆里取任意（非空）颗（相当于是车的走法），或者在两堆里取相同（非空）颗（相当于是象的走法），取到最后一颗石子的人获胜，问先后手谁有必胜策略。”
此题中$N\le 1000$，可以直接用DP的方法解决。
设f[x][y]为横坐标距离终点x步，纵坐标距离终点y步时，必胜的是先手还是后手。

直接转移的话，可以枚举先手的下一步决策进行转移，这样是O(N^3)的。

注意到转移只是一行、一列或者斜着一列，这些都可以通过前缀和，做到最终O(N^2)。

其实对于更大的N也是可以做的。

由于叙述起来比较麻烦，具体的结论和证明可以参见：

https://en.wikipedia.org/wiki/Wythoff\%27s\_game

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int eps=1e-9;
const int pi=acos(-1.0);
const int mod=1e6+7;
const LL INF=0x3f3f3f3f;

int s[1010][1010];
int s2[1010][1010];
void init()
{
    s[2][1]=s[1][2]=1;
    s[0][0]=s[3][3]=-1;
    s[4][2]=s[2][4]=0;
    for(int i=9; i<=2000; i+=3)
    {
        for(int j=2; 2*j<=i; j++)
        {
            if(i-j>1000||j>1000) continue;
            int s1=-s[j-2][i-j-1];
            int s2=-s[j-1][i-j-2];
            s[j][i-j]=s[i-j][j]=max(s1,s2);
        }
    }
    memset(s2,-1,sizeof(s2));
    s2[1][1]=s2[0][1]=s2[1][0]=1;
    for(int i=3; i<=2000; i++)
    {

        for(int j=1; 2*j<=i; j++)
        {
            if(i-j>1000||j>1000) continue;
            int a1=-s2[j-1][i-j];
            int a2=-s2[j][i-j-1];
            int a3=-s2[j-1][i-j-1];
            if(a1>0||a2>0||a3>0)
                s2[j][i-j]=s2[i-j][j]=1;
            else s2[j][i-j]=s2[i-j][j]=-1;
        }
    }
}

int main()
{
    int T,t,m,n;
    init();
    cin>>T;
    while(T--)
    {
        cin>>t>>n>>m;
        int flag;
        if(t==1)
        {
            int buf=s2[n-1][m-1];
            if(buf==-1)flag=0;
            else flag=1;
        }
        else if(t==2)
        {
            if(m==n)
                flag=0;
            else flag=1;
        }
        else if(t==3)
        {
            if((n+m-2)%3!=0) flag=2;
            else
            {
                int k=s[n-1][m-1];
                if(k==-1) flag=0;
                if(k==0) flag=2;
                if(k==1) flag=1;
            }
        }
        else if(t==4)
        {
            n--;
            m--;
            int k = abs(n-m);
            n = n < m? n : m;
            int a_k= floor(k*(1.0 + sqrt(5.0))/2);
            if(n!=a_k) flag=1;
            else flag=0;
        }
        if(flag==0)cout<<"G"<<endl;
        if(flag==1)cout<<"B"<<endl;
        if(flag==2)cout<<"D"<<endl;
    }
}