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]$ ，则题目相当于求对于每个 $i$ 的：$$(s[i]xors[j])+s[j],j<i$$

• 我们枚举 $s[i]$ 的每个二进制位，发现如果为 $1$ 则对答案无影响，

• 如果为 $0$ 则 $s[j]$ 的这一位一定为 $1$ 更优（贪心思想）。

• 为了知道 $i$ 前面有没有一个 $s[j]$ 能满足条件，我们设一个 $f[i]$ 表示满足 $i$ 为 $s[j]$ 子集的最小的 $j$ 。

• 从高位到低枚举二进制位 $k$ ，只要满足 $f[s|2^k]\le i$ 则说明这位能选 $1$ ，并 $s+=2^k$ 。

• 这样一直做下去就能求出答案了。

• 对于 $f[i]$ 的话我们可以开始时预处理出来：

• 初值：$f[s[i]]=min(f[s[i]],i)$

• 转移的话不需要直接枚举子集，

• 我们从大到小枚举 $s$ ，再枚举状态 $s$ 中是 $1$ 的位，将其变为 $0$ ，转移即可。

• 时间复杂度 $O((n+10^6)\ast 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; }

总结

以上是生活随笔为你收集整理的JZOJ 5952. 【NOIP2018模拟11.5A组】凯旋而归的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。