← 返回题目列表

AtCoder · agc065_e

E. 一二三

中文机器翻译题面 查看原题

分数: 1500 点

问题陈述

给定两个长度为正整数的序列 N, A=(A_1,A_2,\dots,A_N) 和 B=(B_1,B_2,\dots,B_N).

找到正整数序列的最小可能反转数 C=(C_1,C_2,\dots,C_N) 这样 i- 第一个元素 C_i is A_i or B_i.

解决 T 测试用例。

约束

  • 1 \le T
  • 1 \le N \le 5 \times 10^5
  • 1 \le A_i,B_i \le \color{red}{\boldsymbol{3}}
  • 总和 N 对于单个输入中的所有测试用例最多 5 \times 10^5.

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

在这里, \mathrm{case}_i 代表 i- 第一个测试用例。每个测试用例均按以下格式给出:

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

输出

打印答案。


示例输入 1

8
3
2 1 1
3 3 2
5
2 1 3 2 2
1 2 1 2 3
8
2 1 3 3 3 1 2 2
1 2 3 1 2 1 3 2
10
1 3 2 1 1 3 2 2 2 2
2 3 1 1 1 1 3 1 3 3
12
2 1 1 3 3 1 3 3 2 2 2 1
3 1 1 3 3 1 3 2 3 2 1 2
15
1 3 1 3 3 2 2 1 2 3 3 3 1 1 3
3 3 3 2 3 2 1 3 2 1 2 2 3 3 3
18
3 1 1 3 3 2 1 1 2 3 2 1 3 3 3 2 2 3
1 1 3 2 1 3 1 2 1 2 3 2 2 1 3 1 3 3
20
2 2 3 1 1 3 2 3 3 1 3 1 2 1 2 2 1 2 3 2
1 1 1 3 3 1 1 3 2 2 1 1 1 1 1 2 2 2 2 1

示例输出 1

1
0
6
6
20
9
5
17

对于第一个测试用例,最佳解决方案是 C=(2,3,2) 的反转数为 1.

对于第二个测试用例,最佳解决方案是 C=(1,1,1,2,3) 的反转数为 0.