作业之考试n

【NOIP2015普及组】求和


#include<bits/stdc++.h>
using namespace std;//所有在奇/偶数项的同一颜色可以满足条件
int l,m,n,ha[100010],c[100010];
int kao[100010],hahaha=10007;
void sf(){
//((A+B)C)%D=(((A+B)%D)(C%D))%D
for(int z=1;z<kao[0];++z){
for(int y=1;y+z<=kao[0];++y){
l+=(((kao[y]+kao[y+z])%hahaha)*((ha[kao[y]]+ha[kao[z+y]])%hahaha));
l%=hahaha;
}
}
}
int main(){
// freopen(“sum.in”,“r”,stdin);
// freopen(“sum.out”,“w”,stdout);
scanf("%d%d",&n,&m);
for(int z=1;z<=n;++z) scanf("%d",&ha[z]);
for(int z=1;z<=n;++z) scanf("%d",&c[z]);
for(int z=1;z<=n;++z){
if(c[z]){
kao[0]=0;
kao[++kao[0]]=z;
for(int y=z+2;y<=n;y+=2)
if(c[y]==c[z]){
kao[++kao[0]]=y;
c[y]=0;
}
c[z]=0;
sf();
}
}
printf("%d",l);
}
假如序号为zn,那么颜色相同的全部为奇/偶数的z1,z2,~~~，zn能够两两构成（若1<=i<j<=n,那么zi,(zi+zj)/2和zj为三元组)题目说的三元组；
对保存颜色的c[z]进行遍历，找到过的清0避免再次计算；
kao[0]保存颜色相同，序号全为奇/偶的元素的个数。kao[1]到kao[kao[0]]为元素序号；
因为kao中元素能够两两构成三元组，分数为序号和乘以序号对应的值。(数组kao中)若y为zi,y+z表示zj;则i与j的差值最大为kao[0]-1;按程序就可以把每种组合算出来了。