一、递推与递归（递归实现指数型枚举、飞行员兄弟）
（递归实现指数型枚举）题目：
本题的递归搜索树及dfs思路：（yxc）
代码题解：
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 30;//防止边界问题，多开大些 int n, m; int way[N];//表示方案 void dfs(int u, int start) { if(u == m + 1)//当u == m + 1时已经选了m个数了 { for(int i = 1; i <= m; i++) printf("%d ", way[i]); puts(""); return; } for(int i = start; i <= n; i++) { way[u] = i; dfs(u + 1, i + 1);//i已经填了，现在填i + 1; way[u] = 0;//恢复现场 } } int main () { scanf("%d%d", &n, &m); dfs(1, 1); return 0; }
（飞行员兄弟）题目：
***解题的思路：看成是16个灯泡的开关状态，”-“表示打开，”+“表示关闭。关键语句：改变任何一个位置 [i,j][i,j] 上把手的状态。
但是，这也会使得第 ii 行和第 jj 列上的所有把手的状态也随着改变。
（1）枚举所有方案，0~2^16-1。时间复杂度：2^16*(16 * 7 + 16 +16)
(2) 按照该方案，对所有灯泡进行操作。（即从小到大枚举就是字典序最小）
（3）判断灯泡是否全亮并记录方案。
为了方便计算，我们将每一个灯泡的位置记为
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; #define x first #define y second typedef pair<int, int> PII; const int N = 5;//jixiongdedevc++多一位用来放\0 char g[N][N], backup[N][N];//backup[]是备份数组 int get(int x, int y)//返回第i,j的编号是多少 { return x * 4 + y; } void turn_one(int x, int y) { if(g[x][y] == '+') g[x][y] = '-'; else g[x][y] = '+'; } void turn_all(int x, int y)//按一行和一列 { for(int i = 0; i < 4; i++) { turn_one(x, i); turn_one(i, y); } turn_one(x,y);//(x,y)位置turn了两次所以要再turn一次 } int main () { for(int i = 0; i < 4; i++) cin >> g[i]; // 输入4次，每次输一行 vector<PII> res; for(int op = 0; op < 1 << 16; op++) { vector<PII>temp;// 把当前位置先存到temp里面去，注意这里是二维坐标 memcpy(backup, g, sizeof g);//先缓存一下 for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) if(op >> get(i, j) & 1)//如果当前位置是1的话--get的作用就是返回二进制数中那一位是第几位，从而判断是否为1 { temp.push_back({i, j}); turn_all(i,j);//操作一行和一列 } //判断索引是否全亮 bool closed = false; for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j ++) if(g[i][j] == '+') closed = true; if(closed == false) { if (res.empty() || res.size() > temp.size()) res = temp; } memcpy(g, backup, sizeof g); } cout << res.size() << endl; for(auto op: res) cout << op.x + 1 << ' ' << op.y + 1 << endl; return 0; }
二、前缀和
什么是前缀和：“一维前缀和 一维前缀和的得到很简单,也很好理解,上面的例子就是一维前缀和。 我们只需要遍历的时候一直把之前计算的和 加上自己就能得到当前的和。
（前缀和）题目：
代码题解：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; int n, m; const int N = 100010; int a[N];//原数组 int s[N];//前缀和数组 int main() { cin >> n >> m; for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); s[i] = s[i -1] + a[i]; } while(m --) { int l , r; cin >> l >> r; printf("%d\n", s[r] -s[l - 1]); } return 0; }
（分巧克力）题目：（二分算法）
输入样例：
2 10 6 5 5 6
输出样例：
2
代码题解：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int N = 100010; int h[N], w[N]; int n, k; bool check(int mid) { int res = 0;//分得的块数 for(int i = 0; i < n; i++) { res += (h[i] / mid) * (w[i] / mid);//关键公式 if(res >= k) return true; //等于号要加，边界问题 } return false; } int main () { cin >> n >> k; for(int i = 0; i < n; i++) scanf("%d%d", &h[i],&w[i]); int l = 1, r = 1e5; while(l < r)//二分右边 { int mid = l + r + 1 >> 1; if(check(mid)) l = mid; else r = mid - 1; } printf("%d\n", r); return 0; }
![【蓝桥杯】[递归]母牛的故事](https://ucc.alicdn.com/pic/developer-ecology/2is4p5rpji74e_be870067c97c42ca9083c25b149faaa5.png?x-oss-process=image/resize,h_160,m_lfit)