[比赛补题][×] 2019 ICPC南昌邀请赛网络赛 K MORE XOR

2019 ICPC南昌邀请赛网络赛 K MORE XOR

题目链接

(⊙﹏⊙)不知道为什么比赛时候这个题和D题死推不出来,比赛完了5分钟ac,我大概脑子坏掉了。真的是超超超超级简单的一个题,但是我光顾着用数学公式推了所以推出来结果巨复杂(⊙﹏⊙)服了自己了。

题解:先说怎么求g(l,r): 首先f(l,r)很好求,利用异或的性质,预处理出来前缀异或和就可以了。设预处理出来p1[x]表示从a[1]到a[x]的异或和,那么很容易得到\[f(l,r)=p1[l-1]\oplus p2[r] \], 那么可以由g的定义就可以知道 \[ g(l,r)=\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} f(i,j) =\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} p1[i-1]\oplus p1[j] \];当然这个东西还是很复杂的,我们想办法把他复杂度搞到O(1):考虑每个p1[x]出现的次数,列个表可以发现,在这个求和式中出现的所有下标,从l-1变化到r, 而每个下标出现的次数都是一样的,这个次数等于 r-l+1 ,那么就可以得出结论,如果r-l+1为偶数,则g(l,r)应为0,否则应为\[ \sum_{i=l-1}^{r} p1[i] \],注意到这个式子又可以用p1的前缀和来O(1)计算,所以又可以提前求出来p1的前缀和p2,这样的话g(l,r)就可以表示为

\[g(l,r)=
\begin{cases}
0& \text{(r-l+1) is odd}\\
p2[l-2]\oplus p2[r]& \text{else }
\end{cases}\]

有了g(l,r)再来考虑w(l,r),\[w(l,r)=\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} g(i,j) \],就跟g的表达式很像,但是这里不能直接再套用g关于p1的公式,因为g里面有很多的0是跟p2无关的,换句话说这些0并不是由p2[l-2]^p2[r]求出来的,所以要分类讨论。分析方法跟g是类似的,列一个表观察每个p2出现的规律,可以发现,这个规律是4个一循环的结构,设\[t=(r-l+1)\mod 4\]; 则当t==0时,所有的p2下标出现次数均为偶数次,也就是结果一定为0,t==2时,所有的p2下标出现次数均为奇数,这样的话即等于\[\sum_{i=l-1}^{r} p2[i] \],这个式子说明我们可以再用一个p2的前缀和p3来O(1)计算这个结果。这是比较简单的两种情况,另外两种是t==1和t==3,这两种一种是奇数项的出现次数为奇数偶数项为偶数,另一种是奇数项出现次数为偶数而偶数项出现次数为奇数,这意味着可以用一个分奇偶的前缀和来O(1)求得这个式子只不过仍需要分类讨论一次。。若令p31[i]和p32[i]分别表示p2的奇偶前缀和,t=(r-l+1)%4, 则w(l,r)的表达式为

\[
w(l,r)=
\begin{cases}
0& \text{t=0}\\
p31[r]\oplus p31[l-3]& \text{t=1 and r is odd}\\
p32[r]\oplus p32[l-3]& \text{t=1 and r is even}\\
p3[l-3]\oplus p3[r]& \text{t=2}\\
p32[r-1]\oplus p32[l-2]& \text{t=3 and r is odd}\\
p31[r]\oplus p31[l-3]& \text{t=3 and r is even}
\end{cases}
\]

这样的话整个问题就可以O(1)解决了。。不知道我当时脑子怎么回事就没推出来

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 1e5+5, mod = 1e9+7;

int a[maxn],n;

int p1[maxn],p2[maxn],p3[maxn],p11[maxn],p12[maxn],p31[maxn],p32[maxn];

void init(){
	for(int i=1;i<=n;i++){
		p1[i]=p1[i-1]^a[i];
		p2[i]=p2[i-1]^p1[i];
		p3[i]=p3[i-1]^p2[i];
	}

	for(int i=1;i<=n;i++){
		if(i&1){
			p11[i]=p11[i-1]^a[i],p12[i]=p12[i-1],p31[i]=p31[i-1]^p2[i],p32[i]=p32[i-1];
		} 
		else{
			p11[i]=p11[i-1],p12[i]=p12[i-1]^a[i],p31[i]=p31[i-1],p32[i]=p32[i-1]^p2[i];
		}
	}
}




int pp2(int x){
	if(x<1)return 0;
	return p2[x];
}

int pp3(int x){
	if(x<1) return 0;
	return p3[x];
}

int pp31(int x){
	if(x<1) return 0;
	return p31[x];
}

int pp32(int x){
	if(x<1) return 0;
	return p32[x];
}



int ww(int l,int r){
	if(l==r) return a[l];
	int res=0;
	int t=(r-l+1)%4;
	if(t==0){
		return 0;
	}
	else if(t==1){
		if(r&1){
			return pp31(r)^pp31(l-3);
		}
		else{
			return pp32(r)^pp32(l-3);
		}
	}
	else if(t==2){
		return pp3(l-3)^pp3(r);
	}
	else
	{
		if((r-1)&1){
			return pp31(r-1)^pp31(l-2);
		}
		else{
			return pp32(r-1)^pp32(l-2);
		}
	}
	
}

int main()
{
	int  t,l,r;
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		init();
		int q;
		cin>>q;
		while(q--){
			scanf("%d%d",&l,&r);
			printf("%d\n",ww(l,r));
		}
	}
	
	return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据