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

这篇具有很好参考价值的文章主要介绍了第十四届蓝桥杯三月真题刷题训练——第 21 天。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第 1 题：灭鼠先锋

问题描述

运行限制

代码：

思路：

第 2 题：小蓝与钥匙

问题描述

答案提交

运行限制

代码：

思路 :

第 3 题：李白打酒加强版

第 4 题：机房

第 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");
    }
}

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

思路：

（1）因为这个题目已经把先手的四种情况进行了说明，所以就非常好想

（2）我们只需要找到一种后手下棋思路让先手必输的情况，那对于后手来说就是最优方法

（3）分别在纸上画一下下棋思路即可

第 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;
    }
}

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

思路 :

（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）推导过程：文章来源地址https://www.toymoban.com/news/detail-400518.html

首先是初始值：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)]