在我的博客查看效果更佳
思路很简单，特别适合我这总菜鸡
先读入，在从前往后扫一遍，每次把i位置以前的同颜色的坐标记到vector数组里（每一种颜色用一个vector），到后面就可以直接用了。
记得开long long
#include<bits/stdc++.h>
using namespace std;
long long read() {
long long x=1,ans=0;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')
x*=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
ans=ans*10+ch-48;;
ch=getchar();
}
return x*ans;
}
const long long N=100005;
long long n,m,num[N],col[N];
vector<long long> w[N];
int main() {
n=read();m=read();
for(long long i=1;i<=n;i++)
num[i]=read();
for(long long i=1;i<=n;i++)
col[i]=read();
long long ans=0;
for(long long i=1;i<=n;i++) {
for(long long j=0;j<w[col[i]].size();j++) {
long long k=w[col[i]][j];
if((i-k)%2) continue;
ans=(ans+(i+k)*(num[i]+num[k]))%10007;
}
w[col[i]].push_back(i);
}
printf("%lldn",ans);
return 0;
}
别急着抄代码，这个代码只有70分（TLE）
咳咳咳，还有一个常数优化
我们可以看到下面这段代码很烦人：
if((i-k)%2) continue;
那么如果(i-k)%2==1的话有什么性质呢？
当(i-k)%2==1时，i与k的奇偶性一样
证明：
一个奇数可以表示成
2*a+1;
若i和k均是奇数
那么
(i-k)%2=(2a+1-(2b+1))%2
化简得：
(2a-2b)%2
而2
a和2b均是偶数，两个偶数之差也是偶数（顺便把i，k均是偶数的情况也包括进去了）
证明完毕
代码：
#include<bits/stdc++.h>
using namespace std;
long long read() {
long long x=1,ans=0;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')
x*=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
ans=ans*10+ch-48;;
ch=getchar();
}
return x*ans;
}
const long long N=100005;
long long n,m,num[N],col[N];
vector<long long> w[N][2];
int main() {
n=read();m=read();
for(long long i=1;i<=n;i++)
num[i]=read();
for(long long i=1;i<=n;i++)
col[i]=read();
long long ans=0;
for(long long i=1;i<=n;i++) {
for(long long j=0;j<w[col[i]][i%2].size();j++) {
long long k=w[col[i]][i%2][j];
// if((i-k)%2) continue;
// cout<<(i-k)%2<<' '<<i<<' '<<k<<' '<<i%2<<' '<<k%2<<endl;
ans=(ans+(i+k)*(num[i]+num[k]))%10007;
}
w[col[i]][i%2].push_back(i);
// cout<<i<<' '<<i%2<<endl;
}
printf("%lldn",ans);
return 0;
}
咳咳咳，80分，
吸口氧不就过去了嘛
