蓝桥杯第二讲--递推【习题】
前言
蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第二讲：递推【习题】
递推【例题】详见博客：蓝桥杯第二讲–递推【例题】
本篇博客所包含习题有：
👊翻硬币
👊飞行员兄弟
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
翻硬币
题目要求
题目描述：
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：**oo***oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式：
两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式：
一个整数，表示最小操作步数
数据范围：
输入字符串的长度均不超过100。
数据保证答案一定有解。
输入样例1：
**********
o****o****
输出样例1：
5
输入样例2：
*o**o***o***
*o***o**o***
输出样例2：
1
思路分析
从左到右递推一遍即可，只要发现不相等，那么就翻转该硬币以及该硬币右边的一个硬币
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105;
char f[N], g[N];
void turn(int u)
{
if (f[u] == '*')
f[u] = 'o';
else f[u] = '*';
}
int main()
{
scanf("%s%s", f, g);
int n = strlen(f);
int res = 0;
for (int i = 0; i < n; i ++ )
if (f[i] != g[i])
{
res ++;
turn(i);
turn(i + 1);
}
printf("%d\n", res);
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
飞行员兄弟
题目要求
题目描述：
“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 16 个把手的冰箱。
已知每个把手可以处于以下两种状态之一：打开或关闭。
只有当所有把手都打开时，冰箱才会打开。
把手可以表示为一个 4×4 的矩阵，您可以改变任何一个位置 [i,j] 上把手的状态。
但是，这也会使得第 i 行和第 j 列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式：
输入一共包含四行，每行包含四个把手的初始状态。
符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式：
第一行输出一个整数 N，表示所需的最小切换把手次数。
接下来 N 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。
注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
数据范围：
1 ≤ i, j ≤ 4
输入样例：
-+--
----
----
-+--
输出样例：
6
1 1
1 3
1 4
4 1
4 3
4 4
思路分析
本题有些类似 蓝桥杯第二讲–递推【例题】 中的 费解的开关，但是又不完全一样，费解的开关题目中影响关系是一一对应的，但是本题不一样，本题中对于任意一个开关，可以有多个开关改变其状态，本题采取爆搜的思路，即暴力枚举每一个开关，一共 16 个开关，每个开关无非就是关和开两种状态，故一共枚举 216次，我们用 0 去表示不操作，用 1 去表示操作，那么操作就是从 0 ~ 216 -1，本题需自修：位运算，图示 4 * 4 的矩阵，我们通过位运算的思维其实是把二维变一维：矩阵变成 01 串，我们给矩阵的每一个格子编号：从上到下，从左到右为 0，1，2，…，15，我们的 get() 函数用来获取第x行第y列的矩阵变成一维 01 串后的下标，turn_all() 函数是用来实现一行 + 一列的开关改变，注意 (x, y) 这个点被操作了两次，所以需要单独再次操作一次，turn() 函数就是具体的操作：即-变+，+变-
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 5;
char g[N][N], backup[N][N];
vector<PII> res;
void turn(int x, int y)
{
if (backup[x][y] == '-')
backup[x][y] = '+';
else backup[x][y] = '-';
}
void turn_all(int x, int y)
{
for (int i = 0; i < 4; i ++ )
{
turn(x, i);
turn(i, y);
}
turn(x, y);
}
int get(int x, int y)
{
return x * 4 + y;
}
int main()
{
for (int i = 0; i < 4; i ++ )
cin >> g[i];
for (int i = 0; i < 1 << 16; i ++ )
{
memcpy(backup, g, sizeof g);
vector<PII> tem_res;
for (int j = 0; j < 4; j ++ )
for (int k = 0; k < 4; k ++ )
if (i >> get(j, k) & 1)
{
tem_res.push_back({j, k});
turn_all(j, k);
}
bool flag = false;
for (int j = 0; j < 4; j ++ )
for (int k = 0; k < 4; k ++ )
if (backup[j][k] == '+')
{
flag = true;
break;
}
if (!flag)
if (res.empty() || res.size() > tem_res.size())
res = tem_res;
}
cout << res.size() << endl;
for (auto r : res)
cout << r.x + 1 << ' ' << r.y + 1 << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。
原文链接：chen-ac.blog.csdn.net/article/details/122555734
- 点赞
- 收藏
- 关注作者
评论（0）