Acwing递归与递推（一）
递归问题可以尝试画一棵递归搜索树。
递归实现指数型枚举
思路
首先是写递归的结束条件。
- 每个选项都有选和不选两种状态，把每个选项都考虑一遍。
- 递归参数传递当前考虑的第几个元素，判断是最后一个，即可终止递归，输出结果。
包含参数：
- 一共有几个数，作为结束条件。
- 当前考虑第几个分支，这个作为函数参数传递。
- 前面的数有没有选，这个可以用一个数组实现。
#include<cstdio>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
const int N = 16;
int n;
int st[N];//记录每个位置的状态：0还没考虑，1选他，2不选他
void dfs(int u) {
if (u > n) {
for (int i = 1; i <= n; ++i) {
if (st[i] == 1) {
printf("%d ", i);
}
}
printf("\n");
return;
}
st[u] = 2;
dfs(u + 1);//第一个分支，选
st[u] = 0;//恢复现场
st[u] = 1;
dfs(u + 1);//第二个分支，不选
st[u] = 0;//恢复现场
}
int main() {
cin >> n;
dfs(1);
}上面用int存储选还是不选，只有两种状态，其实用bool也行。
用int更能体现“恢复现场”这一过程。
通过位存储状态
按位存储也可以实现同样的效果，并且更省内存。但门槛也相对较高。
- 第一次接触还是华为软挑的题目，用位存储信息。那时我大一，不知道怎么读写。
接触过嵌入式之后，现在是会点了，i从0开始：
- 按位读：
data >> i & 1 - 按位写：
data |= 1 << i
按位读，就是把第i位的数据移到第0位，与i做与操作，结果为0或1，也就是第i位的值
按位写，就是把1移到第i位，与原数据做或操作，把第i位赋值为1。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
void dfs(int u, int state) {
if (u == n) {
for (int i = 0; i < n; ++i) {
if (state >> i & 1) {
printf("%d ", i + 1);
}
}
printf("\n");
return;
}
dfs(u + 1, state);
dfs(u + 1, state | 1 << u);
}
int main() {
cin >> n;
dfs(0, 0);
}递归实现排列型枚举
指数型枚举中，每个数可选可不选。每个节点有两个分支，分别对应选和不选两种情况。
排列型枚举中，每个数都要选上，每个节点有n-i个分支，也就是没选的节点各占一个分支。
递归结束条件是，没有分支，也就是每个数都被选上。
也就是说，需要存储：
- 一共有几个数
- 存储选择状态
- 存储已选择的数据的顺序
存储状态需要提前定义好数组大小，这个大小可以根据题目给的数据范围来定。
#include<cstdio>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
const int N = 10;
int n;
bool st[N];
int path[N];
void dfs(int u) {
if (u > n) {
for (int i = 1; i <= n; ++i) {
printf("%d ", path[i]);
}
printf("\n");
return;
}
for (int i = 1; i <= n; i++) {
if (!st[i]) {
path[u] = i;
st[i] = true;
dfs(u + 1);
//恢复现场
st[i] = false;
path[u] = 0;
}
}
}
int main() {
cin >> n;
dfs(1);
}递归实现组合型枚举
递归的结束条件是：到达第n层。
- 需要记录当前的递归层数。
对于路径，可以设置一个全局遍历，需要恢复现场。 还需要记录当前的start，传递到了第几个值。
#include<cstdio>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
const int N = 30;
int m, n;
int path[N];
void dfs(int u, int start) {
if (u > m) {
for (int i = 1; i <= m; i++) {
printf("%d ", path[i]);
}
puts("");
} else {
for (int i = start; i <= n; i++) {
path[u] = i;
dfs(u + 1, i + 1);
path[u] = 0;
}
}
}
int main() {
scanf("%d%d", &n, &m);
dfs(1, 1);
}费解的开关
每一行开关的操作，完全被前一行的灯的亮灭状态所决定。 如果按偶数次，那结果是不变的。如果是奇数次，那结果跟第一次一样：
- 顺序可以任意
- 每个格子最多按一次
如何枚举第一行的操作
每行有5位，每位有按和不按2种状态，每行有32种按或不按的方案。
我们不确定哪种是最优的，需要枚举32种可能的按法。
我们也不需要每一行都枚举，因为第一行按完之后，第二行的操作也就确定了。
此时第二行操作的目的是为了保证第一行全亮。
如果第一行某一位是0，那么接下来的操作固定为，按下第二行上、同一列的按钮。
- 因为如果继续操作第一行，会影响到左右的数据。
第二行操作确定之后，第三行的操作也唯一确定，此时第三行操作的目的是为了保证第二行全亮。 第三行操作确定之后，第四行的操作也唯一确定，此时第四行操作的目的是为了保证第三行全亮。 第四行操作确定之后，第五行的操作也唯一确定，此时第五行操作的目的是为了保证第四行全亮。 第五行操作确定之后，没有第六行可供操作。此时，前四行已经全亮。我们需要判断第五行是否为全亮的状态。
- 如果第五行全亮，则该方案有解，输出操作的总次数。
- 如果第五行存在灭灯，由于没有第六行可供操作，所以这种情况无解。
字符类型
0和1的转换
可以通过位运算只操作最后一位：
- 字符
0，ASCII码为110000 - 字符
1，ASCII码为110001 - 切换方式，异或
1：data^=1
#include<cstdio>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
const int N = 6;
char g[N][N], back_up[N][N];
int n;
int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {0, 1, 0, -1, 0};
void turn(int x, int y) {
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)continue;
g[a][b] ^= 1;
}
}
int main() {
cin >> n;
while (n--) {
int res = 10;
for (int i = 0; i < 5; i++)
cin >> g[i];
for (int op = 0; op < 32; op++) {
memcpy(back_up, g, sizeof g);
int step = 0;
for (int i = 0; i < 5; i++) {
if (op >> i & 1) {
step++;
turn(0, i);
}
}
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 5; j++) {
if (g[i][j] == '0') {
step++;
turn(i + 1, j);
}
}
}
bool dark = false;
for (int i = 0; i < 5; i++) {
if (g[4][i] == '0') {
dark = true;
break;
}
}
if (!dark)
res = min(res, step);
memcpy(g, back_up, sizeof g);
}
if (res > 6)
res = -1;
cout << res << endl;
}
}