洛谷P3150 pb的游戏(1) 题解
题目链接:
https://www.luogu.org/problemnew/show/P3150
分析:
这道题是一道典型的入门博弈论。我们可以进行如下考虑:
先引入一个奇偶的性质:
奇数=奇数+偶数 ;偶数=偶数+偶数/奇数+奇数
那么问题就简单了。
我们可以先倒推一下:什么时候无路可走呢?答案是1,而1是一个奇数,那么我们现在需要做的就是让每次轮到自己的都是偶数。
再观察上面两个性质:我们发现,如果保证自己下一步是偶数的话,对方当前肯定得对奇数操作,如果要让对方必须对奇数进行操作,那么先手最优解即为把一个偶数拆成两个奇数。
那么得出结论,如果m是偶数,那么先手方,即pb,一定会赢;反之则是zs。
end
#include<cstdio>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
if(n%2==0)
printf("pb wins\n");
else
printf("zs wins\n");
}
return 0;
}