https://codeforces.com/contest/2115/problem/D
Гелифиш и Флауэр играют в игру.
Игра состоит из двух массивов из n
целых чисел a1,a2,…,an
и b1,b2,…,bn
, а также бинарной строки c1c2…cn
длиной n
.
Также есть целое число x
, которое инициализируется значением 0
.
Игра состоит из n
раундов. Для i=1,2,…,n
раунд проходит следующим образом:
Если ci=0
, активным игроком будет Гелифиш. В противном случае, если ci=1
, активным игроком будет Флауэр.
Активный игрок выполнит ровно одну из следующих операций:
Присвоить x:=x⊕ai
.
Присвоить x:=x⊕bi
.
Здесь ⊕
обозначает операцию побитового исключающего ИЛИ.
Гелифиш хочет минимизировать итоговое значение x
после n
раундов, в то время как Флауэр хочет максимизировать его.
Найдите итоговое значение x
после всех n
раундов, если оба игрока играют оптимально.
Моя идея - задать начальное значнеие как xor сумму. и на каждом шаге решать включать ли b[i] вместо a[i] или нет.
Была идея включать дп перебирать посуффиксм для различныз range но она несраотало.
_max=sum(a)+sum(b)
_dp = [[0 for _ in range(2*_max+1)] for _ in range(n+1)]
for i in range(_max+1):
_dp[-1][i^a[i]] = a[-1] ^ i
_dp[-1][i^b[i]] = b[-1] ^ i
for i in range(n-1, -1, -1):
for j in range(_max+1):
if c[i]==1:
_dp[i][j]=max(_dp[i+1][j^b[i]], _dp[i+1][j^a[i]])
else:
_dp[i][j]=min(_dp[i+1][j^b[i]], _dp[i+1][j^a[i]])
return max(_dp[0]) if c[0]==1 else min(_dp[0])
Текущая идея - задать начальное значнеие как xor сумму. и на каждом шаге решать включать ли b[i] вместо a[i] или нет.
def _eval_r(a: list, b: list, c:list, n:int):
x=reduce(lambda x,y: x^y, a)
b=[b[i]^a[i] for i in range(n)]
for i in range(n-1, -1, -1):
new_x=x^b[i]
if c[i]==1 and new_x>x:
x=new_x
elif new_x<x:
x=new_x
return x
t=int(input())
for _ in range(t):
_=input()
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]
c=[int(x) for x in input()]
print(_eval_r(a, b, c, len(a)))
