【noi.ac】#309. Mas的童年

#309. Mas的童年

链接

分析：

　　求$max {sj + (s_i oplus s_j)}$

　　因为$a + b = a oplus b + (a & b) imes 2$

　　那么就是求一个j，使得$(s_i oplus s_j) & s_j$最大。

　　而“异或后再与”这两步运算合起来，只有原来是$s_i$的这位是0，$s_j$的这位是1才可以最后是1。

　　那么就可以把i前面的所有$s_j$标记为出现过，以及这些$s_j$的子集。

　　然后将$s_i$中0的位置取出，从高位枚举，看当前这位能否为1。

代码：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<bitset>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 2000005;
int val[N], sum[N];
bool vis[N];

void Insert(int x) {
    if (vis[x]) return ;
    vis[x] = 1;
    for (int i = 20; ~i; --i) 
        if ((x >> i) & 1) Insert(x ^ (1 << i));
}
int solve(int x) {
    int now = 0;
    for (int i = 20; ~i; --i) 
        if ((x >> i) & 1) {
            now += (1 << i);
            if (!vis[now]) now -= (1 << i);
        }
    return now;
}
int main() {
    int n = read();
    for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] ^ read();
    for (int i = 1; i <= n; ++i) {
        Insert(sum[i - 1]);
        int tmp = 0;
        for (int j = 20; ~j; --j) 
            if (!((sum[i] >> j) & 1)) tmp += (1 << j);
        printf("%d ", solve(tmp) * 2 + sum[i]);
    }
    return 0;
}