第十四届蓝桥杯三月真题刷题训练——第 21 天

叁歲伎倆 2023-09-27 16:37 83阅读 0赞

**目录**

第 1 题：灭鼠先锋

问题描述

运行限制

代码：

思路：

第 2 题：小蓝与钥匙

问题描述

答案提交

运行限制

代码：

思路 :

第 3 题：李白打酒加强版

第 4 题：机房

--------------------

## 第 1 题：[灭鼠先锋][Link 1] ##

> #### 问题描述 ####
> 
> **本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。**
> 
> 灭鼠先锋是一个老少咸宜的棋盘小游戏，由两人参与，轮流操作。
> 
> 灭鼠先锋的棋盘有各种规格，本题中游戏在两行四列的棋盘上进行。游戏的规则为：两人轮流操作，每次可选择在棋盘的一个空位上放置一个棋子，或在同一行的连续两个空位上各放置一个棋子，放下棋子后使棋盘放满的一方输掉游戏。
> 
> 小蓝和小乔一起玩游戏，小蓝先手，小乔后手。小蓝可以放置棋子的方法很多，通过旋转和翻转可以对应如下四种情况：
> 
>     XOOO XXOO OXOO OXXO
>     OOOO OOOO OOOO OOOO
> 
> 其中 O 表示棋盘上的一个方格为空，X 表示该方格已经放置了棋子。
> 
> 请问，对于以上四种情况，如果小蓝和小乔都是按照对自己最优的策略来玩游戏，小蓝是否能获胜。如果获胜，请用 V 表示，否则用 L 表示。请将四种情况的胜负结果按顺序连接在一起提交。
> 
> #### 运行限制 ####
> 
>  *  最大运行时间：1s
>  *  最大运行内存: 256M

### 代码： ###

package 第十四届蓝桥杯三月真题刷题训练.day21;
    
    /**
     * @author yx
     * @date 2023-03-24 8:27
     */
    public class 灭鼠先锋 {
        public static void main(String[] args) {
            System.out.println("LLLV");
        }
    }

![b07edd8894e9405293d90374044e68d2.png][]

### 思路： ###

> **（1）因为这个题目已经把先手的四种情况进行了说明，所以就非常好想**
> 
> **（2）我们只需要找到一种后手下棋思路让先手必输的情况，那对于后手来说就是最优方法**
> 
> **（3）分别在纸上画一下下棋思路即可**

## 第 2 题：[小蓝与钥匙][Link 2] ##

> #### 问题描述 ####
> 
> 小蓝是幼儿园的老师, 他的班上有 28 个孩子, 今天他和孩子们一起进行了 一个游戏。
> 
> 小蓝所在的学校是寄宿制学校, 28 个孩子分别有一个自己的房间, 每个房 间对应一把钥匙, 每把钥匙只能打开自己的门。现在小蓝让这 28 个孩子分别将 自己宿舍的钥匙上交, 再把这 28 把钥匙随机打乱分给每个孩子一把钥匙, 有 28!=28×27×⋯×1 种分配方案。小蓝想知道这些方案中, 有多少种方案恰有 一半的孩子被分到自己房间的钥匙 (即有 14 个孩子分到的是自己房间的钥匙, 有 14 个孩子分到的不是自己房间的钥匙)。
> 
> #### 答案提交 ####
> 
> 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。
> 
> #### 运行限制 ####
> 
>  *  最大运行时间：1s
>  *  最大运行内存: 512M

### 代码： ###

package 第十四届蓝桥杯三月真题刷题训练.day21;
    
    /**
     * @author yx
     * @date 2023-03-24 8:51
     */
    public class 小蓝与钥匙 {
        static int N=14;
        public static void main(String[] args) {
            /**
             * 1、先从28个人里面选14个人给定它们的钥匙，一共有C14 28 种选法
             * 2、剩下的14个钥匙分别发给不同的人，使他们拿到的都不是自己的钥匙
             * 3、后半部分属于全错排列问题，用递推来做
             */
            /*
            全错排列问题：f(x)=f(x-1)+f(x-2)
            f(0)=0;
            f(1)=0;
            f(2)=1;
             */
            //排列组合:2006329977
            long C_14_28=paiLie();
            long f1=0;
            long f2=1;
            long temp=0;
            for (int i = 3; i <= 14; i++) {
                temp=f2;
                f2=(i-1)*(f1+f2);
                f1=temp;
            }
            System.out.println(f2*C_14_28);
        }
    
        //
        static long paiLie(){
            long ans=1;
            for (long i = 0; i < 14; i++) {
                ans=ans*(28-i)/(i+1);
            }
            return ans;
        }
    }

![4403490b58b4429ea6458e8632d42ab3.png][]

### 思路 : ###

> （1）先从28个人里面选14个人给定它们的钥匙，一共有C14 28 种选法
> 
>     static long paiLie(){
>             long ans=1;
>             for (long i = 0; i < 14; i++) {
>                 ans=ans*(28-i)/(i+1);
>             }
>             return ans;
>         }
> 
> （2）剩下的14个钥匙分别发给不同的人，使他们拿到的都不是自己的钥匙，即全错排问题
> 
> （3）**全错排公式：****f(x)=(N-1) \* \[f(x-1)+f(x-2)\]**
> 
> **（4）推导过程：**
> 
>  *  首先是初始值：f1=0; f2=1; f3=9这几项是可以自己手撸的
>  *  当i>3，很明显手撸不太行，我们静下心来分析，要找其内在的规律
>  *  设N个人为a,b,c,d...,N张卡为A,B,C,D...
>  *  若a拿b的卡B,b也拿a的卡A,则显然只剩下N-2个人拿卡,自然是f(N-2)种了(好理解)
>  *  **若a拿b的卡B,b没拿a的卡A,则显然与N-1个人拿卡问题一样,自然是f(N-1)种了(不好理解)**
>  *  **为啥是f(N-1)种呢？注意：**这里的b没拿卡A，就相当于在N个数中a没拿卡A一样的道理,在N-1个数字中，b的卡片B被a拿走了，而B又不能拿A，其实就是把卡A变相看作是卡B的平替**，**那是不是就相当于看作了N-1个数字进行错排
>  *  a不一定拿B,只要是B,C,D...(N-1个)中的一个就可以了,所以在f(N-1)+f(N-2)再乘上N-1就行了.
>  *  得出递推公式：f(N)=(N-1)\*\[f(N-1)+f(N-2)\]

## 第 3 题：[李白打酒加强版][Link 3] ##

## 第 4 题：[机房][Link 4] ##

[Link 1]: https://www.lanqiao.cn/problems/2061/learning/?page=1&first_category_id=1&sort=students_count&tags=2022
[b07edd8894e9405293d90374044e68d2.png]: https://img-blog.csdnimg.cn/b07edd8894e9405293d90374044e68d2.png
[Link 2]: https://www.lanqiao.cn/problems/2167/learning/?page=6&first_category_id=1&sort=students_count&tags=2022
[4403490b58b4429ea6458e8632d42ab3.png]: https://img-blog.csdnimg.cn/4403490b58b4429ea6458e8632d42ab3.png
[Link 3]: https://www.lanqiao.cn/problems/2114/learning/?page=2&first_category_id=1&sort=students_count&tags=2022
[Link 4]: https://www.lanqiao.cn/problems/2198/learning/