【P3150 pb的游戏（1）】

pb的游戏（1）

题目背景

有一天 pb 和 zs 玩游戏 你需要帮 zs 求出每局的胜败情况。

题目描述

游戏规则是这样的：

• 先手对给出的数进行分割，分割成两个正整数，之后接着后手选择留下两个数中的其中一个。两人轮流操作，直到一方无法操作，另一方胜利。

现在要你求出 N N N 次游戏的胜败。

我们认为双方绝顶聪明。每局由 pb 先进行分割。如果 pb 存在必胜策略，输出 pb wins；否则输出 zs wins。

输入格式

第一行一个数 N N N，表示数据组数。

之后 N N N 行，每行一个数 M M M，表示每局初始的数。

输出格式

共 N N N 行，每行一串字符，表示游戏结果。

样例 #1

样例输入 #1

5
1
3
7
20
5

样例输出 #1

zs wins
zs wins
zs wins
pb wins
zs wins

提示

对于全部数据， 1 < N < 50 1<N<50 1<N<50， 1 ≤ M ≤ 1 0 9 1\le M\le 10^9 1≤M≤109。

题目分析

在这个游戏中，玩家 pb 和 zs 轮流进行操作。pb 先将数 M 分割成两个正整数，然后 zs 选择其中一个数字，pb 再分割选中的数字，zs 选择，直到某一方无法操作。这时，无法操作的一方输掉游戏。

胜负判断

通过分析游戏规则，对于每个数字 M，需要判断是否 pb 有必胜策略。

1. 奇数与偶数:

   • 如果 M 是一个奇数，那么 pb 能将其分割成两个数，其中至少有一个数是偶数。然后 zs 选择的数字会使得下一个局面为偶数。
   • 如果 M 是一个偶数，则可以通过选择将其分割为两个奇数。

2. 简化问题:

   • 从示例可以看出，数的奇偶性决定了游戏的胜负。实际的游戏结果可以通过观察 M 是奇数还是偶数来确定：
     • 如果 M 是偶数，则 pb 可以将其分割成两个数（至少一个数为偶数），使得 zs 选择时总能让剩下的数为奇数或有利于 pb。
     • 如果 M 是奇数，则 pb 无法避免将数分割为两个奇数，zs 将有机会选择数字，使得最终的局面不利于 pb。

总结

• 对于每个输入数 M:
  • 如果 M 是偶数，pb 总能有必胜策略。
  • 如果 M 是奇数，zs 总能有必胜策略。

C++ 代码实现

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    while (N--) {
        long long M;
        cin >> M;
        
        if (M % 2 == 0) {
            cout << "pb wins" << endl;
        } else {
            cout << "zs wins" << endl;
        }
    }
    
    return 0;
}

代码说明

1. 输入处理: 读取 N（数据组数），然后逐行读取每个 M。
2. 判断游戏结果:
   • 使用模运算 (M % 2) 判断 M 是偶数还是奇数。
   • 输出对应的结果 "pb wins" 或 "zs wins"。

复杂度分析

• 时间复杂度: (O(N))，因为每个 M 的判断是常数时间操作。
• 空间复杂度: (O(1))，除了输入数据外，没有额外的空间开销。

总结

只要保证自己拿到的是偶数，给对面拆成奇数，对面只能拆成一个奇数、一个偶数；循环往复，一定能保证自己拆到2，对面只能拆1（拆不了）。