#C. Menorah (※※)

    远端评测题 2000ms 256MiB

Menorah (※※)

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

光明节灯台上有nn根蜡烛,其中一些蜡烛最初是点燃的。我们可以用二进制字符串 ss来描述哪些蜡烛被点燃,其中当且仅当 si=1s_i=1时,第 ii根蜡烛才会被点燃。

最初,烛光用字符串 aa来描述。在操作中,您可以选择一支当前点亮的蜡烛。这样,您选择的蜡烛将保持点亮状态,而其他蜡烛则会发生变化(如果点亮,则变为未点亮;如果未点亮,则变为点亮)。

您想让蜡烛看起来和字符串bb一样。你的任务是确定这是否可能,如果可能,找出所需的最小运算次数。

输入描述

第一行包含一个整数 tt1t1041\le t\le 10^4)--测试用例数。然后是 tt个案例。

每个测试用例的第一行包含一个整数 nn1n1051\le n\le 10^5)--蜡烛的数量。

第二行包含一个长度为 nn的字符串 aa,由符号 0 和 1 组成--最初的灯光模式。

第三行包含由符号 0 和 1 组成的长度为 nn的字符串 bb--期望的灯光模式。

保证 nn的总和不超过 10510^5

输出描述

对于每个测试用例,输出将 aa转换为 bb所需的最少操作数,如果不可能,则输出 1-1

样例

5
5
11010
11010
2
01
11
3
000
101
9
100010111
101101100
9
001011011
011010101
0
1
-1
3
4

说明

在第一个测试案例中,两个字符串已经相等,因此我们无需执行任何操作。

在第二个测试用例中,我们可以执行一个操作,选择第二根蜡烛,将 0101转换为 1111

在第三个测试案例中,由于没有点燃的蜡烛可以选择,所以无法执行任何操作。

在第四个测试案例中,我们可以执行以下操作将aa转化为bb

  1. 选择77th 蜡烛:100010111011101100100010{\color{red}1}11\to 011101{\color{red} 1}00.
  2. 选择第22根蜡烛:0111011001100100110{\color{red} 1}1101100\to 1{\color{red} 1}0010011.
  3. 选择第11根蜡烛:110010011101101100{\color{red}1}10010011\to {\color{red}1}01101100.

在第五个测试案例中,我们可以执行以下操作将aa转化为bb

  1. 选择第66根蜡烛:00101101111010110000101{\color{red}1}011\to 11010{\color{red}1}100
  2. 选择第22根蜡烛:1101011000110100111{\color{red}1}0101100\to 0{\color{red}1}1010011
  3. 选择第88根蜡烛:0110100111001011100110100{\color{red}1}1\to 1001011{\color{red}1}0
  4. 选择第77根蜡烛:100101110011010101100101{\color{red}1}10\to 011010{\color{red}1}01

10.22下午1点半作业

未认领
状态
已结束
题目
4
开始时间
2023-10-22 0:00
截止时间
2023-10-30 23:59
可延期
24 小时