今天练习的思维为递推。
AcWing3777.砖块
题目描述
\(n\) 个砖块排成一排，从左到右编号依次为 \(1∼n\)。
每个砖块要么是黑色的，要么是白色的。
现在你可以进行以下操作若干次（可以是 \(0\) 次）：
选择两个相邻的砖块，反转它们的颜色。（黑变白，白变黑）
你的目标是通过不超过 \(3n\) 次操作，将所有砖块的颜色变得一致。
输入格式
第一行包含整数 \(T\)，表示共有 \(T\) 组测试数据。
每组数据第一行包含一个整数 \(n\)。
第二行包含一个长度为 \(n\) 的字符串 \(s\)。其中的每个字符都是 W 或 B，如果第 \(i\) 个字符是 W，则表示第 \(i\) 号砖块是白色的，如果第 \(i\) 个字符是 B，则表示第 \(i\) 个砖块是黑色的。
输出格式
每组数据，如果无解则输出一行 \(−1\)。
否则，首先输出一行 \(k\)，表示需要的操作次数。
如果 \(k>0\)，则还需再输出一行 \(k\) 个整数，\(p_1,p_2,…,p_k\)。其中 \(p_i\) 表示第 \(i\) 次操作，选中的砖块为 \(p_i\) 和 \(p_{i+1}\) 号砖块。
如果方案不唯一，则输出任意合理方案即可。
数据范围
\(1≤T≤10 ，\)
\(2≤n≤200。\)
输入样例
4
8
BWWWWWWB
4
BWBB
5
WWWWW
3
BWB
输出样例
3
6 2 4
-1
0
2
2 1
解题思路
此题的结果，我们需要若干次操作将字符串变为全部由 B 组成的或者全部由 W 组成的。
那么我们进行两次转换，一次转换为全部由 B 组成的，另一次全部由 W 组成的。两次思路类似，我们封装为函数，实现一次即可。
假设，我们将该字符串全部变为 B。那么我们从前往后枚举，如果该处不为 B，我们进行一次转换，那么此过程我们最多转换 \(n-1\) 次(字符之间)，不会超过 \(3n\) 次，在此过程中，我们要保存操作的位置。最后，如果最后一个字符不为 B，则无法完成转换，即答案为 \(-1\)，因为我们一旦对其操作，倒数第二个字符就会变化，仍然不符合要求；否则，我们输出操作次数以及方案即可。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int T, n;
string str;
void update(char& c) // 操作对象为string使用&符号
{
if (c == 'W') c = 'B';
else c = 'W';
}
bool check(char c)
{
vector<int> res;
string s = str;
for (int i = 0; i + 1 < n; i ++)
{
if (s[i] != c)
{
update(s[i]);
update(s[i + 1]);
res.push_back(i);
}
}
if (s[n - 1] != s[0]) return false;
cout << res.size() << endl;
for (auto x: res)
cout << x + 1 << ' ';
if (res.size()) cout << endl;
return true;
}
int main()
{
cin >> T;
while (T --)
{
cin >> n >> str;
if (!check('B') && !check('W')) puts("-1");
}
return 0;
}
AcWing1208.翻硬币（蓝桥杯辅导课）
题目描述
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：**oo***oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式
一个整数，表示最小操作步数。
数据范围
输入字符串的长度均不超过 \(100\)。
数据保证答案一定有解。
输入样例1
**********
o****o****
输出样例1
5
输入样例2
*o**o***o***
*o***o**o***
输出样例2
1
解题思路
有了前面的题，相比这道题就比较简单了，思路是类似的。我们对一个字符串操作，如果两个字符串对应位置相同，无需操作，否则进行转换，统计一下操作数即可。
C++代码
#include <bits/stdc++.h>
using namespace std;
string a, b;
void update(char& c)
{
if (c == '*') c = 'o';
else c = '*';
}
int main()
{
cin >> a >> b;
int n = a.size();
int cnt = 0;
for (int i = 0; i < n - 1; i ++)
{
if (a[i] == b[i]) continue;
update(b[i]);
update(b[i + 1]);
cnt ++;
}
cout << cnt << endl;
return 0;
}
AcWing95.费解的开关（算法提高课）
题目描述
你玩过“拉灯”游戏吗？
\(25\) 盏灯排成一个 \(5×5\) 的方形。
每一个灯都有一个开关，游戏者可以改变它的状态。
每一步，游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 \(1\) 表示一盏开着的灯，用数字 \(0\) 表示关着的灯。
下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在 \(6\) 步以内使所有的灯都变亮。
输入格式
第一行输入正整数 \(n\)，代表数据中共有 \(n\) 个待解决的游戏初始状态。
以下若干行数据分为 \(n\) 组，每组数据有 \(5\) 行，每行 \(5\) 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式
一共输出 \(n\) 行数据，每行有一个小于等于 \(6\) 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若 \(6\) 步以内无法使所有灯变亮，则输出 \(−1\)。
数据范围
\(0<n≤500\)
输入样例
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
输出样例
3
2
-1
解题思路
这道题相当于前面两道题的二维拓展。我们这样操作，每次先枚举第一行的可能操作，一共 \(2^5\) 种情况。操作完第一行之后，第一行固定，我们还是看第一行，要将第一行中暗着的灯打开，那么我们就要对应的操作其下方也就是同列的第二行的那个开关，经过遍历，我们实现了第一行的打开。同理，我们实现第二、三、四行的打开。注意，我们仅剩第五行了，那么我们可以对第五行操作吗？答案显然是否定的，我们一旦对于第五操作，那么第四行的开关状态就会变化。因此，我们只需要判断第五行是否全部打开即可，若全部打开，则该方案可行，更新答案；否则，方案不可行。当我们遍历完全部方案，判断答案与 \(6\) 的关系即可。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 6;
int n;
char g[N][N], backup[N][N];
int dx[5] = {0, -1, 0, 1, 0}, dy[5] = {1, 0, -1, 0, 0};
void turn(int x, int y)
{
for (int i = 0; i < 5; i ++)
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;
g[a][b] ^= 1;
}
}
int main()
{
scanf("%d", &n);
while (n --)
{
for (int i = 0; i < 5; i ++) scanf("%s", g[i]);
int res = 10;
for (int op = 0; op < 1 << 5; op ++) // 枚举对第一行的操作
{
int step = 0;
memcpy(backup, g, sizeof g);
for (int j = 0; j < 5; j ++)
if (op >> j & 1)
{
turn(0, j);
step ++;
}
// 至此第一行固定
for (int i = 0; i < 4; i ++)
for (int j = 0; j < 5; j ++)
if (g[i][j] == '0')
{
turn(i + 1, j);
step ++;
}
bool flag = true;
for (int j = 0; j < 5; j ++)
if (g[4][j] == '0')
flag = false;
if (flag) res = min(res, step);
memcpy(g, backup, sizeof backup);
}
if (res > 6) puts("-1");
else printf("%d\n", res);
}
return 0;
}