华硕编程竞赛11月JAVA专场 D题飞机大战题解

Dear 丶 2023-09-24 15:22 33阅读 0赞

> **作者主页**：[Designer 小郑][Designer]  
> **作者简介**：Java全栈软件工程师一枚，来自浙江宁波，负责开发管理公司OA项目，专注软件前后端开发（Vue、SpringBoot和微信小程序）、系统定制、远程技术指导。CSDN学院、蓝桥云课认证讲师，全栈领域优质创作者，在校期间参加PAT乙级考试获得满分，三年ACM竞赛经验，斩获国奖两项，省奖五项。热爱技术、专注业务、开放合作、乐于分享，期待你我共同成长！  
> **主打方向**：Vue、SpringBoot、微信小程序

题目链接：[题目链接][Link 1]

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 题面： ###

小王在太空完成遨游后，就受邀来到了太空的飞机场指挥室，“太空号”少将小张早已等候他多时！

指挥所窗外是看不到界限的直线停机场，小张要和小王比试飞机的指挥能力，小王接受了挑战！

比赛规则是这样的：

1.  设指挥所窗外的第一个停机位编号为 0，窗外的第二个停机位编号为 1，以此类推。
2.  小王和小张双方轮流将某辆飞机召回到距离指挥所更近的停机位。
3.  飞机场上停有 `N` 辆初始的飞机，停机位编号分别为 `a[0] 到 a[n-1]`（取值大于0，即没有初始就停在编号为 0 的飞机）。
4.  飞机可以在这个超级太空中复用空间，即可以重叠排放，允许一个停机场停放无数多辆飞机，但最近只能召回到指挥所窗外的第一个停机位。
5.  当所有的初始飞机都被召回到指挥所窗外的第一个停机位时，最后召回的人获胜。

![图片描述][04249c67f85848b4af6c3602a0b116e5.png]

小张很赏识小王的作战能力，每次比赛都让小王先手指挥，请问小王能获胜吗？

若小王可以获胜，请输出 `Yes`，若不能获胜则输出 `No`。

> 引用说明：上面的图片来源于蓝桥云课。

### 知识点 ###

*  Java 的异或运算
 *  必败态的分析
 *  尼姆博弈

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 初始代码 ###

public class FMain {
        
    
        public static String doWork(List<Integer> list) {
        
            //代码编辑区 开始
            return "No";
            //代码编辑区 结束
        }
    
        public static void main(String[] args) {
        
            //测试用例
            System.out.println((Objects.equals("Yes",doWork(Arrays.asList(7,7,7))) ? "【√正确】" : "【X错误】 ") + "初始飞机停车编号为： 7 7 7，答案：" + doWork(Arrays.asList(7,7,7)));
            System.out.println((Objects.equals("No",doWork(Arrays.asList(7,7))) ? "【√正确】" : "【X错误】")  + " 初始飞机停车编号为： 7 7，答案：" + doWork(Arrays.asList(7,7)));
        }
    }

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 样例说明 ###

输入数据是一个 List，里面包括了 N 辆飞机的停机场编号。

如 List 内数值为 \[7, 7, 7\]，代表初始有三辆飞机，均停在编号为 7 的停机场，小王只需先召回其中一辆飞机到第一个停机位，剩下只要学小张的方法即可，必定可以获胜，输出 `Yes`。

如 List 内数值为 \[7, 7\]，代表初始有两辆飞机，均停在编号为 7 的停机场，不管小王如何召回，小张只要学小王的方法必定获胜，所以小王必败，输出 `No`。

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 题解 ###

考察对尼姆博弈的理解，此题寻找 **必败态（0，0）** 为关键。

若只有两辆飞机，且处于同一位置，则为先手的必败态，**即（N，N）是必败态**。

若有三辆飞机，其中两辆处于同一位置，第三辆在零点，**即（N，N，0）也是必败态**。

根据**尼姆博弈**的理论，可以推出飞机下标值的异或结果 `X`，若 `X` 等于 0，则小王可以获得胜利，否则小张胜利。

参考代码如下：

import java.util.Arrays;
    import java.util.List;
    import java.util.Objects;
    
    public class FAns {
        
    
        public static String doWork(List<Integer> list) {
        
            //代码编辑区 开始
            int ans = 0;
            for (Integer i : list) {
        
                ans ^= i;
            }
            return Objects.equals(0,ans) ? "No" : "Yes";
            //代码编辑区 结束
        }
    
        public static void main(String[] args) {
        
            //测试用例
            System.out.println((Objects.equals("Yes",doWork(Arrays.asList(7,7,7))) ? "【√正确】" : "【X错误】 ") + "初始飞机停车编号为： 7 7 7，答案：" + doWork(Arrays.asList(7,7,7)));
            System.out.println((Objects.equals("No",doWork(Arrays.asList(7,7))) ? "【√正确】" : "【X错误】")  + " 初始飞机停车编号为： 7 7，答案：" + doWork(Arrays.asList(7,7)));
        }
    }

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 总结 ###

要 AC 本题，必须学会**尼姆博弈**的算法，找到先手或后手的必败态，再尔退出必胜态，最终通过本题。

![在这里插入图片描述][3a01dc60e62c415b812015851343f1c0.png_pic_center]

[Designer]: https://blog.csdn.net/qq_41464123
[Link 1]: https://www.lanqiao.cn/contests/lqENT05/challenges/
[d20811fc24154b148e6372d8bd803dab.png_pic_center]: https://img-blog.csdnimg.cn/d20811fc24154b148e6372d8bd803dab.png#pic_center
[04249c67f85848b4af6c3602a0b116e5.png]: https://img-blog.csdnimg.cn/img_convert/04249c67f85848b4af6c3602a0b116e5.png
[3a01dc60e62c415b812015851343f1c0.png_pic_center]: https://img-blog.csdnimg.cn/3a01dc60e62c415b812015851343f1c0.png#pic_center