[AGC026C] String Coloring 题解
题目分析
题目要求对长度为 \(2N\) 的字符串进行染色（红色或蓝色），使得：
- 正向红色序列：从左到右读取所有红色字符组成的字符串。
- 反向蓝色序列：从右到左读取所有蓝色字符组成的字符串。
结论：这两个序列必须完全一致。
直接暴力枚举每个字符的颜色复杂度为 \(O(2^{2N})\)，当 \(N=18\) 时会达到 \(2^{36}\)，显然不可行。因此我们需要使用 折半搜索 (Meet-in-the-middle)。
核心算法：折半搜索
我们将字符串分成前后两部分，每部分长度均为 \(N\)。
1. 逻辑推导
假设前 \(N\) 个字符生成的红色和蓝色字符串分别为 \(R_1, B_1\)，后 \(N\) 个字符生成的红色和蓝色字符串分别为 \(R_2, B_2\)。
根据题意，最终的红色序列为 \(R_1 + R_2\)，最终的反向蓝色序列则是 \(B_2\) 的反转加上 \(B_1\) 的反转。
即：
\[R_1 + R_2 = \text{reverse}(B_2) + \text{reverse}(B_1)
\]
为了方便匹配，我们拆分等式：
- \(R_1\) 必须等于 \(\text{reverse}(B_2)\)
- \(B_1\) 必须等于 \(\text{reverse}(R_2)\)
2. 具体步骤
- 处理前半段：枚举 \(2^N\) 种染色方案，计算出对应的 \((R_1, B_1)\) 二元组，并利用
std::map<pair<string, string>, long long>记录每种二元组出现的次数。 - 处理后半段：枚举 \(2^N\) 种染色方案，计算出对应的 \((R_2, B_2)\)。
- 匹配与合并：对于后半段的方案，构造查找键值
key = {reverse(B_2), reverse(R_2)}，在map中累加对应的次数。
实现技巧：状态压缩
由于 \(N\) 较小，我们可以使用二进制状压枚举：
- 利用
(b >> i) & 1判断第 \(i\) 位是红色（1）还是蓝色（0）。 - 前半段直接提取，后半段提取后进行
reverse即可匹配。
完整代码
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pi;
typedef pair <string, string> ps;
typedef long long ll;
#define all(x) x.begin(), x.end()
int main()
{int n;string s;cin >> n >> s;string s1 = s.substr(0, n), s2 = s.substr(n, 2 * n);map <ps, ll> mp;for (int b = 0; b < (1 << n); b++){string rd, bl;for (int i = 0; i < n; i++){if (b & (1 << i)) rd += s1[i];else bl += s1[i];}mp[{rd, bl}]++;}ll ans = 0;// mp.clear();for (int b = 0; b < (1 << n); b++){string rd, bl;for (int i = 0; i < n; i++){if (b & (1 << i)) rd += s2[i];else bl += s2[i];}// mp[{rd, bl}]++;string red = rd, blue = bl;reverse(all(red)), reverse(all(blue));auto key = make_pair(blue, red);if(mp.find(key) != mp.end()) ans += mp[key];}cout << ans;return 0;
}
复杂度分析
- 时间复杂度：\(O(2^N \cdot N)\)。主要开销在二进制枚举和字符串操作上。
- 空间复杂度：\(O(2^N \cdot N)\)，用于存储
map。对于 \(N=18\)，此解法在时空限制内表现优秀。