JZOJ 5952. 【NOIP2018模拟11.5A組】凱旋而歸

Description

Input

第一行一個整數 n，表示數的個數。

第二行n個整數，第i個整數為ai 。

Output

n行一個整數表示答案，第i行表示序列第i個字首的帥氣值。

Sample Input

5

1 2 3 4 5

Sample Output

1

3

6

10

9

Data Constraint

對于50%的資料，N<=6666

對于100%的資料， N<=456789,0<=ai<=10^6

Solution

• 設字首異或和為 s [ i ] s[i] s[i] ，則題目相當于求對于每個 i i i 的： ( s [ i ]   x o r   s [ j ] ) + s [ j ]   ,   j &lt; i (s[i]\ xor\ s[j])+s[j]\ ,\ j&lt;i (s[i] xor s[j])+s[j] , j<i
• 我們枚舉 s [ i ] s[i] s[i] 的每個二進制位，發現如果為 1 1 1 則對答案無影響，
• 如果為 0 0 0 則 s [ j ] s[j] s[j] 的這一位一定為 1 1 1 更優（貪心思想）。
• 為了知道 i i i 前面有沒有一個 s [ j ] s[j] s[j] 能滿足條件，我們設一個 f [ i ] f[i] f[i] 表示滿足 i i i 為 s [ j ] s[j] s[j] 子集的最小的 j j j 。
• 從高位到低枚舉二進制位 k k k ，隻要滿足 f [ s ∣ 2 k ] ≤ i f[s|2^k]\leq i f[s∣2k]≤i 則說明這位能選 1 1 1 ，并 s + = 2 k s+=2^k s+=2k 。
• 這樣一直做下去就能求出答案了。
• 對于 f [ i ] f[i] f[i] 的話我們可以開始時預處理出來：
• 初值： f [ s [ i ] ] = m i n ( f [ s [ i ] ] , i ) f[s[i]]=min(f[s[i]],i) f[s[i]]=min(f[s[i]],i)
• 轉移的話不需要直接枚舉子集，
• 我們從大到小枚舉 s s s ，再枚舉狀态 s s s 中是 1 1 1 的位，将其變為 0 0 0 ，轉移即可。
• 時間複雜度 O ( ( n + 1 0 6 ) ∗ 20 ) O((n+10^6)*20) O((n+106)∗20) 。

Code

#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
const int N=456800,inf=1e9;
int a[N],f[1<<20],p[20];
inline int read()
{
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
void write(int x)
{
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
inline int min(int x,int y)
{
	return x<y?x:y;
}
int main()
{
	freopen("ak.in","r",stdin);
	freopen("ak.out","w",stdout);
	int n=read();
	for(int i=1;i<=n;i++) a[i]=a[i-1]^read();
	memset(f,60,sizeof(f));
	for(int i=n;i;i--) f[a[i]]=i;
	for(int i=p[0]=1;i<20;i++) p[i]=p[i-1]<<1;
	for(int i=(1<<20)-1;i>=0;i--)
		if(f[i]<inf)
			for(int j=0;j<20;j++)
				if(i&p[j]) f[i^p[j]]=min(f[i^p[j]],f[i]);
	for(int i=1;i<=n;i++)
	{
		int sum=a[i],num=0;
		for(int j=19;j>=0;j--)
			if(!(sum&p[j]) && f[num|p[j]]<=i) num|=p[j];
		int ans=num+(sum^num);
		write(ans),putchar('\n');
	}
	return 0;
}