题目链接：https://www.luogu.org/problemnew/show/P2671
这是noip2015普及组的第三题，谁说的普及组的题就一定水的不行，这道题就比较有意思的
这道题的暴力想法就是双重循环寻找所有情况
但是这会爆时间的
--------------------------
做这题，需要找到一个结论
y-x=z-y的意思其实是x+z是偶数，也就是x,z是同奇偶的
这个结论有了当然就可以暴力了，虽然不能过
正解的思路
我们首先对每一个数来查找他的贡献。。。
但是单纯的查找贡献可能就和暴力一样了，所以我们针对第z个数，查找在他之前的数，和他配对后对答案的贡献。因为这样还是一定是可以达到目标配对数，不重不漏
对于一组x,z(1<=x<z)，z的贡献是(xi+z)*(num[xi]+num[z])
然后z的总贡献就是Σ((xi+z)*(num[xi]+num[z]))其中xi满足xi和z同奇偶并且颜色相同
把这个式子打开就是
Σ(xi*num[i])+Σ(xi)*num[z]+Σ(num[xi])*z+count*z*num[z]
所以正解其实就是不断的加上这个式子
接下来一个问题就是如何储存这些Σ。。。
当然很容易想到的就是前缀和了
我们定义st[w1][w2][4]数组
w1为0表示偶数，1表示奇数
w2表示颜色
最后那一维：
0 表示奇偶颜色相同的情况下，满足条件的个数
1 表示奇偶颜色相同的情况下，满足条件的数的序号和
2 表示奇偶颜色相同的情况下，满足条件的数的价值和
3 表示奇偶颜色相同的情况下，满足条件的数的（价值*序号）的和
这是一个暴力打法，部分分
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<iostream>
5 #include<cmath>
6 #include<cstdlib>
7 #define maxn 100005
8 #define mod 10007
9 using namespace std;
10
11 int num[maxn],col[maxn];
12 int n,x,z,m,ans;
13
14 int main(){
15 cin>>n>>m;
16 for(int i=1;i<=n;i++){
17 cin>>num[i];
18 }
19 for(int i=1;i<=n;i++)cin>>col[i];
20 for(int i=1;i<=n;i++){
21 for(int j=i+2;j<=n;j+=2){
22 if(col[i]==col[j]){
23 ans=(ans+(((i+j)%mod)*((num[i]+num[j]))%mod)%mod)%mod;
24 }
25 }
26 }cout<<ans;
27 }
这是AC的前缀和版本
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<iostream>
5 #include<cstdlib>
6 #include<cmath>
7 #include<queue>
8 #define maxn 100005
9 #define mod 10007
10 #define ll long long
11 using namespace std;
12
13 int st[4][maxn][6];
14 int col[maxn],num[maxn],n,m;
15 ll ans;
16
17 int read() {
18 int xx=0,ff=1;char ch=getchar();
19 while(ch<'0'||ch>'9') {if(ch=='-')ff=-1;ch=getchar();}
20 while(ch>='0'&&ch<='9') {xx=xx*10+ch-'0';ch=getchar();}
21 return xx*ff;
22 }
23
24 int main() {
25 n=read();
26 m=read();
27 for(int i=1; i<=n; i++)num[i]=read()%mod;
28 for(int i=1; i<=n; i++)col[i]=read();
29 for(int i=1; i<=n; i++) {
30 int w1=i%2,w2=col[i];
31 int x=i%mod,v=num[i]%mod;
32 int a,b,c,d;
33 //同类数量 同类的序号和 同类的价值和 同类的价值*序号和
34 a=st[w1][w2][0]%mod;b=st[w1][w2][1]%mod;c=st[w1][w2][2]%mod;d=st[w1][w2][3]%mod;
35 st[w1][w2][0]++; st[w1][w2][0]%=mod;
36 st[w1][w2][1]+=x; st[w1][w2][1]%=mod;
37 st[w1][w2][2]+=v; st[w1][w2][2]%=mod;
38 st[w1][w2][3]+=x*v%mod; st[w1][w2][3]%=mod;
39 ans=(ans%mod+d%mod)%mod;
40 ans=(ans%mod+((a*x%mod)*v)%mod)%mod;
41 ans=(ans%mod+(b*v)%mod)%mod;
42 ans=(ans%mod+(c*x)%mod)%mod;
43 }
44 printf("%lld",ans);
45 }