首页 > 代码库 > codeforce gym 100307H Hack Protection
codeforce gym 100307H Hack Protection
原题地址：http://codeforces.com/gym/100307/problem/H
题意：
给定一个序列，求序列的子区间中，满足子区间XOR值等于AND值得子区间个数。
题解：
一直以为NEERC这种有名的比赛应该题解到处都是，太天真了……
首先考虑区间的AND值。
对于固定起点的区间，因为 & 的性质，AND值必然单调递减，并且，根据AND值中1的个数划分后面的区间，必然最多只能划分成32段，对于某一段中的任意位置，它和固定的起点所形成的子区间的AND值是一样的。
再来考虑区间的XOR值
对于数列A[]，定义sum(a,b)=A[a]^A[a+1]^...^A[b]；
那么sum(a,b)=(A[1]^A[2]^...^A[a-1])^((A[1]^A[2]^...^A[a-1])^(A[a]^A[a+1]^...^A[b])=sum(1,a-1)^sum(1,b)，这是一个前缀和形式
考虑题给的等式，AND(a,b)==XOR(a,b)
也就是AND(a,b)==XOR(1,a-1)^XOR(1,b)
也就是AND(a,b)^XOR(1,a-1)==XOR(1,b) ——（1）
我们枚举区间的起点，XOR(1,a-1）是定值，接下来枚举AND值相同的区段，最多32段，在每一段中寻找满足等式（1）的b，累计答案
区间AND值可以用RMQ思想处理，区段的划分可以二分处理，而寻找区段中XOR值为固定值的元素个数，可以转化为前缀和
#include<bits/stdc++.h>#define clr(x,y) memset((x),(y),sizeof(x))using namespace std;typedef long long LL;struct seg{ int l; int val;};const int maxn=1e5;int AND[maxn+5][18];int XOR[maxn+5];int n;int A[maxn+5];vector <seg> v[maxn+5]; //段划分map <int,vector<int> > mp; //mp[x]中储存XOR[1,a]==x的元素下标avoid build() //计算区间AND值{ for (int i=1;i<=n;++i) AND[i][0]=A[i]; for (int j=1;(1<<j)<=n;++j) { for (int i=0;i+(1<<j)-1<=n;++i) { AND[i][j]=AND[i][j-1] & AND[i+(1<<(j-1))][j-1]; } }}int calu(int l,int r){ int k=0; while ((1<<(k+1))<=r-l+1) ++k; return AND[l][k] & AND[r-(1<<k)+1][k];}LL Count(int l,int r,int val) //区间[l,r]中XOR值为val的元素个数{ return upper_bound(mp[val].begin(),mp[val].end(),r)-lower_bound(mp[val].begin(),mp[val].end(),l);}void solve(){ ++n; A[n]=0;//为了便于划分在末尾加上一个0 build(); for (int i=1;i<=n;++i) v[i].clear(); for (int i=1;i<=n;++i) { int val=A[i]; int l=i; int r=n; v[i].push_back((seg){l,val}); while (val!=0) //不断二分划分段 { int lb=l; int ub=r; while (ub-lb>1) { int mid=(ub+lb)>>1; if (calu(i,mid)==val) { lb=mid; } else { ub=mid; } } l=ub; val=calu(i,l); v[i].push_back((seg){l,val}); } } mp.clear(); XOR[0]=0; for (int i=1;i<=n;++i) { XOR[i]=XOR[i-1]^A[i]; mp[XOR[i]].push_back(i); } LL ans=0; for (int i=1;i<=n;++i) { for (int j=0;j<v[i].size();++j) { int l=v[i][j].l; int r=(j==v[i].size()-1)? n:v[i][j+1].l-1; int val=v[i][j].val^XOR[i-1]; ans+=Count(l,r,val); //printf("%d %d %d\n",l,r,val); } } //消除最后那个虚拟的0对答案的影响 LL extra=1; int xor_tmp=0; for (int i=n-1;i>=1;--i) { xor_tmp^=A[i]; if (xor_tmp==0) ++extra; } printf("%lld\n",ans-extra);}int main(void){ #ifdef ex freopen ("../in.txt","r",stdin); //freopen ("../out.txt","w",stdout); #endif freopen("hack.in","r",stdin); freopen("hack.out","w",stdout); while (scanf("%d",&n)==1) { for (int i=1;i<=n;++i) { scanf("%d",&A[i]); } solve(); }}
codeforce gym 100307H Hack Protection
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。