P3150pb的游戏(1)

朱雀 2022-10-02 12:58 67阅读 0赞

# P3150pb的游戏(1) #

## 1.题目 ##

[P3150pb的游戏][P3150pb]

## 题目背景 ##

（原创）

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

## 题目描述 ##

游戏规则是这样的： 每次一个人可以对给出的数进行分割，将其割成两个非零自然数，之后由另一个人选择留下两个数中的其中一个；之后由另一个人进行分割这个剩下的数，重复步骤……

当一个人无法对数进行分割的时候游戏结束，另一个人获胜

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

每局由pb先进行分割，如果pb赢输出"pb wins" 如果zs赢输出"zs wins"

注：双方都是绝顶聪明的

这是一道简单的博弈问题

首先我们来看给出的数是奇数的情况

假设为１显然zs wins

假设为３那么一次分割只能分割成1和２zs选１的时候显然会输，所以肯定选的是２那么此时zs再切一次之后pb就没办法选了，所以zs wins

假设为５那么只能分割为１４或者２３分割为１４的时候zs选４再分成13就回到了为3的情况，假设为２３选２还是zs wins

由于奇数只能拆解为一个偶数和一个奇数的和，后手选择偶数的时候，我们自己切的时候将偶数变为奇数，所以我们只需要每一次都选择切偶数就好，保证是自己最后切到２，而先手永远不可能切到偶数，先手必输

对于偶数而言，先手可以将这个数分割成１和一个奇数，此时后手变先手切奇数，所以此时先手必胜．

import java.util.Scanner;
    
    public class boyi {
        
        public static int n;
        public static int m;
        public static void init(){
        
            Scanner input = new Scanner(System.in);
            n = input.nextInt();
            for(int i = 0;i < n;i++){
        
                m = input.nextInt();
                if(m%2 == 1){
        
                    System.out.println("zs wins");
                }else{
        
                    System.out.println("pb wins");
                }
            }
        }
        public static void main(String[] args){
        
            init();
        }
    }

[P3150pb]: https://www.luogu.org/problemnew/show/P3150