蓝桥杯
递归
利用递归+dfs枚举全排列
递归搜索树每一个递归问题都可以画成递归搜索树求解。
例题
AcWing 92. 递归实现指数型枚举
高中数学集合问题
思想：考虑选不选这个数。
import java.util.Scanner;
public class Main {
static int n, N = 16;
static int[] st = new int[N]; // 状态，记录每个位置当前的状态：0表示还没考虑，1表示选它，2表示不选它
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
dfs(1);
}
private static void dfs(int u) {
if (u > n) {
for (int i = 1; i <= n; i++) {
if (st[i] == 1) {
System.out.print(i + " ");
}
}
System.out.println();
return;
}
st[u] = 2;
dfs(u + 1); // 第一个分支：不选
// 这两行恢复现场加不加都一样的
// 因为递归时会被下面的值给覆盖掉 所以不用手动恢复 这里加上是让代码看起来更加圆滑 更加还原算法本身
st[u] = 0; // 恢复现场
st[u] = 1;
dfs(u + 1); // 第二个分支：选
st[u] = 0;
}
}
Acwing 94. 递归实现排列型枚举
高中数学枚举，输出n个数所有排列的次序。
题中说按字典序排列，但我们枚举后搜索树已经是按照字典序排列了。
思想：
- 依次枚举每个数放到哪个位置
- 依次枚举每个位置放那个数（本题代码）
import java.util.Scanner;
public class Main {
static int n, N = 10;
static int[] state = new int[N]; // 0表示还没放数，1~n表示放了哪个数
static boolean[] used = new boolean[N]; // true表示用过，false表示还未用过
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
dfs(1);
}
private static void dfs(int u) {
if (u > n) { // 边界
for (int i = 1; i <= n; i++) {
System.out.print(state[i] + " "); // 打印方案
}
System.out.println();
return;
}
// 依次枚举每个分支，即当前位置可以填哪些数
for (int i = 1; i <= n; i++) {
if (!used[i]) {
state[u] = i;
used[i] = true;
dfs(u + 1);
// 恢复现场
state[u] = 0;
used[i] = false;
}
}
}
}
AcWing 93. 递归实现组合型枚举
1~5选3个数，升序排列
思想：组合型枚举就是把指数型符合长度的结果挑出来。
优化：
剪枝，优化dfs，假如第一个数是4，那么只有5可以选，凑不成3个数，第一个数是5也同理，所以第一个数不需要考虑4和5的分支。
import java.util.Scanner;
public class Main {
static int n, m, N = 26;
static Scanner sc = new Scanner(System.in);
static int[] way = new int[N];
public static void main(String[] args) {
n = sc.nextInt();
m = sc.nextInt();
dfs(1, 1);
}
private static void dfs(int u, int start) {
if (u + n - start < m) return; // 剪枝 优化dfs 如果把后面所有数全选上，都不够m个，当前分支就一定无解
if (u == m + 1) { // 边界
for (int i = 1; i <= m; i++) {
System.out.print(way[i] + " "); // 打印方案
}
System.out.println();
return;
}
for (int i = start; i <= n; i++) {
way[u] = i;
dfs(u + 1, i + 1);
way[u] = 0; // 恢复现场
}
}
}
第四届2013年蓝桥杯真题
AcWing 1209. 带分数
JavaB组第9题
同样暴力枚举 n = a + b / c，两边同时乘c，c·n = c·a + b，n已知，枚举a，b，c即可求解。
import java.util.Scanner;
public class Main {
static final int N = 10;
static int n; // 输入的目标数
static int cnt; // 最后的结果数
static int[] num = new int[N]; // 保存全排列的结果
static boolean[] used = new boolean[N]; // 标记数字状态 true表示已使用，false表示未使用
static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
n = sc.nextInt();
dfs(0);
System.out.print(cnt);
}
private static void dfs(int u) {
if (u == 9) {
// 两层循环将数组分成三段
for (int i = 0; i < 7; i++) {
for(int j = i + 1; j < 8; j++) {
int a = calc(0, i);
if (a >= n) return; // 优化：如果a比n还大 说明无解 直接return
int b = calc(i + 1, j);
int c = calc(j + 1, 8);
if (a * c + b == c * n) { // n = a + b / c 化为 c·n = c·a + b
cnt++;
}
}
}
return;
}
// 全排列模板
for (int i = 1; i <= 9; i++) {
if (!used[i]) {
used[i] = true;
num[u] = i;
dfs(u + 1);
used[i] = false; // 恢复现场
}
}
}
// 在数组中计算某一区间的数
private static int calc(int l, int r) {
int res = 0;
for (int i = l; i <= r; i++) {
res = res * 10 + num[i];
}
return res;
}
}
y总的优化方案（很难）：其实我们不用枚举b了，当枚举完a和c后，利用公式变换得到b = c·n - c·a 即得到b的值。
import java.util.Scanner;
import java.util.Arrays;
public class Main {
static final int N = 10;
static int n; // 输入的目标数
static int ans; // 最后的结果数
static boolean[] st = new boolean[N]; // 标记数字状态 true表示已使用，false表示未使用
static boolean[] backup = new boolean[N]; // 判重数组，备份
static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
n = sc.nextInt();
dfs_a(0, 0);
System.out.print(ans);
}
private static void dfs_a(int u, int a) {
if (a >= n) return;
if (a != 0) dfs_c(u, a, 0);
for (int i = 1; i <= 9; i++) {
if (!st[i]) {
st[i] = true;
dfs_a(u + 1, a * 10 + i);
st[i] = false; // 恢复现场
}
}
}
private static void dfs_c(int u, int a, int c) {
if (u > 9) return;
if (check(a, c)) ans++;
for (int i = 1; i <= 9; i++) {
if (!st[i]) {
st[i] = true;
dfs_c(u + 1, a, c * 10 + i);
st[i] = false; // 恢复现场
}
}
}
private static boolean check(int a, int c) {
long b = n * (long)c - a * c; // 这里要定义为long，要不然可能会溢出
if (a == 0 || b == 0 || c == 0) return false; // 不包含0，直接返回
backup = Arrays.copyOf(st, st.length); // 将st数组的值copy到backup里，保持st原样，更改backup里面的值
while (b != 0) {
int x = (int)(b % 10); // 取个位
b /= 10; // 把个位删掉
if (x == 0 || backup[x]) return false;
backup[x] = true;
}
for (int i = 1; i <= 9; i++) {
if (!backup[i]) return false;
}
return true;
}
}
有对代码不理解的地方可以在下方评论。