技术标签： 博弈
官方题解：我们依次分析每一种棋子。
①王。
首先注意一个3*3的棋盘，开始在(1,1)，问走到(3,3)谁有必胜策略。
穷举所有情况，容易发现这是后手赢。
对于NN和MM更大的情况，我们把横坐标每隔3、纵坐标每隔3的点都画出来，这些点都是符合后手胜的。
（因为无论先手怎么移动，后手都能重新移动到这些格子，直到到了终点）
如果初始点不在这些点上，就必然是先手胜。因为先手可以立刻移动到上述的点。
②车。
注意到，如果目前的位置距离终点的xx和yy坐标差相等，一定是后手胜。
（因为先手只能向下或者向右走一段路；无论他往哪里走，后手往另一维走相同的步数，依然保持这一样一种状态。）
反之，先手必然能走到一处相等的位置，转化为上述问题，所以一定是先手胜。
③马。
同样还是画图可以得到规律。
在大多数情况下都是平局。在模3域下，某些地方会存在先后手赢。
④皇后。
画画图后，我们可以将问题转化为：
“有两堆石子，每次可以在一堆里取任意（非空）颗（相当于是车的走法），或者在两堆里取相同（非空）颗（相当于是象的走法），取到最后一颗石子的人获胜，问先后手谁有必胜策略。”
此题中N\leq 1000N≤1000，可以直接用DP的方法解决。
设f[x][y]为横坐标距离终点x步，纵坐标距离终点y步时，必胜的是先手还是后手。
直接转移的话，可以枚举先手的下一步决策进行转移，这样是O(N^3)O(N
3
)的。
注意到转移只是一行、一列或者斜着一列，这些都可以通过前缀和，做到最终O(N^2)O(N
2
)。
其实对于更大的NN也是可以做的。
由于叙述起来比较麻烦，具体的结论和证明可以参见：
https://en.wikipedia.org/wiki/Wythoff\%27s_game
当时做是直接画图，在纸上列举出各种情况，坐标可以表示出来
#include <iostream>
#include <cstdio>
#include <math.h>
using namespace std;
int t,m,n;
int T;
int main()
{
//cout<<(316^388)<<endl;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&t,&n,&m);
if(n>m)
swap(n,m);
if (t==1)//王
{
n--;
m--;
if ((n%2==0) && (m%2==0)) printf("G\n");
else printf("B\n");
}
else if (t==2)//车
{
n--;
m--;
//int ans=n^m;
//cout<<((n^m)==0)<<endl;
if ((n^m)==0) printf("G\n");//这里不能写(n^m==0)等号运算符优先级大于异或
else printf("B\n");
}
else if (t==3)//马
{
n--;
m--;
if (n%3==0 && n==m) printf("G\n");
else if (m%3==2 && m-n==1) printf("B\n");
else printf("D\n");
}
else if (t==4)//后 威佐夫博弈
{
n--;
m--;
int tmp;
if(n<m)
{
tmp=n;
n=m;
m=tmp;
}
int k=n-m;
n=(int)(k*(1+sqrt(5))/2.0);
if(n==m)
printf("G\n");
else
printf("B\n");
}
}
return 0;
}
文章浏览阅读4.2k次。买的JmGO G1过保了，调焦不行。之前把调焦电机卸载了，某宝上找了好久，才找到个差不多的电机。抱着试试看的想法，淘了2个。如下图所示，和原来的相比，电机大小一样的，都是10*8mm，就是上面的齿轮形状不一样，还多了两个翅膀把上部分拆下来，发现和原有电机相比，少一个固定孔，本来想上面的减速部分直接用原来的电机头，发现螺丝孔距不一样，螺丝装不上去。只好用买来的新电机了，换上原来的齿轮头。这里..._坚果g1pro怎么换调焦
文章浏览阅读2k次，点赞17次，收藏14次。结果自动的进行了四舍五入分别详细讲解上面的四种方法，包括它们的原理、异同以及推荐使用的情况。fixedfixedsetf()综上所述，为了确保输出的一致性和准确性，推荐使用第一种或第二种方法，因为它们明确指定了固定点表示法和精度，能够更好地控制输出的格式。_c++保留小数点后几位怎么弄
文章浏览阅读496次。在gpio0的中断控制器为gic，在gic节点中#interrupt-cells属性被设置为3，这也就是为什么在gpio0节点中interrupts 属性有三个值，而ft5x06的中断控制器为gpio0，在gpio0节点中#interrupt-cells属性被设置为2，所以ft5x06节点的interrupts 属性只有两个值。中断信号源节点（例如设备节点或其他中断源节点）中的 interrupt-parent 属性用于指定中断信号源所属的中断控制器节点。中断信号源是产生中断的设备或其他中断源节点。_rk interrupts
文章浏览阅读482次。信号机制是 Linux 0.11 为进程提供的一套"局部的类中断机制"，即在进程执行的过程中，如果系统发现某个进程接收到了信号，就暂时打断进程的执行，转而去执行该进程的信号处理程序，处理完毕后，再从进程"被打断"之处继续执行。_linux0.11 do_signal
文章浏览阅读843次。arm-linux-gcc: Command not found_arm-linux-gcc未找到命令怎么解决
文章浏览阅读98次。123456下列写法错误7下列写法错误转载于:https://www.cnblogs.com/anvivi/p/9695592.html_元素另外一个常见的用途是
文章浏览阅读948次，点赞2次，收藏4次。excel实用技能汇总一．工作中常用的30个excel函数公式1.数字处理（1）取绝对值（2）取整（3）四舍五入（1）案例 =ABS()取整取整分为三种，分别是：（2.1）格式取整（也就是在单元格中通过格式控制显示为整数（四舍五入得到），复制其单元格到其他单元格里面的值依然包含小数点）；（2.2）数值取整（非四舍五入）：在单元格中通过公式取整 -..._excel技能大全
文章浏览阅读57次。#include<vector>#include<string>#include<iostream>#include<algorithm>using namespace std;struct show{ int count; show (): count(0){} void operator()(const char& c){ cout << c; count ++; }};int main(){ vec_c++ foreach (var item, pcfg->cloud_cfg)
文章浏览阅读5.8k次，点赞10次，收藏58次。顺序表的存储结构如下：typedef struct{ ElemType *elem; int length; int listsize;}SqList;顺序表的初始化如下：void InitList_Sq(SqList &L){ //构造一个空的线性表L L.elem = (ElemType *)malloc(LIST_..._在顺序表的指定位置插入元素
文章浏览阅读1k次。c# datetime. DateTime.Month属性 (DateTime.Month Property)DateTime.Month Property is used to get the year component of this object. It's a GET property of DateTime class. DateTime.Month属性用于获取此对象的年份组成部分..._datetime,.year()
文章浏览阅读1.2k次。MTF的倾斜边缘法计算方法简介光学系统性能的衡量方法有很多，常见的有点扩散函数法、瑞利判断法、点列图法、光学传递函数(MTF)法等，其中MTF法在光学系统和镜头加工制造中使用最为广泛。MTF曲线真实的反映了成像系统将物方信息传递到像方的能力。MTF曲线的横坐标一般是cycle/mm或者linepair/mm[1][11]，纵坐标是反映对比度传递特性的像/物方调制度的比值。MTF的计算方法有很多，比..._matlab斜边超采样得到esf
文章浏览阅读493次。在用户态应用程序处理的任务中，elf 加载运行是一个比较重要的步骤，下面就分析一下在 rt-smart 操作系统中，想要将一个应用程序运行起来要经过哪些步骤。ELF 格式介绍ELF 代表 Executable and Linkable Format。它是一种对可执行文件、目标文件和库使用的文件格式。它在 Linux 下成为标准格式已经很长时间，ELF 一个特别的优点在于，同一文件格式可以用于内核支..._rtt5.0 elf文件