目录

• 🌟1、简单斐波那契【入门题】
• • 思路一 【递归】
  • 思路二 【递推】
• 🌟2、Acwing92.递归实现指数型枚举
• • 题目描述
  • 思路
  • AC代码
• 🌟3、94. 递归实现排列型枚举
• • 思路
  • AC代码
• 🌟4、Acwing .93. 递归实现组合型枚举
• • 思路
  • AC代码
• 🌟5、Awing95. 费解的开关
• • 思路 【类似八数码】
  • AC代码
• 🌟6、带分数
• • 思路
  • AC代码
• 🌟7、1208. 翻硬币
• • 思路
  • AC代码
• 🌟8、116. 飞行员兄弟
• • 思路
  • AC代码 [DFS]
  • 最后总结

蓝桥杯热门考点，不知道刷什么题，刷这些就行了，刷完就差不多可以巩固了，每道题都提供链接，建议都刷一遍。
1 - 4 题 模板题
5 - 8 题 实战题【部分真题】

🌟1、简单斐波那契【入门题】

Acwing.717.简单斐波那契

以下数列 `0 1 1 2 3 5 8 13 21 ...`被称为斐波纳契数列。这个数列从第` 3 `项开始，每一项都等于前两项之和。输入一个整数` N`，请你输出这个序列的前` N` 项。输入格式一个整数 N。输出格式在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。数据范围0<N<46输入样例：51输出样例：0 1 1 2 3

思路一 【递归】

#include using namespace std;int dfs(int u) { //从下标为0 开始    if(u == 0) { //第0项 return 0;    }    if (u == 1 || u == 2) { //第1、2项 return 1;    }    if (u > 2) {//第二项之后的 return dfs(u - 1) + dfs(u - 2);    }}int main () {    int n;    cin >> n;    for (int i = 0; i < n; i ++) { cout << dfs(i) << ' ';    }    return 0;}

思路二 【递推】

#include using namespace std;typedef long long ll;int main(){    int n;    cin >> n;    /*普通变量写法，节省空间*/    int a = 0, b = 1;    for (int i = 1; i <= n; i++) { cout << a << ' '; int c = a + b; a = b; b = c;    }    /*数组递推    ll f[46];    f[1] = 0, f[2] = 1;    for (int i = 3; i <= n; i++) { f[i] = f[i - 1] + f[i - 2];    }    for (int i = 1; i <= n; i++) { cout << f[i] << ' ';    }    */    return 0;}

🌟2、Acwing92.递归实现指数型枚举

题目描述

题目链接

思路

写出递归搜索树

AC代码

#include #include #include using namespace std;const int N = 16;int st[N];int n;void dfs (int u) {//u ：层数  if (u > n) {//都选完了    for (int i = 1; i <=n; i ++ ){      if (st[i] == 1) {//如果选了 就输出 cout << i << ' ';      }    }    puts("");    return ;  }  st[u] = 2;//2表示不选  dfs (u+1);//递归下一层  st[u] = 0;//回溯 【恢复现场】  st [u] = 1;//选  dfs (u + 1);//递归下一层  st[u] = 0;//回溯}int main () {  cin >> n;  dfs(1);  return 0;}

🌟3、94. 递归实现排列型枚举

题目链接

思路

这篇文章详细一点 DFS 排列数字

与排列数组一样 ，其实在枚举的时候，就已经按照字典序递归了。
可以定义一个数组path[N] 来保存当前的路径/模拟DFS的过程，当这个数组数字填满的时候，就把当前的数字输出出来，然后回溯的时候就需要一个核心操作回溯(恢复现场)

AC代码

#include using namespace std;const int N = 10;int path[N];int st[N];int n ;void dfs (int u) {  if(u > n) {    for (int i = 1; i <= n; i ++ ) {      cout << path[i] << ' ';    }    cout << endl;    return;  }  for (int i = 1; i <=n ; i ++ ) { //遍历每一个值    if (!st[i]){   st[i] = 1;   path[u] = i;   dfs (u + 1);   st[i] = 0; //恢复现场    }  }}int main () {  cin >> n;  dfs(1);  return 0;}

🌟4、Acwing .93. 递归实现组合型枚举

题目链接

思路

与上道题类似，只是细节上发生了一点小变化

AC代码

#include using namespace std;const int N = 30;int path[N];int n, m;void dfs (int u, int start ) {//u:层数  start：起始的数值    if (u > m) { for (int i = 1; i <= m; i ++ ) {     cout << path[i] << ' '; } puts("");    }    else { for (int i = start; i <= n; i ++) {//     path[u] = i;//表示已经填了     dfs(u + 1, i + 1);//递归下一层     path[u] = 0;//恢复现场 }    }} int main () {    cin >> n >> m;    dfs(1,1); //第一层开始  且从1开始枚举    return 0;}

🌟5、Awing95. 费解的开关

题目太长了 点链接看

思路 【类似八数码】

• 位运算（开关 ^1即可） + 递推
• 每一个位置最多只会操作一次。操作两次==不操作，自然就不可能是最优解。
• 递推的时候：第一行是不可以按的，第一行的要按的格子，确定了第二行要按的相应位置。换句话说，只能从下一行去改变上一行的灯的状态。
• 最后一行是不能按的。【因为它的上面行已经全是1了，我们就无法修改最后一行了】

AC代码

#include using namespace std ;const int N = 7;char g[N][N];int m;//取无穷 并不影响最大值void open(int x, int y) {    int dx[5] = {0, -1, 0, 1, 0}, dy[5] = {0, 0, 1, 0, -1};//分别对应 本位 右下左上    for (int i = 0; i < 5; i ++) {    int a = x + dx[i], b = y + dy[i]; if(a>=0 && a<5 && b>=0 && b<5) {//判断是否在5x5内      g[a][b] ^= 1;//异或 同 0 异1 }    }}int work() {  int ans = 1e8;for (int k = 0; k < 32; k ++) {//枚举第一行所以按法  int cnt =0; //cnt要写fou里面 教训！！！char tmp[10][10];//储存g memcpy(tmp,g,sizeof g);//copy g —> tmp for (int j = 0; j < 5; j ++) {  // <<优先级高于 &(只有1&1 == 1) if ((k >> j) & 1) {  //位运算 举例12和2 二进制分别是 cnt ++;//  01100  和 00010 open (0,j);//按第4、3位     按第2位 }  }//根据第一行  递推前四行 for (int i = 0; i < 4; i ++) {for (int j = 0; j < 5; j ++) {if(g[i][j] == '0') {cnt ++;open(i + 1, j);} }}//判断第四行死否全为1 bool is_successful = true;for(int j = 0; j < 5; j ++) {if(g[4][j] == '0') {is_successful = false;break;} }if(is_successful) {ans = min(ans,cnt);}memcpy(g,tmp,sizeof g);//恢复原状 }   if(ans > 6) {      ans = -1;  }return ans; }int main () {    cin >> m;    while ( m --) { for (int i = 0; i < 5; i ++) {  cin >> g[i]; } cout << work() << endl;    }    return 0;}

🌟6、带分数

题目链接

思路

dfs的排列数字 ①枚举a ②枚举c ③判断a c
n = a + b/c & b= n*c - a*c

AC代码

#include  using namespace std;int ans = 0;const int N = 520;int had_use[N],ever[N];int n;bool check(int a,int c){int b = n*c - a*c;if(!a||!b||!c) return false; //如果有一个数为0 memcpy(ever,had_use,sizeof had_use);//用来判断且不会改变原数组的目的while (b) {int t = b % 10;//取个位 b /= 10; //删除 if(!t ||ever[t]) return false;ever[t] = 1;}for (int i = 1; i <= 9; i ++) {if(!ever[i]) {return false;//判断1-9是否都已经用了}}return true;}void dfs_c(int x, int a, int c) {//x:已经用了多少个数 if (x >= 10) return;if(check(a, c)) ans ++;for (int i =1; i <= 9; i ++) {if(!had_use[i]) {//如果这个数没有用过 had_use[i] = 1;dfs_c(x + 1,a,c*10 + i);//递归下一层 had_use[i] = 0;//恢复现场(回溯) } }}void dfs_a(int x,int a) {if(a>=n) return;  if(a) dfs_c(x,a,0);//如果a满足 就枚举Cfor (int i = 1;i <= 9; i ++) {if (!had_use[i]) {//如果这个数没有被用过had_use[i] = 1;dfs_a(x + 1, a*10 + i);had_use[i] = 0;}} }int main () {cin >> n;dfs_a(0,0);cout <<ans << endl;return 0;} 

🌟7、1208. 翻硬币

题目链接

思路

一开始想到BFS的八数码，但是，如果用BFS时间复杂度为2¹⁰⁰一定会TLE的。
观察发现：

• 改变第一个的状态 ，只能操作第一个。[后面同理]
• 每个最多进行一次操作。【操作2次相当于没有操作】
• 操作次数最多为n-1 [如果操作完倒数第二个，且最后一个硬币与答案不同，则一定无解(因为操作最后一个，一定会影响前面那个)]
• 因此最后一个不需要操作

AC代码

#include #include #include using namespace std;const int N = 110;char s1[N],s2[N];void turn(int a) {  if(s1[a] == 'o') {    s1[a] ='*';  }  else {    s1[a] = 'o';  }}int main () {  int cnt = 0;  cin >> s1 >> s2;  int len = strlen(s1);  //只需执行到倒数第二个就行  for (int i = 0;i < len - 1; i ++) {    if(s1[i] != s2[i]) {      turn(i),turn(i + 1);      cnt ++;    }  }  cout << cnt << endl;   return 0;}

🌟8、116. 飞行员兄弟

题目链接

思路

和费解开关一样，可以位运算 +递推
我这里写DFS的版本
位运算可以看这个大佬的题解

AC代码 [DFS]

#include using namespace std;typedef pair<int, int> PII; const int N = 5;char g[N][N];int path[N][N];vector<PII>ans, tmp;void turn (int x, int y) { if(g[x][y]=='+'){g[x][y] ='-';}else {g[x][y] = '+';}for(int i = 0;i < 4; i ++) {if(g[i][y]=='+'){g[i][y] ='-';}else {g[i][y] = '+';}}for(int j = 0;j < 4; j ++) {if(g[x][j]=='+'){g[x][j] ='-';}else {g[x][j] = '+';}}} void dfs(int x, int y) {if(x==3 && y == 4) { //(3,4)是最后一个格子 bool success = true;for (int i = 0; i < 4; i ++) {for (int j = 0; j < 4; j ++) {if (g[i][j] == '+') {success = false;return ;}} }//答案为空 or 答案更优 则更新 if(success && (ans.empty()|| tmp.size() < ans.size())) {ans = tmp;}return ;}if(y ==4) {x++,y=0;//移动到下一行 }turn(x,y); tmp.push_back({x,y});dfs(x,y+1);//操作//恢复现场tmp.pop_back(); turn(x,y); dfs(x,y+1);//不操作 }int main () {for (int i = 0;i < 4; i ++) {cin >>g[i]; }dfs(0,0);cout << ans.size() << endl ;for (int i =0; i < ans.size(); i ++ ) {cout << ans[i].first + 1 <<' ' << ans[i].second + 1 << endl;}return 0;}

最后总结

• 目前我字符串还是不太熟，一碰到字符串就坐牢，一直A不了。今天开杠字符串，
• 位运算还得多刷几道