#3784. 题目5-数组划分-三段异或相等-待处理
题目5-数组划分-三段异或相等-待处理
【题目描述】
给定一个非负整数数组,判断是否可以将其划分为三个连续非空的区间,使得这三个区间的异或和相等。
提示:设整个数组的异或和为 S。如果存在一种划分使得每个部分的异或和均为 T,则必有 3T = S(由于异或没有加法意义,此处“等于”应理解为 T 在划分下可以相等)。事实上,对于该题的已知证明:
- 若整个数组的异或和为 0,则答案必定为“YES”(此时只需找到任意两个非结束位置使得前缀异或和为 0);
- 否则,只要能找到两个索引 i, j(1 ≤ i < j ≤ n-1),使得 pre[i] == pre[j] == S,则答案为“YES”。
【输入格式】
- 第一行包含一个正整数 T,表示测试数据组数。
- 对于每组数据,第一行给出一个正整数 n(n ≥ 3)。
- 第二行给出 n 个非负整数,表示数组元素。
【输出格式】
- 对于每组数据,输出一行,如果能划分输出 “YES”,否则输出 “NO”。
2
4
1 2 3 0
5
1 2 3 4 5
YES
NO
【说明】
对于第一组数据,整个数组的异或和为 1 ^ 2 ^ 3 ^ 0 = 0,因此只要存在任意两个划分点使得前缀异或和为 0,即可划分成三个异或和均为 0 的区间;对于第二组数据,不存在这样的划分方式。