P11361 题解
船酱魔王
·
·
题解
题目来源：NOIP 2024 全国统考（仅一试）第一题。
题意回顾
两个 0-1 串，有些位置固定，可以任意交换不固定的两个同一个串中的相邻位置，最大化两个串对应位置上相同的字符个数。
字符串长度上限为 10^5 ，单测试点内最多 10 组测试数据，时限 1s，空限 512MB。
分析
下文中，称两个字符串为 s,t ， u,v 分别表示 s,t 对应位置可否移动，说明中下标从 1 开始，实现中从 0 开始（这是因为 std::string 的特性）。
Subtask 1~4（ n \le 10 ）
首先有一个显然的结论，对于一个序列交换相邻项有限次一定可以排序。
考虑如何将一个序列通过相邻项交换转化为另一个序列？如果两个序列组成元素不同的话那么不可以，否则的话对于目标序列的每个元素依次编号，对于初始序列的每个元素找到这个元素在目标序列中所有编号还没被使用的最小的一个，然后不弱于序列排序问题。
故对于一段不固定位置，可以任意排列其中的字符。
枚举全排列即可，时间复杂度为 O((n!)^2) ，剪枝得当应该是能过的（心虚）。
Subtask 5~8（性质 A：第一个串中所有字符相同）
考虑答案可以转化为， \sum_{i=1}^n{[s_i=t_i]} 。
由特殊性质得，答案转化为 \sum_{i=1}^n{[s_1=t_i]} 。
直接统计即可。
时间复杂度为 O(n) 。
Subtask 9~12（性质 B：是否固定情况相同）
考虑问题可以转化为，对于若干组可以任意排列的两个等长 0-1 串，将它们分别匹配求出最大匹配个数。
显然，每个串的答案为两串同种出现次数的差值（一一匹配所有 0 ，再一一匹配所有 1 ，没被消耗的即为差值）。
Subtask 13~16（性质 C：保证两串各仅有一个位置固定）
感觉，不太好打？
也对正解没什么启发意义。
Subtask 17~20（无特殊性质）
直接讲正解吧。
考虑暴力子任务的结论，可以任意排列一段连续的可以移动的字符。
那么我们把问题转化为：对于一段连续的可以移动的字符，把他们打成一个包裹放到这段的开头一个字符，对于所有可以移动的字符从包裹中取数最大化匹配次数。
从左到右依次匹配：
* 如果此时两个字符串该位置均为固定，则直接统计答案。
* 如果此时两个字符串位置有一个不固定，那么让不固定的位置去找包裹中是否有与固定位置相同的字符，匹配上去，否则匹配另一个字符。
* 如果此时两个字符串均不固定，那么有相同字符任选一个匹配，否则匹配仅有的字符。
对于情况二，如果可以匹配上而不去匹配，那么这个位置上答案少 $ 1 $，而我们只会多获得一个字符（甚至还要考虑到放置另一个字符的对其的消耗），对答案的贡献最大为 $ 1 $。
对于情况三，如果不能匹配那么只有唯一的放置方案，否则不匹配的证明参见情况二，本质等价。设该位置为 $ s_i=t_i=0 $，则若 $ s_i=t_i $ 更改为 1，那么若答案更优一定存在（不妨设）$ s_j=0 $ 固定，$ t_j $ 由 1 换为 0 ，则存在一个 $ k $ 使得 $ s_k $ 被由 1 换为 0，则此时若 $ t_k $ 原来为 1 则答案一定不会更优，若 $ t_k $ 原来为 0 的话，因为贪心策略的原因 $ i<k<j $，则此时 $ t_p(k<p \le j) $ 一定不能为 1，因为 $ t_k $ 已经属于是被强制匹配。故 $ t_j $ 原来即为 0，与前置条件矛盾。
故贪心策略得证。
## AC 代码
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
const int N = 1e5 + 5;
int T;
int n;
string s, t, u, v;
int a[N][2], b[N][2];
int main() {
cin >> T;
for(int ti = 1; ti <= T; ti++) {
cin >> n;
cin >> s >> t >> u >> v;
for(int i = 0; i < n; i++) a[i][0] = a[i][1] = b[i][0] = b[i][1] = 0;
int beg = 0;
for(int i = 0; i < n; i++) {
if(u[i] == '0') continue;
if(i > 0 && u[i - 1] == '0') beg = i;
a[beg][s[i] - '0']++;
}
beg = 0;
for(int i = 0; i < n; i++) {
if(v[i] == '0') continue;
if(i > 0 && v[i - 1] == '0') beg = i;
b[beg][t[i] - '0']++;
}
int c[2] = {0, 0};
int d[2] = {0, 0};
int ans = 0;
for(int i = 0; i < n; i++) {
c[0] += a[i][0], c[1] += a[i][1], d[0] += b[i][0], d[1] += b[i][1];
int o = 0;
if(u[i] == '0' && v[i] == '0') ans += (s[i] == t[i]);
else if(u[i] == '0') {
o = s[i] - '0';
if(d[o] > 0) ans++, d[o]--;
else d[1 - o]--;
} else if(v[i] == '0') {
o = t[i] - '0';
if(c[o] > 0) ans++, c[o]--;
else c[1 - o]--;
} else {
if(c[0] > 0 && d[0] > 0) c[0]--, d[0]--, ans++;
else if(c[1] > 0 && d[1] > 0) c[1]--, d[1]--, ans++;
else {
if(c[0] > 0) c[0]--;
if(c[1] > 0) c[1]--;
if(d[0] > 0) d[0]--;
if(d[1] > 0) d[1]--;
}
}
}
cout << ans << endl;
}
return 0;
}
```