2021 牛客 OI 赛前集训营-普及组(第三场)异或题解

我tm的好不容易做出来结果没开long long只拿到了暴力分！

三年OI一场空，不开long long 见祖宗！

一定要记住这句话，我之前没怎么在意过，现在才知道后果！！！！！！

吐槽：我们同学有个ren他ctj!!!!而且他还AC了！！不讲武德！~~~~他，就是姓陈！!!!!!

解决思路

你会发现他在转圈。 比如:

1 2 3 4 5(编号1)
5 1 2 3 4(编号2)
4 5 1 2 3(编号3)
3 4 5 1 2(编号4)
2 3 4 5 1(编号5)
1 2 3 4 5//嘿嘿，转回来了！跟第1行 一样！

构造一下序列： 1 2 3 4 5 1 2 3 4 5 (其实就是在后面添了一圈！）

来对比:这个序列前5个数就是编号1,5~9是编号2,类推....

所以说就求个前缀和！（在后面添一圈的前缀和）

代码献上：

#include<bits/stdc++.h>
using namespace std;
long long Read(){
	char c=' ';
	long long f=1;
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	long long x=0;
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
long long n,m,a[200005];
long long sum[200005];
long long b[200005];
long long x[200005];
long long ans=1;
int main(){
	cin>>n>>m;
	for(long long i=1;i<=n;i++){
		a[i]=Read();
		a[i+n]=a[i];//在后面添加一圈
	}
	for(long long i=1;i<2*n;i++){
		sum[i]=sum[i-1]+(a[i]^a[i+1]);//求一个前缀和！
	}
	//cout<<endl;
	/*
	for(long long i=1;i<2*n;i++){
		cout<<sum[i]<<' ';
	}
	cout<<endl;
	*/
	for(long long i=1;i<=n;i++){
		if(i==1){
			b[i]=sum[n-1];
		} 
		else if(i!=1){
			b[i]=sum[n+i-2]-sum[i-2]-(a[(n-i+1)]^a[(n-i+2)]);//分别算出编号1,编号2等等的值
		}
	}
	/*
	for(long long i=1;i<=n;i++){
		cout<<b[i]<<' ';
	}
	cout<<endl;
	*/
	
	for(long long i=1;i<=m;i++){
		cin>>x[i];
		
	}
	cout<<sum[n-1]<<' ';
	for(long long i=1;i<=m;i++){
		//cin<<x[i];
		ans=ans+x[i];
		if(ans%n==0){
			cout<<b[n]<<' ';
		}
		else{
			cout<<b[ans%n]<<' ';
		}
	}
} 

点个赞再走！

还有就是，我这个代码比较土，建议看看官方题解.