#309. Mas的童年

链接

分析：

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

　　因为$a + b = a \oplus b + (a \& b) \times 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=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

int val[N], sum[N];

bool vis[N];

void Insert(int x) {

    if (vis[x]) return ;

    vis[x] = ;

    for (int i = ; ~i; --i)

        if ((x >> i) & ) Insert(x ^ ( << i));

}

int solve(int x) {

    int now = ;

    for (int i = ; ~i; --i)

        if ((x >> i) & ) {

            now += ( << i);

            if (!vis[now]) now -= ( << i);

        }

    return now;

}

int main() {

    int n = read();

    for (int i = ; i <= n; ++i) sum[i] = sum[i - ] ^ read();

    for (int i = ; i <= n; ++i) {

        Insert(sum[i - ]);

        int tmp = ;

        for (int j = ; ~j; --j)

            if (!((sum[i] >> j) & )) tmp += ( << j);

        printf("%d ", solve(tmp) *  + sum[i]);

    }

    return ;

}

巴特西

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

#309. Mas的童年

最新文章

热门文章