logo AlgoBeat OnlineJudge
登录 注册

#215267. [ROIR 2026] XOR 染色

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

给定两个非负整数数组

定义 。换句话说, 是数组 中所有满足 的按位异或结果不超过 的下标 的集合。

请求出最小的数字 ,使得可以将数组 中的元素染成 种颜色,且满足:如果 相交,则 必须被染成不同的颜色。

换言之,需要找到 ,使得 ,并且如果 ,则

提醒一下,两个非负整数的按位“异或”(,xor)定义如下:将两个数写作二进制形式,结果的第 个二进制位为 1,当且仅当两个参数中恰好有一个在该位为 1。例如,。该操作在所有现代编程语言中都有实现,在 C++、Java 和 Python 中写作 ^,在 Pascal 中写作 xor。

输入格式

此题的输入包含多个测试用例。

输入的第一行包含一个整数 —— 测试用例的数量。

接下来是各个测试用例的描述。

每个测试用例的第一行包含三个整数 )。

第二行包含 个整数 —— 数组 的元素()。

第三行包含 个整数 —— 数组 的元素()。

保证所有测试用例的 值之和以及 值之和均不超过

输出格式

对于每个测试用例,输出一个整数 —— 所求的最小

样例

样例输入 1

3
2 2 0
0 0
1 1
5 5 3
0 1 2 3 4
0 1 2 3 4
5 5 4
0 1 2 3 4
0 1 2 3 4

样例输出 1

1
4
5

数据范围与提示

评分规则

子任务 分值 额外限制 必要子任务
1 5 ---
2 1
3 1, 2
4 1–3
5 1–4
6 10 1–5
7 5 ---
8 10
9 5
10 9
11 35 无额外限制 1–10