文章目录

• • 1.费解的开关（递推、位运算）
  • 2.带分数（全排序/递归👍）
  • 3.飞行员兄弟（位运算）
  • 4.翻硬币（贪心/递推❓）
  • 5.递归实现指数型枚举
  • 6.递归实现排列行枚举
  • 7.递归实现组合型枚举

1.费解的开关（递推、位运算）

你玩过“拉灯”游戏吗？

25 盏灯排成一个 5×5 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。
下面这种状态

10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：

01111
11101
10111
11011
再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6
步以内使所有的灯都变亮。
数据范围
0

💡思路：
目标是将所有的数都变为1，当上一行的状态确定时，若上一行存在0，那么我们只能通过操作0去影响上一行的0.
(1)只要第一行的状态确定了，那么所有开关的状态就可以确定了，（显然我们直到下一行去改上一行，为什么还要枚举第一行的开关状态呢，其实是为了找到尽可能小的答案，我们把第一行的按法枚举一遍，每个位置都有两种选择，按(1)或者不按(0)，遍历这32情况，然后取最小值 ）
实现：

（1）只要第0行开关的状态确定，那么所有情况我们都可以推出来，因此枚举第一行操作的所有情况，总有32种情况,
（2）从第0行递推出第1到第4行的状态，若当前行状态已确定，且存在一个开关是0状态，则需要下一行的位置对开关进行切换，影响当前行开关是0的状态
（3）最后枚举最后一行，若该状态全部是1，则表示这种情况是可以的，更新最小步数

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int n = 0;static int dx[] = {-1, 0, 1, 0, 0};static int dy[] = {0, 1, 0, -1, 0};static int[][]a = new int[10][10];static int[][]ca = new int[10][10];static int minn = 10;public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());while(n-- > 0) {minn = 10;for(int i = 0; i < 5; i++) {String line = br.readLine();for(int j = 0; j < 5; j++) {a[i][j] = line.charAt(j) - '0';ca[i][j] = a[i][j];}}if(n >= 1) {String blank = br.readLine();}for(int i = 0; i < (1 << 5); i++) {int step = 0;copy();for(int j = 0; j < 5; j++) {if(((i >> j) & 1) == 1) { //1代表按step++;turn(0,j); //改变(x,y)及其周围的}}for(int x = 0; x < 4; x++) {for(int y = 0; y < 5; y++) {if(a[x][y] == 0) {step++;turn(x + 1, y);}}}boolean ok = true;for(int j = 0; j < 5; j++) {if(a[4][j] == 0) {ok = false;break;}}if(ok) {minn = Math.min(minn,step);}}if(minn > 6) {out.println(-1);}else {out.println(minn);}out.flush();}}private static void turn(int x, int y) {for(int k = 0; k < 5; k++) {int nx = x + dx[k];int ny = y + dy[k];if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) {continue;}else {a[nx][ny] ^= 1;}}}private static void copy() {for(int i = 0; i < 5; i++) {for(int j = 0; j < 5; j++) {a[i][j] = ca[i][j];}}}
}

2.带分数（全排序/递归👍）

100 可以表示为带分数的形式：100=3+69258/714
还可以表示为：100=82+3546/197
注意特征：带分数中，数字 1∼9分别出现且只出现一次（不包含 0 ）。
类似这样的带分数，100 有 11 种表示法。

输入格式：
一个正整数。

输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
（N<1e6）

💡思路：

只能说很巧妙，想到了其实很简单，想不到就没…
很显然，他说1-9种的数字每个数只能出现且只出现一次，我们可以枚举1-9的全排列，并用数组存下来每一位，对于每一种情况，为了表示此表达式的三部分，我们将全排列，通过i和j两个变量分为三段，然后计算是否满足给定的表达式即可（❗❗❗注意除法：防止出现小数，我们将其变为乘法，这种做法我们经常会用到）

//全排列实现关键代码（经常使用）for(int i = 1; i <= 9; i++) {if(!vis[i]) {vis[i] = true;perm[u] = i;dfs(u + 1);vis[i] = false;}}

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int n = 0,ans = 0;static int[] perm = new int[20];static boolean[] vis = new boolean[20];public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());dfs(1);System.out.println(ans);}private static void dfs(int u) {if(u == 10) {for(int i = 1; i < 8;i++) {for(int j = i + 1; j < 9; j++) {int a = cal(1,i);int b = cal(i + 1,j);int c = cal(j + 1,9);if(a*c + b == n*c) {ans++;}}}return;}for(int i = 1; i <= 9; i++) {if(!vis[i]) {vis[i] = true;perm[u] = i;dfs(u + 1);vis[i] = false;}}}private static int cal(int l, int r) {int res = 0;for(int i = l; i <= r; i++) {res = res * 10 + perm[i];}return res;}}

3.飞行员兄弟（位运算）

💡💡💡思路：
由于数据范围比较小，我们可以直接通过位运算进行二进制枚举，但是需要注意的是，借助二进制枚举的时候，我们只能枚举一维的，我们需要将0-15共16个位置映射到二维坐标（一般映射的时候，xy坐标从0开始比较方便映射），然后枚举所有答案，取得最小的值进行输出。
❗需要注意的是：
每次进行新的状态枚举的时候，我们需要从初始状态开始，所以一定不用忘记数组的拷贝和相关变量的初始化。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int n = 0,ans = 0,step = 0,minn = 0x3f3f3f3f;static String path = "",p = "";static int[] perm = new int[20];static boolean[][] vis = new boolean[10][10];static boolean[][] vis1 = new boolean[10][10];static int[][] a = new int[10][10];static int[][] ca = new int[10][10];public static void main(String[] args) throws Exception{for(int i = 0; i < 4; i++) {String str = br.readLine();for(int j = 0; j < 4; j++) {char ch = str.charAt(j);if(ch == '-') {a[i][j] = 0; //打开状态是0}else {a[i][j] = 1;}ca[i][j] = a[i][j];}}dfs();}private static void dfs() {for(int m = 0; m < (1 << 16); m++) {p = ""; step = 0;copy(a,ca);for(int i = 0; i < 16; i++) {  //将1代表需要操作，0代表不操作if(((m >> i) &1) == 1) { int x = i/4;int y = i%4;turn(x,y);p += (x + 1); p += (y + 1);step++;}}boolean ok = true;for(int i = 0; i < 4; i++) {for(int j = 0; j < 4; j++) {if(a[i][j] == 1) {ok = false;break;}}}if(ok) {if(step < minn) {minn = step;path = p;}}}System.out.println(minn);for(int i = 0; i < path.length();i++) {System.out.println(path.charAt(i) + " " + path.charAt(i + 1));i += 1;}}private static void copy(int[][] a, int[][] ca) {for(int i = 0; i < 4; i++) {for(int j = 0; j < 4; j++) {a[i][j] = ca[i][j];}}}private static void turn(int x, int y) {for(int i = 0; i < 4; i++) {a[i][y] ^= 1; }for(int i = 0; i < 4; i++) {a[x][i] ^= 1;}a[x][y] ^= 1;}}

4.翻硬币（贪心/递推❓）

思路：从前往后，将问题规模不断缩小，并且保证对所有需要翻转的棋子，只需要翻转一次，使得我们的操作保证操作次数最小。

ACcode:

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int n = 0,ans = 0;public static void main(String[] args) throws Exception{String str1 = "";String str2 = "";str1 = br.readLine();str2 = br.readLine();char[]s1 = str1.toCharArray();char[]s2 = str2.toCharArray();for(int i = 0; i < s1.length - 1; i++) {if(s1[i] != s2[i]) {ans++;if(s1[i] == '*') {s1[i] = 'o';}else {s1[i] = '*';}if(s1[i + 1] == '*') {s1[i + 1] = 'o';}else {s1[i + 1] = '*';}}}System.out.println(ans);}
}

5.递归实现指数型枚举

思路：直接递归实现选不选即可，注意需要回溯（即取消标记，恢复现场）

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 20;static int n = 0,m = 0,ans = 0;static int[] a = new int[N];static boolean vis[] = new boolean[N];public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());dfs(1);}private static void dfs(int u) {if(u == n + 1) {for(int i = 1; i <= n; i++) {if(vis[i]) {System.out.print(i + " ");				}}System.out.println();return;}vis[u] = false;dfs(u + 1);vis[u] = true;dfs(u + 1);}
}

方法二：记住上次的结束，下次直接从后面开始

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 20;static int n = 0,m = 0,ans = 0, k = 0;static int[] a = new int[N];static int pos[] = new int[N];public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());k = Integer.parseInt(br.readLine());dfs(1,0);}private static void dfs(int u,int pre) {if(u == k + 1) {for(int i = 1; i <= k; i++) {System.out.print(pos[i] + " ");}System.out.println();return;}for(int i = pre + 1; i <= n; i++) {pos[u] = i;dfs(u + 1,i);}}
}

6.递归实现排列行枚举

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 20;static int n = 0,m = 0,ans = 0;static int[] a = new int[N];static boolean vis[] = new boolean[N];public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());dfs(1);}private static void dfs(int u) {if(u == n + 1) {for(int i = 1; i <= n; i++) {System.out.print(a[i] + " ");}System.out.println();return;}for(int i = 1; i <= n; i++) {if(!vis[i]) {vis[i] = true;a[u] = i;dfs(u + 1);vis[i] = false;}}}}

7.递归实现组合型枚举

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 30;static int n = 0,m = 0,ans = 0, k = 0;static int[] a = new int[N];static int pos[] = new int[N];public static void main(String[] args) throws Exception{String[]nm = br.readLine().split(" ");n = Integer.parseInt(nm[0]);k = Integer.parseInt(nm[1]);dfs(1,0);}private static void dfs(int u,int pre) {if(u == k + 1) {for(int i = 1; i <= k; i++) {System.out.print(pos[i] + " ");}System.out.println();return;}for(int i = pre + 1; i <= n; i++) {pos[u] = i;dfs(u + 1,i);}}
}