1592E - Скучающий Бакри

首先把那式子转换成长度为偶数并且二进制有一段连续的一，大于这位的数量都是偶数

如果长度为奇数那么如果 and 是1，xor 一定是1；and 是0，xor可能是1；所以长度为奇数一定不可以。

那么长度为偶数的话，对二进制的每位来说，and = 0,xor = 1   ; and = 1/0 ,xor=0;

两个数的大小是由最高不同位确定的，那么假设 二进制第 i位不同，那么上面的要相同则 只有xor = and 0  ，所以有偶数个1   和第 i 位都是 1 ；

二进制有一段连续的一，大于这位的数量都是偶数  - > 大于 这位的前缀 prexor【r】= prexor【l-1】 

 

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<map> using namespace std;typedef long long LL; typedef pair<int,int> PII; const int N=1e6+10,mod=1e9+7;void add(int &a,LL b){a=(a+b)%mod;return ;} int sum[N]; int pos[2][N],pre[N],a[N]; int main() {int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",a+i);int ma=0;for(int i=20;i>=0;i--){for(int j=1;j<=n;j++)pre[j]=pre[j-1]^(a[j]>>(i+1)),pos[j&1][pre[j-1]]=n+1;for(int r=1;r<=n;r++)if(a[r]>>i&1){if(pos[(r-1)&1][pre[r]])ma=max(ma,r-pos[(r-1)&1][pre[r]]+1);pos[r&1][pre[r-1]]=min(pos[r&1][pre[r-1]],r);}else {for(int k=r-1;a[k]>>i&1;k--)pos[k&1][pre[k-1]]=n+1;}}printf("%d\n",ma);return 0; } //那个式子转换下就是l-r，长度为偶数，二进制其中一位都是 1 ，并且 大于这位的1的数量是偶数 //假设连续一的位数是二进制的第i位 则 l-r中 i+1，i+2 -> 20 的异或是0；那就是pre[r]=pre[l-1]; //然后维护一段一，如果不是一段1的话就消去这段一的影响

总结

以上是生活随笔为你收集整理的1592E - Скучающий Бакри的全部内容，希望文章能够帮你解决所遇到的问题。

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