你玩过“拉灯”游戏吗?
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];}}}
}
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;}}
💡💡💡思路:
由于数据范围比较小,我们可以直接通过位运算进行二进制枚举,但是需要注意的是,借助二进制枚举的时候,我们只能枚举一维的,我们需要将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;}}
思路:从前往后,将问题规模不断缩小,并且保证对所有需要翻转的棋子,只需要翻转一次,使得我们的操作保证操作次数最小。
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);}
}
思路:直接递归实现选不选即可,注意需要回溯(即取消标记,恢复现场)
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);}}
}
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;}}}}
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);}}
}
上一篇:SQL刷题【基础篇】