hdoj5754

佚名 6年前 (2019-04-10) 随笔 615人围观抢沙发百度已收录

题意：略

国王和骑士用记忆搜索，注意骑士的移动是x-2,y-1或x-1,y-2。车是NIM博弈，后是威佐夫博弈。注意威佐夫博弈中两堆石子有大小之分，而输入不一定小在前。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <stack>
#include <bitset>
#define mkp make_pair
using namespace std;
const double EPS=1e-8;
typedef long long lon;
const lon SZ=1010,SSZ=2*SZ,APB=26,INF=0x7FFFFFFF,mod=1000000007;
const double GOLDSEP=(1+sqrt(5))/2.0;
int dp1[SZ][SZ],dp2[SZ][SZ];

int dfs1(int x,int y)
{
    if(dp1[x][y]!=INF)return dp1[x][y];
    else if(x==0&&y==0)return dp1[x][y]=0;
    else
    {
        int dx[]={-1,0,-1},dy[]={0,-1,-1};
        int LM=3;
        dp1[x][y]=0;
        for(int i=0;i<LM;++i)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(nx>=0&&ny>=0)
            {
                if(!dfs1(nx,ny))dp1[x][y]=1;
            }
        }
        return dp1[x][y];
    }
}

int dfs2(int x,int y)
{
    //cout<<x<<" "<<y<<" "<<dp2[x][y]<<" "<<INF<<endl;
    if(dp2[x][y]!=INF)return dp2[x][y];
    else if(x==0&&y==0)return dp2[x][y]=-1;
    else if(!((x>=2&&y>=1)||(x>=1&&y>=2)))
    {
        //cout<<"here"<<(x>=3&&y>=2)<<" "<<x<<" "<<y<<endl;
        return dp2[x][y]=0;
    }
    else
    {
        int dx[]={-1,-2},dy[]={-2,-1};
        int LM=2,minv=INF;
        for(int i=0;i<LM;++i)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(nx>=0&&ny>=0)
            {
                minv=min(minv,dfs2(nx,ny));
            }
        }
        //cout<<"minv: "<<minv<<endl;
        return dp2[x][y]=0-minv;
    }
}

void init()
{
    int type,ll,rr;
    cin>>type>>ll>>rr;
    --ll,--rr;
    if(type==1)
    {
        if(dfs1(ll,rr))cout<<'B'<<endl;
        else cout<<'G'<<endl;
    }
    else if(type==2)
    {
        if((ll^rr))cout<<'B'<<endl;
        else cout<<'G'<<endl;
    }
    else if(type==3)
    {
        int res=dfs2(ll,rr);
        if(res==1)cout<<'B'<<endl;
        else if(res==0)cout<<'D'<<endl;
        else cout<<'G'<<endl;
    }
    else
    {
        if(ll>rr)swap(ll,rr);
        if((int)(GOLDSEP*(rr-ll))==ll)
        {
            cout<<'G'<<endl;
        }
        else cout<<'B'<<endl;
    }
}

void work()
{
    
}

int main()
{
    std::ios::sync_with_stdio(0);
    //freopen("d:\\1.txt","r",stdin);
    //freopen("d:\\2.txt","w",stdout);
    lon casenum;
    cin>>casenum;
    for(int i=0;i<SZ;++i)
    {
        for(int j=0;j<SZ;++j)
        {
            dp1[i][j]=dp2[i][j]=INF;
        }
    }
    //cout<<casenum<<endl;
    for(lon time=1;time<=casenum;++time)
    //for(lon time=1;cin>>n>>len>>wid;++time)
    {
        init();
        work();
    }
    return 0;
}