第十四届蓝桥杯三月真题刷题训练——第 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");}
}

思路：

（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;*///排列组合:2006329977long 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;}
}

思路 :

（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 题：李白打酒加强版 

第 4 题：机房