递推
1.砖块
3777. 砖块 - AcWing题库
n个砖块排成一排，从左到右编号依次为 1∼n。
每个砖块要么是黑色的，要么是白色的。
现在你可以进行以下操作若干次（可以是 00 次）：
选择两个相邻的砖块，反转它们的颜色。（黑变白，白变黑）
你的目标是通过不超过 3n 次操作，将所有砖块的颜色变得一致。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含一个整数 n。
第二行包含一个长度为 n的字符串 s。其中的每个字符都是 W 或 B，如果第 i个字符是 W，则表示第 i号砖块是白色的，如果第 i 个字符是 B，则表示第 i 个砖块是黑色的。
输出格式
每组数据，如果无解则输出一行 −1−1。
否则，首先输出一行 k，表示需要的操作次数。
如果 k>0，则还需再输出一行 k 个整数，p1,p2,…,pk。其中 pi 表示第 i 次操作，选中的砖块为 pi和 pi+1 号砖块。
如果方案不唯一，则输出任意合理方案即可。
数据范围
1≤T≤10
2≤n≤200
输入样例：
1
2
3
4
5
6
7
8
9
| 4
8
BWWWWWWB
4
BWBB
5
WWWWW
3
BWB
|
输出样例：
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(in.readLine());
while (T-- > 0) {
int n = Integer.parseInt(in.readLine());
String s = in.readLine();
fun(n, s.toCharArray());
}
}
private static void fun(int n, char[] chars) {
StringBuffer sb = new StringBuffer();
int t = 0;
for (int i = 0; i < chars.length - 1; i++) {
if (chars[i] != 'W') {
t++;
sb.append(i + 1);
sb.append(" ");
chars[i] = chars[i] == 'W' ? 'B' : 'W';
chars[i + 1] = chars[i + 1] == 'W' ? 'B' : 'W';
}
}
if (chars[chars.length - 1] == 'W') {
if (t == 0) {
System.out.println(0);
return;
}
sb.deleteCharAt(sb.length() - 1);
System.out.println(t);
System.out.println(sb.toString());
return;
}
for (int i = 0; i < chars.length - 1; i++) {
if (chars[i] != 'B') {
t++;
sb.append(i + 1);
sb.append(" ");
chars[i] = chars[i] == 'W' ? 'B' : 'W';
chars[i + 1] = chars[i + 1] == 'W' ? 'B' : 'W';
}
}
if (chars[chars.length - 1] == 'B') {
if (t == 0) {
System.out.println(0);
return;
}
sb.deleteCharAt(sb.length() - 1);
System.out.println(t);
System.out.println(sb.toString());
return;
}
System.out.println(-1);
}
}
|
2.斐波那契
717. 简单斐波那契 - AcWing题库
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(in.readLine());
int a = 0;
int b = 1;
while (n-- > 0) {
sb.append(a);
sb.append(" ");
int t = b;
b = a + t;
a = t;
}
System.out.println(sb.toString());
}
}
|
3.费解的开关
95. 费解的开关 - AcWing题库
你玩过“拉灯”游戏吗？
2525 盏灯排成一个 5×55×5 的方形。
每一个灯都有一个开关，游戏者可以改变它的状态。
每一步，游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 11 表示一盏开着的灯，用数字 00 表示关着的灯。
下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在 66 步以内使所有的灯都变亮。
输入格式
第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。
以下若干行数据分为 n 组，每组数据有 55 行，每行 55 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式
一共输出 n 行数据，每行有一个小于等于 66 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若 66 步以内无法使所有灯变亮，则输出 −1−1。
数据范围
0<n≤500
输入样例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
|
输出样例：
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
while (n-- > 0) {
int[][] nums = new int[5][5];
for (int i = 0; i < nums.length; i++) {
String s = in.readLine();
for (int j = 0; j < s.length(); j++) {
nums[i][j] = s.charAt(j) - '0';
}
}
fun(nums);
in.readLine();
}
}
private static void fun(int[][] nums) {
int res = 10;
for (int i = 0; i <= 31; i++) {
int t = 0;
int[][] ints = copyOf(nums);
for (int j = 0; j < 5; j++) {
if (((i >> j) & 1) == 1) {
t++;
change(ints, 0, j);
}
}
int temp = make(ints);
if (temp != -1) {
res = res == -1 ? temp + t : Math.min(temp + t, res);
}
}
if (res > 6) {
System.out.println(-1);
} else {
System.out.println(res);
}
}
private static int[][] copyOf(int[][] nums) {
int[][] res = new int[5][5];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
res[i][j] = nums[i][j];
}
}
return res;
}
private static int make(int[][] ints) {
int t = 0;
for (int i = 1; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (ints[i - 1][j] == 0) {
change(ints, i, j);
t++;
}
}
}
for (int i = 0; i < 5; i++) {
if (ints[4][i] == 0) {
return -1;
}
}
return t;
}
private static void change(int[][] ints, int i, int j) {
if (j > 0) {
ints[i][j - 1] = 1 - ints[i][j - 1];
}
ints[i][j] = 1 - ints[i][j];
if (j < 4) {
ints[i][j + 1] = 1 - ints[i][j + 1];
}
if (i > 0) {
ints[i - 1][j] = 1 - ints[i - 1][j];
}
if (i < 4) {
ints[i + 1][j] = 1 - ints[i + 1][j];
}
}
}
|
4.飞行员兄弟
116. 飞行员兄弟 - AcWing题库
“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 1616 个把手的冰箱。
已知每个把手可以处于以下两种状态之一：打开或关闭。
只有当所有把手都打开时，冰箱才会打开。
把手可以表示为一个 4×44×4 的矩阵，您可以改变任何一个位置 [i,j]上把手的状态。
但是，这也会使得第 i 行和第 j 列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式
输入一共包含四行，每行包含四个把手的初始状态。
符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式
第一行输出一个整数 N，表示所需的最小切换把手次数。
接下来 N 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。
注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
数据范围
1≤i,j≤4
输入样例：
输出样例：
1
2
3
4
5
6
7
| 6
1 1
1 3
1 4
4 1
4 3
4 4
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int[][] nums = new int[4][4];
for (int i = 0; i < nums.length; i++) {
String s = in.readLine();
for (int j = 0; j < s.length(); j++) {
if (s.charAt(j) == '+') {
nums[i][j] = 0;
} else {
nums[i][j] = 1;
}
}
}
fun(nums);
}
private static void fun(int[][] nums) {
int res = 0;
int min = 20;
for (int i = 0; i < (1 << 16); i++) {
int[][] ints = copyOf(nums);
int t = 0;
for (int j = 0; j < 16; j++) {
if (((i >> j) & 1) == 1) {
change(ints, j / 4, j % 4);
t++;
}
}
if (check(ints)) {
if (min > t) {
min = t;
res = i;
}
}
}
System.out.println(min);
for (int j = 0; j < 16; j++) {
if (((res >> j) & 1) == 1) {
int r = j / 4;
int l = j % 4;
System.out.println((r + 1) + " " + (l + 1));
}
}
}
private static boolean check(int[][] ints) {
for (int i = 0; i < ints.length; i++) {
for (int j = 0; j < ints[i].length; j++) {
if (ints[i][j] == 0) {
return false;
}
}
}
return true;
}
private static void change(int[][] ints, int i, int j) {
for (int k = 0; k < 4; k++) {
ints[i][k] = 1 - ints[i][k];
}
for (int k = 0; k < 4; k++) {
ints[k][j] = 1 - ints[k][j];
}
ints[i][j] = 1 - ints[i][j];
}
private static int[][] copyOf(int[][] nums) {
int[][] res = new int[4][4];
for (int i = 0; i < 4; i++) {
System.arraycopy(nums[i], 0, res[i], 0, 4);
}
return res;
}
}
|
5.翻硬币
1208. 翻硬币 - AcWing题库
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：**oo***oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式
一个整数，表示最小操作步数
数据范围
输入字符串的长度均不超过100。  
数据保证答案一定有解。
输入样例：
输出样例：
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
char[] origin = in.readLine().toCharArray();
char[] target = in.readLine().toCharArray();
int t = 0;
for (int i = 0; i < origin.length - 1; i++) {
if (origin[i] != target[i]) {
change(origin, i);
t++;
}
}
System.out.println(t);
}
private static void change(char[] origin, int i) {
origin[i] = origin[i] == '*' ? 'o' : '*';
origin[i + 1] = origin[i + 1] == '*' ? 'o' : '*';
}
}
|
