CP002798 [NOIP2015 普及组] 求和 题解

前言

此篇题解不是正解，如果想看正解请前往其他题解。

题目传送门

可能更好的阅读体验

别说我是抄袭的，同步在洛谷的文章的作者也是我。

为什么题解中没有一个是说明解题步骤的啊 QWQ

讲解

题都看了吧，第一个反应是暴力求解。

我是这样暴力的：先输入数据，在输入颜色的时候就顺便枚举到了 $z$ 了，然后从后往前遍历，考虑到 $y − x = z − y$ 这个条件，说明了要么 $x$ 和 $z$ 都是奇数，要么 $x$ 和 $z$ 都是偶数，所以说从后往前遍历的时候是依次减二的。

$50$ 分代码：

#include <iostream>
#include <vector>
using namespace std;
int main(){
	int n,m;
	cin >> n >> m;
	vector<pair<int,int>> a;
	for (int i=0;i<n;++i){
		int t;
		cin >> t;
		a.emplace_back(t%10007,0);
	}
	long long ans=0;
	for (int i=0;i<n;++i){
		cin >> a[i].second;
		for (int j=i-2;j>=0;j-=2){
			if (a[i].second==a[j].second){
				ans+=((i+1)%10007+(j+1)%10007)*(a[i].first+a[j].first)%10007;
				ans%=10007;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

我们考虑优化，不丢弃只遍历 $x$ 和 $z$ 的思路，把所有颜色相同的每一个下标放在一个地方，当输入到这个颜色的时候遍历之前跟自己同一个颜色的格子，然后进行是否奇偶性相同的判断，如果符合就加在一起。

$80$ 分代码：

#include <iostream>
#include <vector>
using namespace std;
int main(){
	int n,m;
	cin >> n >> m;
	vector<int> a(n+1);
	vector<vector<int>> qwq(m+1);
	for (int i=1;i<=n;++i){
		cin >> a[i];
	}
	long long sm=0;
	for (int i=1;i<=n;++i){
		int t;
		cin >> t;
		for (const auto &item : qwq[t]){
			if ((item+i)%2==0){
				sm+=((i+item)%10007)*(a[i]+a[item])%10007;
				sm%=10007;
			}
		}
		qwq[t].emplace_back(i);
	}
	cout<<sm<<endl;
	return 0;
}

继续在上一步优化下想，因为每次都要遍历一遍又要判断，会多遍历很多次，于是我们将奇数和偶数区分开来放，每次就省去了判断的过程。

$100$ 分代码：

#include <iostream>
#include <vector>
using namespace std;
int main(){
	int n,m;//定义。
	scanf("%d%d",&n,&m);//输入。
	vector<int> a(n+1);//数字。 
	vector<pair<vector<int>,vector<int>>> v(m+1);//第一个放奇数的下标，第二个放偶数的下标。 
	for (int i=1;i<=n;++i){//输入每一个格子上的数字。
		scanf("%d",&a[i]);//输入。
	}
	int sm=0;//答案。
	for (int i=1;i<=n;++i){//边输入边操作。
		int t;//定义颜色。
		scanf("%d",&t);//输入每一位的颜色。
		if (i%2==1){//如果位数是奇数。
			for (const auto &item : v[t].first){//遍历。
				sm+=((i+item)%10007)*(a[i]+a[item])%10007;//计算。
				sm%=10007;//再模一次。
			}
			v[t].first.emplace_back(i);//添加。
		}else{//如果位数是偶数。
			for (const auto &item : v[t].second){//遍历。
				sm+=((i+item)%10007)*(a[i]+a[item])%10007;//计算。
				sm%=10007;//再模一次。
			}
			v[t].second.emplace_back(i);//添加。
		}
	}
	printf("%d\n",sm);//输出。
	return 0;
}

时间复杂度：神仙复杂度，计算是 $O(1)$ 的，所以优化过后较为快。

幸好ACGO的评测机较为强大，没有卡我常，在洛谷上要卡我常，所以在洛谷上要开O2。

踩着点过的，好像是960ms左右。