笔试时间：2022年8月21日

1 坐摩天轮

摩天轮有四个仓，每转动1/4圈称为一次转动。现在有几波人排队，每波人的人数都大于1。摩天轮的每个仓最多能坐四个人。现安排游客坐摩天轮，每个人都必须至少有一个同伴和其同仓。请问最少多少次转动可以将让游客都游玩一遍？

输入：

每波的人数*N波

输出：

最小转动次数

输入样例1：

2 5

输出样例1：

1

解释：

第一个仓坐第一波的2人+第二波的2人，转动一次

第二个仓坐第二波剩下的2人

共转动1次

输入样例2：

6 2 4

输出样例2：

2

解释：

第一个仓坐第一波的4人，转动一次

第一个仓坐第一波剩下的2人+第二波的2人，转动一次

第三个仓坐第三波的4人

共转动2次

2 逃出迷宫

一个迷宫中有空地（用.表示）、四个方向的传送带（用R L U D表示右 左 上 下）和出口（用O表示）。在传送带上则必须强制按其方向移动一格，撞墙直接昏迷，无法到达出口；循环在传送带上也无法到达出口。请问迷宫中有多少个格子是不能到达出口的？

输入第一行为行数和列数

输入样例1：

5 5
.....
.RRD.
.U.DR
.ULL.
....O

输出样例1：

10

解释：

被循环传送带包围起来的9个格子，以及向右撞墙的格子是无法到达出口的，共10个

3 通配符广告

给出一个含有通配符的模式串，看其它不含有通配符的串能否符合模式串的形式。

第一行是需要比较的字符串个数N，第二行是通配符模式串，后面N行是需要比较的字符串

输入样例1：

3
ab{X}cdc{Y}f{Z}e
abcdcfe
abddddcdcffge
abeeecdcfff

输出样例1：

True
True
False

解释：

第一个可以视为ab{}cdc{}f{}e，第二个可以视为ab{dddd}cdc{f}f{g}e，第三个的最后一个e匹配不到

4 最小子串和

定义01串的子串和为每个长度为2的子串的值的和。例如0101101的子串为：

01 ：1

10 ：10

01 ：1

11 ：11

10 ：10

01：1

其子串和为34。

现给出n次交换这些数字位子的机会，每次交换只能相邻两个数进行交换。请问交换完之后，子串和的最小值为多少（可以不使用完所有次数）。输入第一行为01串长度和可交换次数n，第二行为01串

输入样例1：

7 0
0101101

输出样例1：

34

解释：不能交换，字串和恒为34

输入样例2：

5 1
00110

输出样例2：

12

解释：可以交换一个数，变为00101，子串和为12

后续：已寄