蓝桥杯 --- 递归与递推（习题）
蓝桥杯 --- 递归与递推（习题）
- 93. 递归实现组合型枚举
- 1209. 带分数
- 116. 飞行员兄弟
- 1208. 翻硬币
93. 递归实现组合型枚举
从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
输入格式
两个整数 n,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。
数据范围
n>0
0≤m≤n
n+(n−m)≤25
输入样例：
5 3
输出样例：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
#include<iostream>
using namespace std;
int n, m;
int f[30];
//x：当前选择了几个数
//y：从1开始往后选择，当前最大的数是几
void dfs(int x, int y) {
//没有数可以再选择了
if(x + n - y < m) return;
if(x == m) {
for(int i = 0; i < m; i ++ ) cout << f[i] << ' ';
cout << endl;
return;
}
for(int i = y; i < n; i ++ ) {
f[x] = i + 1;
dfs(x + 1, i + 1);
}
}
int main() {
cin >> n >> m;
dfs(0, 0);
return 0;
}
1209. 带分数
100 可以表示为带分数的形式：100=3+69258 / 714
还可以表示为：100=82+3546 / 197
注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0 ）。
类似这样的带分数，100 有 11 种表示法。
输入格式
一个正整数。
输出格式
输出输入数字用数码 1∼9
不重复不遗漏地组成带分数表示的全部种数。
数据范围
1≤N<106
输入样例1：
100
输出样例1：
11
输入样例2：
105
输出样例2：
6
解题思路
n = a + b / c 转化成 n * c = a * c + b
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N = 15;
bool flag[N];
bool backup[N];
int n;
int ans;
bool check(int a, int c) {
ll b = n * (ll)c - a * c;
if(!a || !b || !c) return false;
memcpy(backup, flag, sizeof flag);
while(b) {
int x = b % 10;
b /= 10;
if(!x || backup[x]) return false;
backup[x] = true;
}
for(int i = 1; i <= 9; i ++ ) {
if(!backup[i]) {
return false;
}
}
return true;
}
void dfs_c(int u, int a, int c) {
if(u >= 10) return;
if(check(a, c)) ans ++ ;
for(int i = 1; i <= 9; i ++ ) {
if(!flag[i]) {
flag[i] = true;
dfs_c(u + 1, a, c * 10 + i);
flag[i] = false;
}
}
}
//u：位数 a：数字值
void dfs_a(int u, int a) {
if(a >= n) return;
if(a) dfs_c(u, a, 0);
for(int i = 1; i <= 9; i ++ ) {
if(!flag[i]) {
flag[i] = true;
dfs_a(u + 1, a * 10 + i);
flag[i] = false;
}
}
}
int main() {
cin >> n;
dfs_a(0, 0);
cout << ans << endl;
return 0;
}
116. 飞行员兄弟
“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 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
解题思路
//一个把手改变，会使所在行列的所有把手全部反转
//特点：①在最优解里面每个把手只按一次，按两次没有区别，
//②按的顺序无关紧要，最终取决于这个把手按的次数！！！
//思考这个题可以递推出来吗？ 答案是：很难
//可以想一想，前面的题都是通过某种顺序，每一次都是影响一个灯泡，但是这个题
//不能使用前面的办法，因为操作一次会影响好多灯泡。所以想一想朴素做法
//我们发现这个题的数据范围很小，所以尝试用暴力解决ac
//暴力思路：①16个开关，所有开关的状态数量想一想是多少？ 答案是2^16！这个我感觉
//我这么笨还是可以想出来的，往后怎么想呢？
//状态数量即最大操作次数2^16（65536）,既然也不大，那就①枚举所有的方案，
//然后按照这个方案来操作
//②如果可以实现把手全开，证明此方案合法
//③然后统计这个方案里面需要操作的把手数量
//④在所有能按的开关数量里取一个最小值
//ac
//输出方案注意:若两种方案步数相同，按字典序（先按横坐标排序，再按纵坐标排序）
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
char g[4][4];
char backup[4][4];
int get(int i, int j) {
return i * 4 + j;
}
void turn_one(int i, int j) {
if(g[i][j] == '+') g[i][j] = '-';
else g[i][j] = '+';
}
void turn_all(int i, int j) {
for(int l = 0; l < 4; l ++ ) {
turn_one(i, l);
turn_one(l, j);
}
turn_one(i, j);
}
int main() {
for(int i = 0; i < 4; i ++ ) cin >> g[i];
vector<PII> res;
//枚举所有的操作状态
for(int op = 0; op < 1 << 16; op ++ ) {
vector<PII> temp;
memcpy(backup, g, sizeof g);
//对每种状态进行判断
for(int i = 0; i < 4; i ++ ) {
for(int j = 0; j < 4; j ++ ) {
int dist = get(i, j);
if(op >> dist & 1) {
temp.push_back({i, j});
turn_all(i, j);
}
}
}
//判断该种操作下是否全部的开关都已经打开
bool flag = false;
for(int i = 0; i < 4; i ++ ) {
for(int j = 0; j < 4; j ++ ) {
if(g[i][j] == '+') {
flag = true;
}
}
if(flag) break;
}
if(!flag) {
if(res.empty() || res.size() > temp.size()) {
res = temp;
}
}
memcpy(g, backup, sizeof backup);
}
cout << res.size() << endl;
for(int i = 0; i < res.size(); i ++ ) {
cout << res[i].first + 1 << ' ' << res[i].second + 1 << endl;
}
return 0;
}
1208. 翻硬币
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：**oo***oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式
一个整数，表示最小操作步数
数据范围
输入字符串的长度均不超过100。
数据保证答案一定有解。
输入样例1：
**********
o****o****
输出样例1：
5
输入样例2：
*o**o***o***
*o***o**o***
输出样例2：
1
解题思路
纯模拟
#include<iostream>
using namespace std;
int main() {
string a, b;
cin >> a >> b;
int step = 0;
for(int i = 0; i < a.size(); i ++ ) {
if(a[i] != b[i]) {
if(a[i] == '*') a[i] = 'o';
else a[i] = '*';
if(a[i + 1] == '*') a[i + 1] = 'o';
else a[i + 1] = '*';
step ++ ;
}
}
cout << step << endl;
return 0;
}