题目传送门(BZOJ)
>原文链接<

题解 :

求最小值, 又是为运算, 考虑贪心.

100000_{(2)} > 011111_{(2)}

我们尽可能的让高位为0, 这样一定可以获得最优解

由于异或满足前缀减, 我们先给这个数列做个前缀和.

若想一位是0, 那么在所有前缀和里必须有不小于m0,

(同样的, 不小于m1是不行的, 因为出现了一个1就代表某段有1了)

而且, 在这位上sum[n]也必须不能是1, 因为它如果是1, 前面再怎么选也会有一个配不掉的1

若没能满足这个条件, 答案就要累加这位的1

若满足了这个条件, 这位就可以是0,

但是要对所有这位为1的前缀和打一个标记, 代表以后计前缀0数目时不能再选它了.

代码很短

代码 :

#include <cstdio>#define ll long longll s[510000], x;int vis[510000];int main() { int n, m; scanf("%d%d", &n, &m); ll ans = 0; for(int i = 1; i <= n; i ++ ) scanf("%lld", &x), s[i] = s[i-1]^x; for(int i = 62; ~i ; i -- ) { int now = 0; for(int j = 1; j <= n; j ++ ) if(!(s[j]&(1ll<<i)) && !vis[j]) now ++; if((s[n]&(1ll<<i)) || now < m) ans += 1ll<<i; else { for(int j = 1; j <= n; j ++ ) if(s[j]&(1ll<<i)) vis[j] = 1; } } printf("%lld\n", ans);}