6002. T2-[NOIP2024] 编辑字符串(edit)
时间限制：1000 MS 内存限制：512 MB
题目描述
## 题目描述 小 M 有两个长度为 $n$ 且字符集为 $\{0, 1\}$ 的字符串 $s\_1, s\_2$。 小 M 希望两个字符串中对应位置字符相同的出现次数尽可能多，即满足 $s\_{1,i} = s\_{2,i}$ 的 $i(1 \leq i \leq n)$ 尽可能多。为此小 M 有一个字符串编辑工具，这个工具提供的基本操作是在一个字符串中交换两个**相邻**的字符。为了保持字符串的可辨识性，规定两个字符串中的部分字符不能参与交换。小 M 可以用工具对 $s\_1$ 或 $s\_2$ 进行多次字符交换，其中可以参与交换的字符能够交换任意多次。 现在小 M 想知道，在使用编辑工具后，两个字符串中对应位置字符相同的出现次数最多能有多少。 ## 输入格式 **本题包含多组测试数据。** 输入的第一行包含一个整数 $T$，表示测试数据的组数。 接下来包含 $T$ 组数据，每组数据的格式如下： - 第一行包含一个整数 $n$，表示字符串长度。 - 第二行包含一个长度为 $n$ 且字符集为 $\{0, 1\}$ 的字符串 $s\_1$。 - 第三行包含一个长度为 $n$ 且字符集为 $\{0, 1\}$ 的字符串 $s\_2$。 - 第四行包含一个长度为 $n$ 且字符集为 $\{0, 1\}$ 的字符串 $t\_1$，其中 $t\_{1,i}$ 为 $1$ 表示 $s\_{1,i}$ 可以参与交换，$t\_{1,i}$ 为 $0$ 表示 $s\_{1,i}$ 不可以参与交换。 - 第五行包含一个长度为 $n$ 且字符集为 $\{0, 1\}$ 的字符串 $t\_2$，其中 $t\_{2,i}$ 为 $1$ 表示 $s\_{2,i}$ 可以参与交换，$t\_{2,i}$ 为 $0$ 表示 $s\_{2,i}$ 不可以参与交换。 ## 输出格式 对于每组测试数据输出一行，包含一个整数，表示对应的答案。 ## 输入输出样例 #1 ### 输入 #1 ``` 1 6 011101 111010 111010 101101 ``` ### 输出 #1 ``` 4 ``` ## 说明/提示 **【样例 1 解释】** 最开始时，$s\_1 = \tt{011101}$，第 $4$ 和第 $6$ 个字符不能参与交换；$s\_2 = \tt{111010}$，第 $2$ 和第 $5$ 个字符不能参与交换。 考虑如下操作：先交换 $s\_{1,1}$ 与 $s\_{1,2}$ 得到 $s\_1 = \tt{101101}$，再交换 $s\_{1,2}$ 与 $s\_{1,3}$ 得到 $s\_1 = \tt{110101}$，最后交换 $s\_{2,3}$ 与 $s\_{2,4}$ 得到 $s\_2 = \tt{110110}$。此时 $s\_1$ 与 $s\_2$ 的前 $4$ 个位置上的字符都是相同的。可以证明不存在更好的方案，故输出 $4$。 **【样例 2 解释】** 见附件的 edit/edit2.in 与 edit/edit2.ans。 该样例共有 $10$ 组测试数据，其中第 $i(1 \leq i \leq 10)$ 组测试数据满足数据范围中描述的测试点 $2i - 1$ 的限制。 **【数据范围】** 对于所有的测试数据，保证：$1 \leq T \leq 10$，$1 \leq n \leq 10^5$。 | 测试点编号 | $n\leq$ | 特殊性质 | | :----------: | :----------: | :----------: | | $1\sim 4$ | $10$ | 无 | | $5,6$ | $10^3$ | A | | $7,8$ | $10^5$ | ^ | | $9,10$ | $10^3$ | B | | $11,12$ | $10^5$ | ^ | | $13,14$ | $10^3$ | C | | $15,16$ | $10^5$ | ^ | | $17,18$ | $10^3$ | 无 | | $19,20$ | $10^5$ | ^ | - 特殊性质 A：保证 $s\_1$ 的所有字符相同。 - 特殊性质 B：保证 $t\_1 = t\_2$。 - 特殊性质 C：保证 $t\_1$ 和 $t\_2$ 中各自恰有一个字符 $\tt 0$。