链接:https://ac.nowcoder.com/acm/contest/338/I
来源:牛客网
IG won the S championship and many people are excited, ii and gg are no exception. After watching the game, the two of them also want to play a game.
There is now an infinite chessboard with only one piece. Initially the pieces are placed at the (x, y) position (the board coordinates are counted from 0). They took turns to move the pieces. ii moves first.
There are three ways to move
It should be noted that the pieces cannot be removed from the board.
The first person who can not operate is judged negative (in other words, the first person who moves the piece to (0,0) wins).
Now give the initial coordinates x, y of the piece. Under the premise that both take the optimal strategy, please output the name of the winner (ii or gg).
The input contains only one line. Enter two integers x y to represent the initial coordinates of the piece. (0<=x, y<=1000)。
the winner’s name (ii or gg)。
输入
1 1
输出
ii
输入
124 654
输出
gg
ii和gg一起玩游戏,将一个石子放在棋盘(x,y)的位置,每次移动石子,必须把石子从(x,y)位置移动到(x,y-1)、(x-1,y)、(x-1,y-1)这三个位置中的其中一个位置,将石子移动到(0,0)点的人获胜,ii先移动
一、博弈论
推出一部分的NP态,可以发现,当并且时,先手处于必败态
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | P | N | P | N | P | N |
1 | N | N | N | N | N | N |
2 | P | N | P | N | P | N |
3 | N | N | N | N | N | N |
4 | P | N | P | N | P | N |
5 | N | N | N | N | N | N |
N代表先手必胜,P代表先手必败
二、DP
根据题意可以知道,(0,1),(1,1),(1,0)点为N状态。
可以得出递推关系:当前点如果为P状态,那么这个点的前一步对应的三个可能的点一定都为N状态
//NP
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
if((n&1)||(m&1))
cout<<"ii"<<endl;
else
cout<<"gg"<<endl;
return 0;
}
//DP
#include<bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
const int maxn=1e3+10;
using namespace std;
int dp[maxn][maxn];
inline void init()
{
ms(dp,0);
dp[0][1]=dp[1][0]=dp[1][1]=1;
for(int i=1;i<maxn;i++)
{
for(int j=1;j<maxn;j++)
if(dp[i-1][j]&&dp[i][j-1]&&dp[i-1][j-1])
dp[i][j]=0;
else
dp[i][j]=1;
}
}
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
init();
int n,m;
cin>>n>>m;
if(dp[n][m])
cout<<"ii"<<endl;
else
cout<<"gg"<<endl;
return 0;
}
本文地址:https://blog.csdn.net/wang_123_zy/article/details/85989303
如对本文有疑问, 点击进行留言回复!!
中国科大校友文库 机器学习理论及应用(当代科学技术基础理论与前
网友评论