A5653 · 「NOIP2024」编辑字符串

题目描述

小 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 想知道，在使用编辑工具后，两个字符串中对应位置字符相同的出现次数最多能有多少。

从文件 edit.in 中读入数据。 **本题包含多组测试数据。** 输入的第一行包含一个整数 $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}$ 不可以参与交换。

输出到文件 edit.out 中。 对于每组测试数据输出一行，包含一个整数，表示对应的答案。

输入 #1

输出 #1