站长百科 NOIP2015 普及组 洛谷P2671 求和 （数学） 正文

NOIP2015 普及组 洛谷P2671 求和 （数学）

2022-12-01,,,

一道数学题......

采用分组的思想，我们要统计答案的数对满足两个条件：同奇偶，同颜色。所以可以按这两个要求分组。

然后就是分组处理了，对于每组（有k个数），这里面的任意两对数都是满足条件的，可推出下面的公式：

x[k]*(y[k]*(k-2)+y[1]+y[2]+......+y[k])

x[]是数值，y[]是下标。

公式推导还是好推的，自己在草稿纸上列出式子，用数学方式处理。

由此可以得到代码：

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int N=1e5+10;

 4 int s[N][2],sum[N][2],c[N],x[N];

 5 int n,m,ans;

 6 //推公式优化到n

 7 int main(){

 8     scanf("%d%d",&n,&m);

 9     for(int i=1;i<=n;i++)

10         scanf("%d",&x[i]);

11     for(int i=1;i<=n;i++){

12         scanf("%d",&c[i]);

13         s[c[i]][i%2]++;//求出这个分组的个数

14         sum[c[i]][i%2]=(sum[c[i]][i%2]+x[i])%10007;//求这个分组中的累加和

15     }

16     for(int i=1;i<=n;i++)

17         ans=(ans+i*((s[c[i]][i%2]-2)*x[i]%10007+sum[c[i]][i%2]))%10007;//推出来的公式

18     cout<<ans;

19 }

这道题是容易想到暴力的，但n2过不了，按照上面的方式优化后，可以到n。

NOIP2015 普及组 洛谷P2671 求和 （数学）的相关教程结束。

《NOIP2015 普及组 洛谷P2671 求和 （数学）.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!