noi.ac309 Mas的童年

题面

题目描述

\(mas\)完成了一天的工作，走在回家的路上，看着路边的景色，他想起来自己的童年。

许许多多的记忆交错，丝丝缕缕的牵扯着\(mas\)。

在回忆的深处，\(mas\)想起来了一个常常在幼儿园玩的游戏。

有\(n\)个小朋友一起排成一排，然后小朋友们会一起开始跳舞。

聪明的\(mas\)发现，每个小朋友都有自己的高兴程度，对于第\(i\)个小朋友，他的高兴程度是\(ai\)。

当一排高兴程度分别为\(b_1,b_2,…,b_k\)的\(k\)个小朋友跳舞的时候，他们会产生\(b1 \otimes b2 \otimes ⋯\otimes bk\)的愉悦值。

但是\(mas\)觉得不够尽兴，于是他决定让小朋友们从某个位置分开，让原本一排的队伍分成两排，从而使两排新队伍的愉悦值加起来最大，当然，是有可能不分成两排的。

具体的，对于一排kk个小朋友，他们的高兴程度分别是\(b_1,b_2,…,b_k\),\(mas\)会找到位置\(i\in [0,k)，使得(b1\otimes ⋯\otimes bi)+(bi+1\otimes ⋯\otimes bk)\)最大。

回想起这个游戏的\(mas\)决定再来玩一下这个游戏，于是他想起来了某一天排成一排的\(n\)个小朋友的高兴程度\(a1,a2,…,an\)对于\(i=1..n\)，\(mas\)希望求出前\(i\)个小朋友排成的队伍中通过拆分成两个队伍能够得到的最大愉悦值的和是多少。

输入

第一行一个正整数\(n\)表示小朋友的数量。

第二行\(n\)个整数，表示\(a_{1..n}\)。

输出

一行\(n\)个整数表示答案。

思路

读完拉么长的题面。发现他其实就是对于每个位置要求这个东西

\[max\{(s_i \otimes s_j)+ s_j\}\]

其中\(s_i\)表示前\(i\)个元素的异或和。

然后根据\(a+b = a\otimes b + (a \& b) \times 2\)

这个证明的话很显然：因为异或相当于不进位的加法。用\(\&\)可以求出需要进位的位置。然后乘二在相加就可以啦。

这样我们就可以把要求的式子变成这个样子

\[max\{s_i \otimes s_j \otimes s_j + (s_i \otimes s_j \& s_j) \times 2\}\]

\[=max\{s_i + (s_i \otimes s_j \& s_j) \times 2\}\]

因为\(s_i\)是确定的，只要让\(s_i \otimes s_j \& s_j\)最大就行了。

然后我们按位思考。对于二进制下的第\(k\)位。如果\(s_i\)的这一位为\(1\)，那么不管\(s_j\)这一位是什么，肯定都无法将答案的这一位变成\(1\)。

所以我们就想要让\(s_i\)为\(0\)的那些位置尽可能变成\(1\)。

对于每个\(s_j\)，我们将他和他的子集标记一下。然后贪心的从高位到低位将\(s_i\)为\(0\)的位置变为\(1\).

并且查看当前的答案是不是之前标记过。

具体看代码吧

代码

/*
* @author: wxyww
* @date:   2019-03-30 08:10:10
* @last modified time: 2019-03-31 08:31:43
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int n = 2000000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int s[n];
bool vis[n];
void ins(int x) {
    if(vis[x]) return;
    vis[x] = true;
    for(int i = 0;i <= 20;++i) {
        if((x >> i) & 1)    ins(x - (1 << i));
    }
}
int solve(int x) {
    int ret = 0;
    int k = x ^ ((1 << 21) - 1);
    for(int i = 20;i >= 0;--i) 
        if(((k >> i) & 1) && vis[(ret + (1 << i))]) 
            ret += (1 << i);
    return ret;
}
int main() {
    int n = read();
    for(int i = 1;i <= n;++i) s[i] = s[i - 1] ^ read();

    vis[0] = true;

    for(int i = 1;i <= n;++i) {
        printf("%d ",solve(s[i]) * 2 + s[i]);
        ins(s[i]);
    }

    return 0;
}