2016第三场多校联盟训练1003

【题意】给出N*M的棋盘和棋子的类型，两人以最优策略轮流走.棋子初始时在(1,1), 先走到(N,M)者获胜.(只能往右下角方向移动)。问对于给定的情形先手胜、败、平.

【解题方法】博弈。

1. king：可走到周围的8个格子.

   当前位置(i,j)的状态由(i+1,j) (i,j+1) (i+1,j+1)确定.

2. rook：可以横着竖着走任意个格子.

   简单推理可得只有i==j时必败，其余必胜.

3. knight：走"L"型路线.

   当前位置(i,j)的状态由(i+2,j+1) (i+1,j+2)确定.

   不同的是，题目要求不能移动且没有到右下角时为平手，那么只有knight可能出现平手，即走到边界时不能再移动.

   对于当前位置，如果能走到必败态，那么一定是必胜态；若不能走到必败态，那么如果能走到平局位置，则一定是平局;

4. queen：横竖斜走任意格子.

   对于每个必败态，将可到达的横竖斜格子全部置成必胜态.（这里也可以直接套用威佐夫博弈的公式，但是注意起点是从1,1开始的，威佐夫博弈是从0,0开始的）

【AC 代码】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N =1100;
int a[N][N],b[N][N],c[N][N],d[N];
void init()
{
    a[1][1]=0;
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            if(i==1&&j==1) continue;
            int flag=0;
            int xx,yy;
            xx=i-1,yy=j-1;
            if(xx>=1&&yy>=1){
                if(a[xx][yy]==0) flag=1;
            }
            xx=i,yy=j-1;
            if(xx>=1&&yy>=1){
                if(a[xx][yy]==0) flag=1;
            }
            xx=i-1,yy=j;
            if(xx>=1&&yy>=1){
                if(a[xx][yy]==0) flag=1;
            }
            a[i][j]=flag;
        }
    }
    memset(b,-1,sizeof(b));
    b[1][1]=0;
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            if(i==1&&j==1) continue;
            int xx,yy,x,y;
            xx=i-2,yy=j-1;
            x=i-1,y=j-2;
            if(xx>=1&&yy>=1&&x>=1&&y>=1){
                if(b[x][y]==0||b[xx][yy]==0) b[i][j]=1;
                else if(b[x][y]==1&&b[xx][yy]==1) b[i][j]=0;
            }
            else if(xx>=1&&yy>=1){
                if(b[xx][yy]==0) b[i][j]=1;
                else if(b[xx][yy]==1) a[i][j]=0;
            }
            else if(x>=1&&y>=1){
                if(b[x][y]==0) b[i][j]=1;
                else if(b[x][y]==1) b[i][j]=0;
            }
            }
        }
//    memset(d,0,sizeof(d));
//    int k=0,t;
//    for(int i=0;i<=1000;i++){
//            t=-1;
//        for(int j=0;j<=1000;j++){
//            if(d[j]==0){
//                t=j;
//                d[j]=1;
//                d[t+k]=1;
//                break;
//            }
//        }
//        if(t==-1||t+k>1000) break;
//        c[t][t+k]=1;
//        k++;
//    }
}
int main()
{
    init();
    int T,n,m,id;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&id,&n,&m);
        if(id==1){
            if(a[n][m]) printf("B\n");
            else printf("G\n");
        }
        else if(id==2){
            if(n==m) printf("G\n");
            else printf("B\n");
        }
        else if(id==3){
            if(b[n][m]==-1) printf("D\n");
            else if(b[n][m]==0) printf("G\n");
            else printf("B\n");
        }
        else{
            if(n>m) swap(n,m);
//            if(c[n-1][m-1])  printf("G\n");
//            else printf("B\n");
            double x=(1.0+sqrt((double)5.0))/2.0;
            n--,m--;
            int f=m-n;
            if(n==(int)(f*x)) puts("G");
            else puts("B");
        }
    }
    return 0;
}