4969. 异或和之差【Python实现】
Date:4.10
Key:Tire、贪心
思路
异或求最值的问题,还是很容易和字典树联系上的,因为用Tire可以解决序列中任意两个元素的异或值的最值问题。
回到这道题目上来,异或有个很好的性质,那就是类似于前缀和的思想,通过预处理前缀异或值可以$O(1)$的得到任意区间的异或值。
基于此,我们可以通过维护前缀异或值,得到$dp[i][0/1]$代表考虑前$i$个元素,能够得到的区间异或值的最大值(0)/最小值(1)
然后我们再从末尾开始往前扫一遍序列,对于位置$j$,我们可以求得以$j$为起始位置的区间异或值的最大值和最小值,再结合dp数组($dp[j-1]$代表的是前$j-1$个元素中能够得到的区间异或值的最值),我们可以求得最终的答案。
具体实现见下方的代码。
【测评结果】
AcWing上的机子跑出来被T掉了,但我估计是AcWing上给py开的时限不够,因为俺觉得俺的做法不假,可能常数稍微有点大,在蓝桥杯的机子上测评是能够AC的, 蓝桥杯传送门
代码
from sys import stdin
input = lambda: stdin.readline()
n = int(input())
A = list(map(int, input().split()))
maxm = 21 * n + 100
nxt = [[0, 0] for _ in range(maxm)]
tot = 0
def ins(s):
global tot
p = 0
for i in reversed(range(21)):
ch = (s >> i) & 1
if not nxt[p][ch]:
tot += 1
nxt[p][ch] = tot
p = nxt[p][ch]
def getmax(s):
lis = []
p = 0
for i in reversed(range(21)):
ch = (s >> i) & 1
nch = ch ^ 1
if nxt[p][nch]:
p = nxt[p][nch]
lis.append(nch)
else:
p = nxt[p][ch]
lis.append(ch)
res,bas = 0,1
while len(lis):
res += bas * lis.pop()
bas <<= 1
return res
def getmin(s):
lis = []
p = 0
for i in reversed(range(21)):
ch = (s >> i) & 1
nch = ch ^ 1
if nxt[p][ch]:
p = nxt[p][ch]
lis.append(ch)
else:
p = nxt[p][nch]
lis.append(nch)
res,bas = 0,1
while len(lis):
res += bas * lis.pop()
bas <<= 1
return res
dp = [[0, 0]for _ in range(n)]
tmp = 0
ins(tmp)
for i in range(n):
tmp ^= A[i]
dp[i][0] = getmax(tmp) ^ tmp
dp[i][1] = getmin(tmp) ^ tmp
ins(tmp)
if i:
dp[i][0] = max(dp[i - 1][0], dp[i][0])
dp[i][1] = min(dp[i - 1][1], dp[i][1])
for i in range(tot + 1):
nxt[i][0] = nxt[i][1] = 0
tot = 0
tmp = 0
ins(tmp)
ans = 0
for i in reversed(range(1, n)):
j = i - 1
tmp ^= A[i]
maax = getmax(tmp) ^ tmp
miin = getmin(tmp) ^ tmp
ins(tmp)
ans = max(ans, maax - dp[j][1], dp[j][0] - miin)
print(ans)