线上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;
}