题目2：AcWing 1209.带分数【简单，蓝桥杯编程第2题】
来源：第四届蓝桥杯省赛C++B/C组,第四届蓝桥杯省赛JAVAA/B组
链接：1209. 带分数
import java.util.*; class Main { private static int n; private static boolean[] v = new boolean[10]; //记录结果集 private static int ans; //检查 private static boolean check(int a, int c) { //计算b int b = n * c - a * c; //提前剪枝（若是出现0则直接结束） if (a == 0 || b <= 0 || c == 0) return false; //复制拷贝是否存在的数组（避免重新恢复现场） boolean[] vv = Arrays.copyOfRange(v, 0, v.length); //遍历b的所有元素 while (b != 0) { int x = b % 10; //若是b中出现0或者之前已经出现过，此时直接就结束 if (x == 0 || vv[x]) return false; //记录访问过 vv[x] = true; b = b / 10; } //遍历10个数是否都有存在 for (int i = 1; i <= 9; i++) { if (!vv[i]) return false; } return true; } public static void dfs_c(int u, int a, int c) { //c以n的最大长度最为基准 if (u == n) return; //相当于枚举出来一组a,c if (check(a, c)) ans++; //向下递归推举出下一个c for (int i = 1; i <= 9; i++) { if (!v[i]) { v[i] = true; dfs_c(u + 1, a, c * 10 + i); v[i] = false; } } } //在进行递归推的时候算出a的值 public static void dfs_a(int u, int a) { //若是a的值>=n数字，此时就直接提前结束 if (a >= n) return; //符合条件情况，向下递归推出c if (a != 0) { dfs_c(u, a, 0); } for (int i = 1; i <= 9; i++) { if (!v[i]) { v[i] = true; dfs_a(u + 1, a * 10 + i); v[i] = false; } } } //枚举出来a,c => 推出b，最后进行check检查 //全排列+check检查【更加复杂】 public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); dfs_a(0, 0); System.out.printf("%d", ans); } }
题目3：AcWing 95.费解的开关【中等】
来源：《算法竞赛进阶指南》
链接：95. 费解的开关
学习链接：AcWing 95. 费解的开关
思路：是否点亮全部的灯泡完全取决于第一行是否按灯泡开关起到了决定性的作用，后面的四行都是依据前一行来进行开关动作。当前给出的是固定范围，5x5，第一行有五个格子，换成二进制表示5位就有32中按法，该题中我们需要来进行所有方案的枚举即可找到最少次数的按键。
复杂度分析：时间复杂度计算（32x(25x5)x500）
其中32表示一个问题解的第一行开关按钮的方案数，25表示要对25个格子进行遍历判断亮关，5表示若是进行开那么上下左右以及当前位置需要进行变换操作，最后的500则是可能出现最大500个方案问题。 约等于2000000，在一亿次运行范围中。 import java.util.*; class Main { //输入情况数 private static int n; //backup表示备份矩阵 private static int[][] arr = new int[5][5], backup = new int[5][5]; //结果集 private static int ans = Integer.MAX_VALUE; //定义x、y方向 上下左右中 private static int[] dx = {-1, 1, 0, 0, 0}; private static int[] dy = {0, 0, -1, 1, 0}; //按开关 public static void turn(int i, int j) { //五个位置：上下左右中 for (int pos = 0; pos < 5; pos++) { int x = i + dx[pos]; int y = j + dy[pos]; //若是越界则不进行开关操作（1->0 0->） if (x < 0 || x >= 5 || y < 0 || y >= 5) continue; //0^1=1 1^1=0 backup[x][y] ^= 1; } } /* 01111 11111 11111 11111 11111 **/ public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); while (n != 0) { //初始化 for (int i = 0; i < 5; i++) { String s = sc.next(); for (int j = 0; j < 5; j++) { arr[i][j] = s.charAt(j) - '0'; } } //每个位置的开关操作表示一个按法（按or不按） //对于00000，5位可以有32种按法 00000 00001 00010 00011，其中1就是开，0就是不按 for (int op = 0; op < 1 << 5; op++) { int cnt = 0;//记录当前方案按的次数 //备份与arr同样的状态backup，之后的模拟操作针对backup数组 for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) backup[i][j] = arr[i][j]; //对第一行进行操作 //op表示的就是一个方案，根据来操作 //根据当前的op方案来按第一行灯泡 for (int j = 0; j < 5; j++){ //取出最后一个，例如：0 二进制表示00000000，op>>0表示进行右移1位，此时&1，就是取到最后一位，当前是0 //之后四个方案一次对应表示 if ((op >> j & 1) == 1){ turn(0, j); cnt++; } } //对后四行来进行操作 for (int i = 0; i < 4; i++) { for (int j = 0; j < 5; j++) { //若是当前行没有点亮 if (backup[i][j] == 0) { turn(i + 1, j); cnt++; } } } //check最后一行是否全部点亮（有一个没点亮表示该方案不成立） int j = 0; while (j < 5) { if (backup[4][j] == 0) break; j++; } //若是当前的方案能够完全点亮 if (j == 5 && cnt <= 6) ans = Math.min(cnt, ans); } if (ans > 6) ans = -1; System.out.printf("%d\n", ans); n--; ans = Integer.MAX_VALUE; } } }
题目4：AcWing 116.飞行员兄弟【简单】
来源：《算法竞赛进阶指南》
视频讲解：2.1 链接：116. 飞行员兄弟 y总分析：数据量小，可以使用暴力搜索。216=65535，数据量不大，枚举所有方案，再最终check所有状态。【太强了 】 优化：可以使用二进制来进行优化，不过当前使用数组方案是能够满足情况的。 思路：将16个格子从左往右，从上至下，看做是16位的数，可使用一个int整型表示。 import java.util.*; //顺序从上到下，从左到右 //枚举16位 //2^16 x 7 x 16 约733万 class Main { static class Pair<K, V> { K x; V y; public Pair(K x, V y) { this.x = x; this.y = y; } } static final int N = 4; static char[][] arr = new char[4][4], backup = new char[4][4]; //保存结果集、按下的位置 static List<Pair<Integer, Integer>> ansList; //根据i与j取得当前的位数 public static int getPos(int i, int j) { return i * 4 + j; } public static void turnOne(int x, int y) { if (backup[x][y] == '-') backup[x][y] = '+'; else backup[x][y] = '-'; } //按住当前位置 public static void turnAll(int i, int j) { for (int pos = 0; pos < 4; pos++) { turnOne(i, pos); turnOne(pos, j); } turnOne(i, j); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); //初始化 for (int i = 0; i < 4; i++) { String line = sc.next(); for (int j = 0; j < 4; j++) { arr[i][j] = line.charAt(j); } } //定义不同的方案数 for (int op = 0; op < 1 << 16; op++) { List<Pair<Integer, Integer>> list = new ArrayList<>(); //根据指定方案来进行推算 //备份一份状态 for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { backup[i][j] = arr[i][j]; } } //对backup来进行操作 for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { //当前方案该i，j位置需要进行按住 if ((op >> getPos(i, j) & 1) == 1) { turnAll(i, j); list.add(new Pair<Integer, Integer>(i, j)); } } } //最终进行check检查 boolean flag = true; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { if (backup[i][j] != '-') { flag = false; break; } } } //报错结果集 if (flag && (ansList == null || ansList.size() > list.size())) { ansList = list; } } //最终输出结果集 System.out.printf("%d\n", ansList.size()); for (int i = 0; i < ansList.size(); i++) { System.out.printf("%d %d\n", ansList.get(i).x + 1, ansList.get(i).y + 1); } } }
题目5：AcWing 1208.翻硬币【简单，蓝桥杯2013年B组第8题】
来源：第四届蓝桥杯省赛C++B组
标签：递推 视频讲解：2.1中 链接：1208. 翻硬币 分析：两大类做法：初始状态->目标状态。 可采用宽搜bfs，可使用时间复杂度比较高。只有状态数局面不大采用bfs。 若是局面特别大可采用其他做法。 把其想象为开关的做法【此类就是一个模拟的问题】 有解必然只有一组唯一解。（看起来最少需要多少步，实际上只有一组解） 若是一次翻转3或4次时，也同样可以使用上面的模拟解决了【前面一次能够推举出后面按的操作】。 10个字符，一次连续按两个，相当于9次，那么一个个依次去进行比较即可。 import java.util.*; class Main { public static void turn(int i) { from[i] = from[i] == '*' ? 'o' : '*'; } static char[] from; static char[] to; public static void main(String[] args) { Scanner cin = new Scanner(System.in); from = cin.next().toCharArray(); to = cin.next().toCharArray(); //n - 1步 int n = from.length; int ans = 0; for (int i = 0; i < n - 1; i++) { if (from[i] != to[i]) { //进行反转连续的两个 turn(i); turn(i + 1); ans++; } } System.out.printf("%d", ans); } }
二、递推
例题
题目1：AcWing 95.斐波那契【简单，递推写法】
题目链接：21. 斐波那契数列
class Solution { private int[] fn = new int[40]; //递推 public int Fibonacci(int n) { fn[1] = 1; fn[2] = 1; for (int i = 3; i <= n; i++) fn[i] = fn[i - 1] + fn[i - 2]; return fn[n]; } }
![【蓝桥杯】[递归]母牛的故事](https://ucc.alicdn.com/pic/developer-ecology/2is4p5rpji74e_be870067c97c42ca9083c25b149faaa5.png?x-oss-process=image/resize,h_160,m_lfit)