F. Fix Flooded Floor - 题解
比赛与标签
比赛: 2024-2025 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred) 标签: constructive algorithms, dp, graphs 难度: *1700
喵~来康康题目说了什么
主人，晚上好呀！今天我们来帮伟大的科学家阿基米德解决一个地板漏水的小麻烦，喵~
事情是这样的：阿基米德的浴室地板是一个 2 x n 的长条形。因为他洗澡时太沉迷于科学思考，水漫了出来，损坏了一些地板（用 . 表示）。完好的部分用 # 表示。现在，他想用无限多的 1 x 2 的小木板把所有损坏的区域都铺好。
我们的任务就是判断一下铺地板的方案：
- 是不是只有 唯一 一种铺法？("Unique")
- 是不是有 多种 铺法？("Multiple")
- 还是根本就 没有 办法铺好？("None")
输入会告诉我们 n 的大小和两行表示地板状况的字符串。我们要对每个测试用例给出对应的答案，呐。
猫猫的思考时间~
一看到这种在狭长网格上铺东西的问题，猫猫的DNA就动了！这不就是经典的 轮廓线DP (Profile DP) 嘛，喵~ 它的核心思想就是一列一列地处理，只记录下当前列与前一列之间的“交界线”状态。
状态要怎么表示呢？
对于第 i 列，我们需要知道哪些信息才能推导出第 i+1 列的情况呢？其实，我们只需要关心一件事：第 i 列的两个格子，是否已经被从第 i-1 列伸过来的横向木板给占据了。
这个“交界线”的状态只有两个格子，所以我们可以用一个 2 位的二进制数 m 来表示，非常方便！
m的第 0 位（最右边的位）代表第 0 行（上面那行）的格子状态。m的第 1 位代表第 1 行（下面那行）的格子状态。
1 表示这个格子已经被左边伸过来的木板覆盖了，0 表示没有。 这样，我们就有 4 种可能的状态 m：
m = 0(二进制00): 第i列的两个格子都没有被左边的木板覆盖。m = 1(二进制01): 第i列上面的格子被覆盖了。m = 2(二进制10): 第i列下面的格子被覆盖了。m = 3(二进制11): 第i列的两个格子都被覆盖了。
DP数组的含义
我们定义 dp[m] 表示，在处理完第 i-1 列后，使得第 i 列处于状态 m 的铺法有多少种。 但是题目不要求我们计算具体的方案数，只需要知道是 0, 1, 还是大于1。所以我们可以用一个技巧：
dp[m] = 0: 表示没有方案可以达到这个状态。dp[m] = 1: 表示有且仅有 1 种方案可以达到这个状态。dp[m] = 2: 表示有超过 1 种方案（即多种方案）可以达到这个状态。
之后所有的加法都变成 min(2, a + b)，这样就不会溢出，也满足了我们的需求，是不是很聪明呀~
状态转移，一步一步来解决喵！
我们从左到右，一列一列地（从 i = 0 到 n-1）进行状态转移。假设我们正在处理第 i 列，并且已经知道了到达第 i 列各种状态 m 的方案数 dp[m]。我们的目标是计算出 next_dp，也就是到达第 i+1 列各种状态的方案数。
对于第 i 列，我们先看看哪些格子是空的（.）并且需要我们来铺的。一个格子 (row, i) 需要被铺，当且仅当它本身是 . 并且没有被 i-1 列伸过来的木板覆盖。
我们来分析所有情况：
两个格子都需要铺 (
.且未被覆盖)- 方案A (竖着铺): 我们可以用一个
1x2的木板竖着放在第i列，正好把两个都盖住。这样，没有木板伸到第i+1列，所以下一列的状态是0。我们将dp[m]的方案数累加到next_dp[0]。 - 方案B (横着铺): 我们可以用两个
1x2的木板横着铺，分别占据(0,i)-(0,i+1)和(1,i)-(1,i+1)。这要求第i+1列的两个格子也都是.才行。这样，第i+1列的两个格子都被来自第i列的木板覆盖了，下一列的状态是3。我们将dp[m]累加到next_dp[3]。 - 如果两种方案都可行，那么方案数就可能变多啦！
- 方案A (竖着铺): 我们可以用一个
只有上面那个格子需要铺
- 唯一的办法就是横着铺一个木板，占据
(0,i)-(0,i+1)。这要求(0,i+1)也得是.。这样，下一列的状态就是1（上面被覆盖，下面没被覆盖）。我们将dp[m]累加到next_dp[1]。
- 唯一的办法就是横着铺一个木板，占据
只有下面那个格子需要铺
- 和上面类似，横着铺一个木板占据
(1,i)-(1,i+1)。要求(1,i+1)是.。下一列的状态是2。我们将dp[m]累加到next_dp[2]。
- 和上面类似，横着铺一个木板占据
两个格子都不需要铺
- 这说明它们要么是墙壁
#，要么已经被左边伸过来的木板盖住了。我们什么都不用做，也没有木板伸到下一列。所以下一列的状态是0。我们将dp[m]累加到next_dp[0]。
- 这说明它们要么是墙壁
初始化和最终答案
- 初始状态: 在处理第 0 列之前，我们可以看作是在一个虚拟的-1列的右边。这里什么都没有，所以到达第 0 列的状态
m=0的方案数是 1（就是什么都不做的“无为”之法），其他状态都是 0。所以dp[0]=1, dp[1]=dp[2]=dp[3]=0。 - 最终答案: 当我们处理完所有
n列后，一个合法的铺法必须保证没有木板伸出边界。也就是说，在第n-1列之后，状态必须是0。所以我们最后只需要检查dp[0]的值：dp[0] == 0-> "None"dp[0] == 1-> "Unique"dp[0] == 2-> "Multiple"
好啦，思路就是这样！让我们看看代码怎么实现吧，喵~
代码时间到!
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main() {
// 优化输入输出速度，让程序跑得更快喵~
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
string s0, s1;
cin >> s0 >> s1;
// dp[m] 存储方案数（0, 1, 或 2(表示>=2)），m是轮廓线状态
// m=0 (00): 上下都未被覆盖
// m=1 (01): 上方被覆盖
// m=2 (10): 下方被覆盖
// m=3 (11): 上下都被覆盖
vector<int> dp(4, 0);
// 初始状态：在第0列前，唯一的方式是“什么都不铺”，所以状态0有1种方案
dp[0] = 1;
// 从左到右，一列一列地处理
for (int i = 0; i < n; i++) {
vector<int> next_dp(4, 0); // 用来存储处理完第i列后的新状态
for (int m = 0; m < 4; m++) {
if (dp[m] == 0) continue; // 如果这个状态本来就无法达到，就跳过
// 检查当前状态m是否与地图冲突
// 如果状态m要求上方格子被覆盖，但该格子是'#'，则此路不通
if (m & 1) {
if (s0[i] != '.') continue;
}
// 如果状态m要求下方格子被覆盖，但该格子是'#'，则此路不通
if (m & 2) {
if (s1[i] != '.') continue;
}
// 判断第i列的两个格子是否是空的 '.'
bool a0 = (s0[i] == '.');
bool a1 = (s1[i] == '.');
// 判断第i列的两个格子是否已经被左边伸过来的方块覆盖了
bool covered0 = (m & 1);
bool covered1 = (m & 2);
// 判断第i列的两个格子是否需要被新的方块覆盖
bool need0 = a0 && !covered0;
bool need1 = a1 && !covered1;
if (need0 && need1) {
// 情况1：上下两个格子都需要覆盖
// 方案A: 竖着放一个1x2方块，不影响下一列。下一列状态为0
next_dp[0] = min(2, next_dp[0] + dp[m]);
// 方案B: 横着放两个1x2方块，这要求下一列的两个格子也是'.'
if (i + 1 < n && s0[i+1] == '.' && s1[i+1] == '.') {
// 这样下一列的两个格子都被覆盖，状态为3
next_dp[3] = min(2, next_dp[3] + dp[m]);
}
} else if (need0) {
// 情况2：只有上面格子需要覆盖
// 只能横着放，覆盖 (0,i) 和 (0,i+1)
if (i + 1 < n && s0[i+1] == '.') {
// 下一列上方被覆盖，状态为1
next_dp[1] = min(2, next_dp[1] + dp[m]);
}
} else if (need1) {
// 情况3：只有下面格子需要覆盖
// 只能横着放，覆盖 (1,i) 和 (1,i+1)
if (i + 1 < n && s1[i+1] == '.') {
// 下一列下方被覆盖，状态为2
next_dp[2] = min(2, next_dp[2] + dp[m]);
}
} else {
// 情况4：两个格子都不需要覆盖（要么是'#'，要么已被覆盖）
// 直接进入下一列，下一列状态为0
next_dp[0] = min(2, next_dp[0] + dp[m]);
}
}
dp = move(next_dp); // 更新dp数组，准备处理下一列
}
// 最终，所有格子都铺满且没有方块伸出边界，意味着最终状态必须是0
if (dp[0] == 0) {
cout << "None\n";
} else if (dp[0] == 1) {
cout << "Unique\n";
} else {
cout << "Multiple\n";
}
}
return 0;
}跑得快不快呀?
- 时间复杂度: O(N) 的说。我们对
n列中的每一列都进行一次遍历。在每一列中，我们只对固定的 4 种状态进行常数次操作。所以总的时间复杂度和n是线性的，超级快！ - 空间复杂度: O(1) 的说。我们只用了两个大小为 4 的
dp数组来回滚动更新，所以使用的空间是常数级别的，和n的大小无关，非常节省内存呢！
这次学到了什么喵?
这道题是一个非常标准的 轮廓线动态规划 入门题，教会了我们一些很棒的技巧，喵~
- 轮廓线DP思想: 解决网格问题的利器！通过逐行或逐列推进，只记录交界处的少量状态信息，从而将二维问题化为线性递推。
- 状态压缩: 用一个简单的整数（二进制位）来表示复杂的组合状态，是DP中非常常见的优化手段。这里用2个bit表示2个格子的状态，简洁又高效。
- 方案数统计技巧: 当题目只关心方案数是0、1还是大于1时，使用
min(2, ...)的方法可以避免处理大数，简化代码逻辑，还能防止溢出，一举三得！ - 问题分解: 把一个复杂铺砖问题，分解成在每一列处理 "需要铺0/1/2个格子" 的几种简单情况，让思路变得非常清晰。
希望这篇题解能帮助到你，如果还有不明白的地方，随时可以再来问猫猫哦！一起加油，变得更强吧！喵~ >w<