蓝桥杯部分题目(含答案)
1、未名湖边的烦恼
关键词：递归，蓝桥杯，算法
问题描述
每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多
了，每天下午收工后，常常一双冰鞋都不剩。
每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问
题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同
样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）
输入格式
两个整数，表示m和n
输出格式
一个整数，表示队伍的排法的方案数。
### 蓝桥杯知识点解析
#### 一、未名湖边的烦恼
**关键词**：递归，蓝桥杯，算法
**问题背景**：
本题来源于蓝桥杯编程竞赛，题目背景设定在北京大学未名湖上的滑冰场景。在冬季，未名湖成为学生们的滑冰胜地。由于冰鞋数量有限，每天早上的租鞋窗口前都会排起长队。题目旨在考察参赛者对于递归算法的理解和应用。
**问题描述**：
假设在租鞋窗口前排队的队伍中，有 `m` 个人来还冰鞋，有 `n` 个人来租冰鞋。目标是计算有多少种不同的排队方式，可以确保租鞋窗口在任何时候都有足够的冰鞋出租。需要注意的是，相同需求的人（即同时为租鞋或还鞋）之间互换位置被视为同一种排列方式。
**输入格式**：
两个整数 `m` 和 `n`，分别表示还冰鞋的人数和租冰鞋的人数。
**输出格式**：
一个整数，表示满足条件的不同排队方式的数量。
**样例输入**：
```
3 2
```
**样例输出**：
```
5
```
**数据规模**：
`m`, `n` ∈ [0, 18]
**解决方案分析**：
本题可以通过递归的方式来解决。关键在于理解每一步的决策以及如何通过递归的方式减少问题的规模。
- **基本思路**：
- 如果 `m < n`，则无法实现任何一种排列方式使得始终有足够的冰鞋可供出租，因为还冰鞋的人比租冰鞋的人少。
- 如果 `n == 0`，则所有排队的人都只需要还冰鞋，此时只有一种排列方式。
- 对于其他情况，可以将问题拆分为两种子情况：一是第一个人还冰鞋；二是第一个人租冰鞋。
- 递归函数可以定义为 `f(m, n)`，表示还 `m` 双冰鞋的人和租 `n` 双冰鞋的人的排列数。
- **递归函数**：
```cpp
int f(int m, int n) {
if (m < n) return 0;
if (n == 0) return 1;
return f(m, n - 1) + f(m - 1, n);
}
```
**时间复杂度分析**：
递归解法的时间复杂度为 O(2^(m+n))，这可能非常低效。为了提高效率，可以考虑使用动态规划方法，通过记忆化搜索或者数组存储已计算的结果来减少重复计算。
---
#### 二、蚂蚁感冒
**关键词**：结构体排序，蓝桥杯
**问题背景**：
本题同样是来自蓝桥杯的编程题，题目背景设计在一个长为100厘米的细长直杆子上，上面分布着若干只蚂蚁。这些蚂蚁中有一只感冒了，并且在与其它蚂蚁相遇时会将其传染给对方。题目要求计算所有蚂蚁都爬离杆子后，感染感冒的蚂蚁总数。
**输入格式**：
- 第一行输入一个整数 `n` (1 < n < 50)，表示蚂蚁的总数。
- 接下来的一行包含 `n` 个整数 `Xi` (-100 < Xi < 100)，表示每只蚂蚁距离杆子左边端点的距离。正值表示头朝右，负值表示头朝左。
**输出格式**：
输出一个整数，表示最后感冒蚂蚁的数目。
**数据规模**：
`n` ∈ [1, 50]
**解决方案分析**：
- **基本思路**：
- 首先定义一个结构体 `location` 来存储每只蚂蚁的位置信息和是否感染感冒的状态。
- 使用结构体数组来保存所有蚂蚁的信息。
- 通过排序算法对蚂蚁的位置进行排序，以便按照蚂蚁之间的相对位置来模拟它们的移动。
- 模拟蚂蚁之间的碰撞并更新其方向和感染状态。
- **核心代码片段**：
```cpp
struct location {
int dir; // 方向：1 表示向右，-1 表示向左
int value; // 位置
int state; // 是否感染感冒：1 表示感染，0 表示未感染
};
bool cmp(struct location a, struct location b) {
return a.value < b.value;
}
int main() {
int n, i, tmp;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &tmp);
if (i == 0) loc[i].state = 1; // 第一只蚂蚁感冒
else loc[i].state = 0;
if (tmp > 0) {
loc[i].dir = 1;
loc[i].value = tmp;
} else {
loc[i].dir = -1;
loc[i].value = -tmp;
}
}
sort(loc, loc + n, cmp);
int flag = 1;
while (flag) {
flag = 0;
for (i = 0; i < n - 1; i++) {
if (loc[i].dir == 1 && loc[i + 1].dir == -1) {
loc[i].dir = -1;
loc[i + 1].dir = 1;
if (loc[i].state == 1 || loc[i + 1].state == 1) {
loc[i].state = 1;
loc[i + 1].state = 1;
flag = 1;
}
}
}
}
int cnt = 0;
for (i = 0; i < n; i++) {
if (loc[i].state == 1) cnt++;
}
printf("%d\n", cnt);
return 0;
}
```
**时间复杂度分析**：
- 排序的时间复杂度为 O(n log n)。
- 模拟碰撞的时间复杂度为 O(n^2)。
- 总体时间复杂度为 O(n^2 + n log n)。
这两个题目都很好地体现了蓝桥杯编程竞赛的特点，既考察了参赛者的算法思维能力，也要求参赛者具备一定的编程技巧和细节处理能力。
