#NOIP2024A. 编辑字符串(edit)民间数据

编辑字符串(edit)民间数据

[NOIP2024] 编辑字符串(民间数据)

题目背景

1s 512MB

题目描述

小 M 有两个长度为 nn 且字符集为 {0,1}\{0, 1\} 的字符串 s1,s2s_1, s_2

小 M 希望两个字符串中对应位置字符相同的出现次数尽可能多,即满足 s1,i=s2,is_{1,i} = s_{2,i}i(1in)i(1 \leq i \leq n) 尽可能多。为此小 M 有一个字符串编辑工具,这个工具提供的基本操作是在一个字符串中交换两个相邻的字符。为了保持字符串的可辨识性,规定两个字符串中的部分字符不能参与交换。小 M 可以用工具对 s1s_1s2s_2 进行多次字符交换,其中可以参与交换的字符能够交换任意多次。

现在小 M 想知道,在使用编辑工具后,两个字符串中对应位置字符相同的出现次数最多能有多少。

输入格式

本题包含多组测试数据。

输入的第一行包含一个整数 TT,表示测试数据的组数。

接下来包含 TT 组数据,每组数据的格式如下:

  • 第一行包含一个整数 nn,表示字符串长度。
  • 第二行包含一个长度为 nn 且字符集为 {0,1}\{0, 1\} 的字符串 s1s_1
  • 第三行包含一个长度为 nn 且字符集为 {0,1}\{0, 1\} 的字符串 s2s_2
  • 第四行包含一个长度为 nn 且字符集为 {0,1}\{0, 1\} 的字符串 t1t_1,其中 t1,it_{1,i}11 表示 s1,is_{1,i} 可以参与交换,t1,it_{1,i}00 表示 s1,is_{1,i} 不可以参与交换。
  • 第五行包含一个长度为 nn 且字符集为 {0,1}\{0, 1\} 的字符串 t2t_2,其中 t2,it_{2,i}11 表示 s2,is_{2,i} 可以参与交换,t2,it_{2,i}00 表示 s2,is_{2,i} 不可以参与交换。

输出格式

对于每组测试数据输出一行,包含一个整数,表示对应的答案。

样例 #1

样例输入 #1

1
6
011101
111010
111010
101101

样例输出 #1

4

提示

【样例 1 解释】

最开始时,s1=011101s_1 = \tt{011101},第 44 和第 66 个字符不能参与交换;s2=111010s_2 = \tt{111010},第 22 和第 55 个字符不能参与交换。

考虑如下操作:先交换 s1,1s_{1,1}s1,2s_{1,2} 得到 s1=101101s_1 = \tt{101101},再交换 s1,2s_{1,2}s1,3s_{1,3} 得到 s1=110101s_1 = \tt{110101},最后交换 s2,3s_{2,3}s2,4s_{2,4} 得到 s2=110110s_2 = \tt{110110}。此时 s1s_1s2s_2 的前 44 个位置上的字符都是相同的。可以证明不存在更好的方案,故输出 44

【样例 2 解释】

见附件的 edit/edit2.in 与 edit/edit2.ans。

该样例共有 1010 组测试数据,其中第 i(1i10)i(1 \leq i \leq 10) 组测试数据满足数据范围中描述的测试点 2i12i - 1 的限制。

【数据范围】

对于所有的测试数据,保证:1T101 \leq T \leq 101n1051 \leq n \leq 10^5

测试点编号 nn\leq 特殊性质
141\sim 4 1010
5,65,6 10310^3 A
7,87,8 10510^5
9,109,10 10310^3 B
11,1211,12 10510^5
13,1413,14 10310^3 C
15,1615,16 10510^5
17,1817,18 10310^3
19,2019,20 10510^5
  • 特殊性质 A:保证 s1s_1 的所有字符相同。
  • 特殊性质 B:保证 t1=t2t_1 = t_2
  • 特殊性质 C:保证 t1t_1t2t_2 中各自恰有一个字符 0\tt 0