题解：P12097 [NERC2024] Fix Flooded Floor

这个人居然还活着！

~~什么黄题，绿题还差不多。~~

由于 $n$ 非常大，所以要用 $O(n\log n)$ 或者 $O(n)$ 级别的时间复杂度。

所以这个题使用 DP。

# 状态设计
$dp[i][mask]$ 表示处理到第 $i$ 列时，第 $i$ 列被覆盖情况的方案数，其中 $mask$ 是一个2位的二进制数：

- 第 $0$ 位：表示**第二行**是否被一个从左边来的横放骨牌覆盖。
- 第 $1$ 位：表示**第一行**是否被一个从左边来的横放骨牌覆盖。

# 状态转移
对于每一列：
1. 当前列的格子状态：哪些格子需要覆盖（坏的地板 `.`）
2. 从左边横放过来的影响（即当前 $mask$）
3. 当前列可能采取的放置方式

考虑：

## 当前列已经被完全覆盖
如果从左边横放过来的骨牌已经覆盖了当前列所有需要覆盖的坏格子，那么直接转移到下一列，且下一列没有从当前列横放过去的骨牌。

## 两个格子都需要覆盖
如果第一行和第二行的格子都是坏的且没有被左边覆盖：

1. 竖放一个 $1\times 2$ 的骨牌

- 转移到下一列，$mask=0$
2. 两个横放

- 当前列第一行和第二行都横放，延伸到下一列
- 转移到下一列，$mask=3$

## 只有第一行需要覆盖
在第一行横放一个骨牌（如果下一列的第一行格子是坏的）：

- 转移到下一列，$mask=1$

# 算法步骤
基本的输入输出就不做解释。

遍历每一列 $i=1$ 到 $n$：

- 对于当前列的每个 $mask$ 状态，检查是否与好格子冲突
- 根据当前列需要覆盖的格子情况，尝试各种放置方式
- 更新下一列的状态

输出答案 $dp[n+1][0]$。

# AC code
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
string s0, s1;
cin >> s0 >> s1;
int g[2][n+2];
for (int j = 1; j <= n; ++j) {
g[0][j] = (s0[j-1] == '.') ? 0 : 1;
g[1][j] = (s1[j-1] == '.') ? 0 : 1;
}
int dc[4] = {0};
dc[0] = 1;
for (int i = 1; i <= n; ++i) {
int dn[4] = {0};
for (int m = 0; m < 4; ++m) {
int val = dc[m];
if (val == 0) continue;
if ((g[0][i] == 1 && (m & 2)) || (g[1][i] == 1 && (m & 1))) {
continue;
}
bool need0 = (g[0][i] == 0 && ((m & 2) == 0));
bool need1 = (g[1][i] == 0 && ((m & 1) == 0));
if (!need0 && !need1) {
dn[0] = min(2, dn[0] + val);
} else if (need0 && need1) {
dn[0] = min(2, dn[0] + val);
if (i+1 <= n && g[0][i+1] == 0 && g[1][i+1] == 0) {
dn[3] = min(2, dn[3] + val);
}
} else if (need0 && !need1) {
if (i+1 <= n && g[0][i+1] == 0) {
dn[2] = min(2, dn[2] + val);
}
} else {
if (i+1 <= n && g[1][i+1] == 0) {
dn[1] = min(2, dn[1] + val);
}
}
}
for (int m = 0; m < 4; ++m) {
dc[m] = dn[m];
}
}
int ans = dc[0];
if (ans == 0) {
cout << "None\n";
} else if (ans == 1) {
cout << "Unique\n";
} else {
cout << "Multiple\n";
}
}
return 0;
}
```