题目链接
https://ac.nowcoder.com/acm/contest/7412/B
题目大意
棋盘左上角为(0,0)，在棋盘的(x,y)位置有一枚棋子，牛牛先移动，牛可乐再移动，轮流进行。规定：每只牛都采用最优移动策略，且每次移动只能向上移动1个或2个格，或者向左1个或2个格（不存在“左移1+上移1”的操作）。规定先无法移动的牛输。
解题思路
博弈论。（我也是刚听说）
正好借此机会学习并讲解一下。
博弈论
必败点（P点）：前一个选手(Previous player)将取胜的位置称为必败点，即谁先走到这个位置谁赢。
必胜点（N点）：下一个选手(Next player)将取胜的位置称为必胜点，即谁先走到这个位置谁输。
P-N表格的画法：
对于P-N表格，我们采用从终点往前推导的方法，因为，终点必定是必败点，终点不同，则必败点的位置不同，P-N表格的也不相同。
P-N表格的三个属性：
一：终点必定是必败点（P点）。因为在终点时，已经没办法走了，那么就是从前一个位置进入这个位置的人获胜。
二：对于必败点（P点），能一步进入这个点的必定是必胜点（N点），而必败点（P点）无论怎么走，也只能进入必败点（N点）。
三：对于必胜点（N点），可以进入必败点（P点），也可以进入必胜点（N点）。也就是说，必胜点（N点）可以由必胜点（N点）进入，也可以由必败点（P点）进入。
总而言之，1.终点为P点；2.P点只能进入N点；3.N点能进入P点和N点。
算法：
S1：将所有终结位置标记为必败点（P点）；
S2：将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点）；
S3：如果从某个点开始的所有一步操作都只能进入必胜点（N点），则将该点标记为必败点（P点）；
S4：如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到S2。
本题思路
画P-N表格吧。
首先找到所有终点，标记为P点。将(0,0)标记为P点。
将所有一步能到达P点的位置标记为N点。
一次操作能到达P点的位置有：一步到达P点的有(0,1)，(1,0)；两步到达P点的有(0,2)，(2,0)
将一次操作只能到达N点的位置标记为P点。
(0,3)，(1,1)，(3,0)
重复S2的过程
重复S3的过程
不断重复，最终得到
在图中可看到，此图是关于左上-右下对角线对称的，所以只关注左下三角即可。发现当且仅当y与x坐标之差为3的倍数或0时，为必败点（P点）。
AC代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
int t,x,y;
cin>>t;
while(t--){
cin>>x>>y;
int sum=x+y;
if(abs(x-y)%3==0) puts("awsl");
else puts("yyds");
}
} 
京公网安备 11010502036488号