題面 ### 題目描述 $Mas$完成了一天的工作，走在回家的路上，看著路邊的景色，他想起來自己的童年。 許許多多的記憶交錯，絲絲縷縷的牽扯著$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;
}
