多校hdu5754(博弈)

©此题中在Ｎ×Ｍ的棋盘中从（１，１）走到（Ｎ，Ｍ）Ｂ先走Ｇ后走，谁先到（Ｎ，Ｍ）谁赢，走法分为４中分别是国际象棋中的国王，车，马，王后的发，在四种走法下谁能赢；

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

①王。

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

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

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

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

②车。

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

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

③马。

　　因为只能向右下走所以有两种走法，左１右２，和左２右１；棋盘内有的是可以到达且到达的步数是不变的，分别设走１的k1步,第２种走法的为k2步;可以有方程k1*1+k2*2=m,k1*2+k2*1=n;联立求解，若k1,k2为正整数则能分出胜负；

根据奇偶求胜负。但是还有一点要注意，因为谁都不想输所以要输的人尽量走成平局，这种情况需判断k1与k2间之差大于等于２；大于２就是平局，不难推出。

④皇后。

　　仔细观察可发现这是一个威佐夫博弈，可利用n,m之差乘以1.618完美比例与m,n中最小的值进行比较若想等则后手赢。

以下是代码：

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <math.h>

#include<algorithm>

#define LL long long

#define d (sqrt(5)+1)/2　//黄金比例

using namespace std;

int main()

{

    int t,type,n,m;

     cin>>t;

     while(t--)

     {

         scanf("%d%d%d",&type,&n,&m);

         if(m>1000||n>1000||n<2||m<2)

         continue;

         n--,m--;

         if(type==1)

         {

             if(n%2==0&&m%2==0)

               printf("G\n");

             else

               printf("B\n");

         }

         if(type==2)

         {

             if(n==m)

             {

                printf("G\n");

             }

             else

             printf("B\n");

         }

         if(type==3)

         {

             if((2*n-m)/3*3==2*n-m&&(2*m-n)/3*3==2*m-n)

             {

                 int k1=(2*n-m)/3;

                 int k2=(2*m-n)/3;

                 int k=k2+k1;

                 if(abs(k1-k2)>1)

                 {

                       printf("D\n");

                       continue ;

                 }

                 else if(k%2==0)

                {

                        printf("G\n");

                }

                 else

                 printf("B\n");

             }

             else

             printf("D\n");

         }

         if(type==4)

         {

             if((int)(abs(n-m)*d)==min(n,m))　// 注意　(abs(n-m)*d)一定要转换成int型的否则会出错；

             {

                 printf("G\n");

             }

             else

             printf("B\n");

         }

     }

    return 0;

}

巴特西

多校hdu5754(博弈)

最新文章

热门文章