♐ CSP_J 组真题
2015年
3. 求和

线上OJ:

一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1971 (opens in a new tab)
AcWing:https://www.acwing.com/problem/content/465/ (opens in a new tab)

核心思想:

本题的约束条件有两个:
条件1、colorx = colorz
条件2、x、y、z的坐标满足 y − x = z − y(即 y 在 x 和 z 的中心位置)
第二个约束条件可以理解为, z 到 x 的距离是 y 到 x 的距离的两倍,所以对z暴力枚举时,步长为2的倍数

样例图

考场上如果暂时没有更好的想法,可以先把 暴力枚举 写出来。本题的暴力法比较简单,只需要枚举x和z,并且在 枚举z的时候考虑步长为2 即可(这样可以保证x和z中间一定有整数y,就不用再考虑y了)。这样可以快速拿到40%的分数。

解法一、暴力枚举(40%):
#include <bits/stdc++.h>
#define MOD 10007
using namespace std;
 
// 40% 暴力分
int main()
{
	int n, m, ans = 0;
	cin >> n >> m;
	
	int col[n+5], num[n+5];
	for(int i = 1; i <= n; i++) scanf("%d", &num[i]);
	for(int i = 1; i <= n; i++) scanf("%d", &col[i]);	
	
	for(int x = 1; x <= n; x++)
		for(int z = x + 2; z <= n; z += 2)	// 考虑x和z中间夹一个y,所以每次搜寻z时步长为2
		{
			if(col[x] == col[z])
				ans += (((x + z) % MOD) * ((num[x] + num[z]) % MOD)) % MOD;
		}
	
	printf("%d", ans % MOD);  // 最后一次别忘了除模
	return 0;
}