蓝桥杯有参加蓝桥杯的同学可以给博主点个关注，博主也在准备蓝桥杯，可以跟着博主的博客一起刷题。
我的AcWing
题目及图片来自蓝桥杯C++ AB组辅导课
递推递归和递推的区别
递归可以理解为把原问题分解成若干个同类子问题求解。
递推就是先求子问题，然后用子问题推原问题。
我们可以根据斐波那契这个公式来理解：
递归的话就是先想f(n)怎么做，然后我们发现f(n) = f(n - 1) + f(n - 2)，当我们定义一个函数f(n)的时候，只需要返回两个 f(n - 1) + f(n - 2)子问题就可以了。
递推的写法就是，我先算出来f(n - 1) + f(n - 2)，然后再算f(n)，从前往后1~n开始算，一项一项算，然后用数组存下，从前往后递推一遍。
例题 AcWing 717.简单斐波那契递推写法
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] f = new int[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++) System.out.print(f[i] + " ");
}
}
优化写法
dp滚动数组的雏形
还是递推写法，但是优化跟递推无关
我们可以发现，每一项只跟前两项有关系，因此我们可以省点空间，不开数组，直接开变量就可以，每次只记录前两项是多少。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a = 0, b = 1;
for (int i = 1; i <= n; i++) {
System.out.print(a + " ");
int fn = a + b;
a = b;
b = fn;
}
}
}
AcWing 95. 费解的开关
将所有灯变亮 也就是所有数字变为1
我们以输入的第二个5x5的数为例：
11101 11101 11110 11111 11111
怎么把所有灯变亮呢？
我们可以先灭掉（2,5），然后再涂右上角的就可以，两步完成，所以输出2。
灭掉（2,5），（2,4）（3,5）亮，（1,5）灭
此时的5x5数字为
11100 11110 11111 11111 11111
再将（1,5）也就是右上角点亮，（1,4）（2,5）亮，所有数字全亮。
此时数字为
11111 11111 11111 11111 11111
符合题目要求，两步完成，输出2。
思想：
每一行开关的操作完全被上一行灯的亮灭状态所唯一确定
我们只需要枚举第一行的操作，之后所有的操作都可以根据上一行的亮灭来进行操作； 第二行的操作完全取决于第一行，第一行操作完改变了第一行的状态，第一行的状态决定了第二行的操作，假如第一行操作完之后还有灭的，因为第一行不能操作了，所以我们只能按第二行来使第一行的灯全亮，同理，第三行的操作完全取决于第二行，以此类推。
顺序可以任意，每个格子最多按一次。
所以解法就是枚举第一行，之后的所有操作就都确定了。
最后一行的状态不能改了，需要特判一下，如果有灭着的说明方案不合法，如果全亮说明方案ok。
import java.util.Scanner;
public class Main {
static final int N = 6;
static char[][] g = new char[N][N];
static char[][] backup = new char[N][N]; // 备份数组
static int[] dx = {-1, 0, 1, 0, 0}; // 坐标x的偏移量
static int[] dy = {0, 1, 0, -1, 0}; // 坐标y的偏移量
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while (n-- != 0) {
for (int i = 0; i < 5; i++) g[i] = sc.next().toCharArray();
int res = Integer.MAX_VALUE;
for (int op = 0; op < 32; op++) { // 5位数 转换成2进制最大的数是32
for (int i = 0; i < 5; i++) {
backup[i] = g[i].clone();
}
int step = 0;
// 对第一行状态的判断
for (int i = 0; i < 5; i++) {
if ((op >> i & 1) == 0) { // 判断i的二进制的第几位是不是1
step++;
turn(0, 4 - i);
}
}
// 对2,3,4行判断
for (int i = 0; i < 4; i++){
for (int j = 0; j < 5; j++){
if (g[i][j] == '0') {
step++;
turn(i + 1, j);
}
}
}
boolean dark = false;
// 对最后一行特判
for (int i = 0; i < 5; i++) {
if (g[4][i] == '0') {
dark = true;
break;
}
}
if (!dark) res = Math.min(res, step);
for (int i = 0; i < 5; i++) {
g[i] = backup[i].clone();
}
}
if (res > 6) res = -1;
System.out.println(res);
}
}
// 利用偏移量改变5个位置的值
private static void turn(int x, int y) {
for (int i = 0; i < 5; i++) {
int a = x + dx[i];
int b = y + dy[i];
if (a < 0 || a >= 5 || b < 0 || b >= 5) continue; // 在边界外，直接忽略即可
g[a][b] ^= 1; // 异或运算
}
}
}
AcWing 116. 飞行员兄弟
-+-- ---- ---- -+--
目的：将所有+号变成-号
假设切换一下图中圈红的位置，这个绿色的部分就会变成下图所示，它所处的行和列都会变化。
我们发现这个题是很难递推出来的，它跟上一题开关问题不一样，上一题是每一次只会有一个开关能影响灯泡，但是这题是每一个开关可以被很多个开关控制，这一个开关的状态并不会影响到其余开关的操作，因此我们不能用递推的方法来解决这道题。
本题是为了区分上一题，不要固定思想！！这道题没法用递推来解决咱们就直接暴力搜索所有方案。
思想：
枚举所有方案 0~2^16 - 1
按照该方案对所有开关进行操作
判断 => 记录方案
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Main {
static final int N = 5;
static char[][] g = new char[N][N];
static char[][] backup = new char[N][N]; // 备份数组
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws Exception {
for (int i = 0; i < 4; i++) g[i] = in.readLine().toCharArray();
List res = new ArrayList<>();
for (int op = 0; op < 1 << 16; op++) { // 1 << 16 同等于2^16
List temp = new ArrayList<>();
for (int i = 0; i < 4; i++) {
backup[i] = g[i].clone(); // 备份
}
// 进行操作
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if ((op >> get(i, j) & 1) == 1) {
temp.add(new PII(i, j));
turn_all(i, j);
}
}
}
// 判断所有灯泡是否全亮
boolean has_closed = false;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (g[i][j] == '+') has_closed = true;
}
}
if (has_closed == false) {
if (res.isEmpty() || res.size() > temp.size()) res = temp;
}
for (int i = 0; i < 4; i++) {
g[i] = backup[i].clone(); // 还原
}
}
System.out.println(res.size());
for (PII p : res) System.out.println((p.x + 1) + " " + (p.y + 1));
in.close();
}
private static 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);
}
private static void turn_one(int x, int y) {
if (g[x][y] == '+') g[x][y] = '-';
else g[x][y] = '+';
}
private static int get(int x, int y) {
return 4 * x + y;
}
static class PII {
int x;
int y;
public PII (int x, int y) {
this.x = x;
this.y = y;
}
}
}
第四届2013年蓝桥杯真题
AcWing 1208. 翻硬币
C++B组第8题
翻动相邻的两个硬币
输入样例1:
********** // 初始状态 o****o**** // 要达到的目标状态
操作
// 第一步操作 oo******** o****o**** // 第二步操作 o*o******* o****o**** // 第三步操作 o**o****** o****o**** // 第四步操作 o***o***** o****o**** // 第五步操作 o****o**** o****o****
输出样例1
5
这个题其实就是上面费解的开关简化版，能操控灯泡的状态只有一个开关，能操控硬币的正反也只有一个开关，想象两个硬币中有一个开关可以控制两个硬币的正反，绿色的线就是我们的开关。
因为第一个硬币对应的正反就不一样，所以第一个开关我们必须按下，变成下图这样：
第二个开关同理，对比我们想要达到的状态，第二个开关也必须要按，如下图：
以此类推，当我们对比到第6个硬币的时候，发现是一样的，所以第6个开关就一定不能按，之后所有耳朵开关也都不能按。
每个开关按不按的状态是唯一确定的，题中说没有无解的情况，所以这道题必然是只有一种解；一般来说这种问步数的题都是一个优化问题，从所有的解法里找一个最优解，这题看起来是找最小操作步数，但其实我们发现它如果有解的话它只有一种解。
我们只需要把这个问题递推一遍就可以了。
import java.util.Scanner;
public class Main {
static final int N = 101;
static char[] s1 = new char[N];
static char[] s2 = new char[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
s1 = sc.next().toCharArray();
s2 = sc.next().toCharArray();
int res = 0;
for (int i = 0; i < s1.length - 1; i++) {
if (s1[i] != s2[i]) {
turn(i);
turn(i + 1);
res++;
}
}
System.out.print(res);
}
private static void turn(int i) {
if (s1[i] == '*') s1[i] ='o';
else s1[i] = '*';
}
}
有对代码不理解的地方可以在下方评论
