49 lines
1.4 KiB
Python
49 lines
1.4 KiB
Python
# -*- coding:utf-8 -*-
|
||
# @Author len
|
||
# @Create 2023/12/27 12:14
|
||
|
||
# 6.异或和之差
|
||
# 问题描述
|
||
# 给定一个含有n个元素的数组A，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。
|
||
# 输入格式
|
||
# 输入的第一行包含一个整数n。
|
||
# 第二行包含n个整数A，相邻整数之间使用一个空格分隔
|
||
# 输出格式
|
||
# 输出一行包含一个整数表示答案。
|
||
# 样例输入
|
||
# 6
|
||
# 1 2 4 9 2 7
|
||
# 样例输出
|
||
# 14
|
||
# 样例说明
|
||
# 两个子段可以分别选1和4,9,2，差值为 15-114
|
||
|
||
def max_xor_sum_difference(arr):
|
||
# 预计算异或前缀数组。
|
||
n = len(arr)
|
||
xor_arr = [0] * (n+1)
|
||
for i in range(1, n+1):
|
||
xor_arr[i] = xor_arr[i-1] ^ arr[i-1]
|
||
|
||
# 初始化答案。
|
||
max_difference = 0
|
||
|
||
# 遍历所有非重叠子段对。
|
||
for i in range(1, n+1):
|
||
for j in range(i, n+1):
|
||
for k in range(j+1, n+1):
|
||
for l in range(k, n+1):
|
||
# 计算两个子段的异或和。
|
||
xor1 = xor_arr[j] ^ xor_arr[i-1]
|
||
xor2 = xor_arr[l] ^ xor_arr[k-1]
|
||
# 更新最大差值。
|
||
max_difference = max(max_difference, abs(xor1 - xor2))
|
||
|
||
return max_difference
|
||
|
||
# 样例输入
|
||
array_length = int(input())
|
||
arr = list(map(int, input().split(" ")))
|
||
# 输出结果
|
||
print(max_xor_sum_difference(arr))
|