You are given an array a1,a2,…,an(1≤n≤105,0≤ai≤109) and two integers k,x, determine if it is possible to divide the array into exactly k segments [l1,r1],[l2,r2],…,[lk,rk](l1=1,rk=n,li+1=ri+1) such that ∀i∈[1,k],⊕rij=liaj≤x.
Greedy.
Consider the first segment. Let p be the mininum position such that ⊕pj=1aj≤x, is the partition [l1,r1]=[1,p] optimal?
Yes. You could easily prove that.
Have you found some cases that the solution in Hint 2 dosen't work?
Try to reverse the array.
Read the hints first.
For each segment, we want it to be as short as possible. Thus, we can just iterate r from l to n, when the XOR sum of a[l,r] is not greater than x, divide here. If we get exactly k segments, output Yes
, otherwise the answer is No
.
There's a small case: sometimes you need to reverse the array and calculate again, think about why.