[NOIP2015普及组]求和

· · 题解

分析

20分做法

看完这题，第一想法当然是无脑暴力啦...直接枚举x,y,z,看是否满足条件即可。算法复杂度为O(N^3)。[代码就算了]

这样就可得20分了。当然，如果你想用更高级的算法不开long long也是可以的。

40分做法

可以直接枚举x，z的值，通过条件(1)求出y。再看是否满足条件。算法复杂度为O(N^2)。

40~50分做法

仍然是枚举x,z的值，但可以先分析x+z=2*y的奇偶性，因为xyz是整数，因此2y是2的倍数，因此x,z必然都为偶数或奇数，因此可以分奇偶性进行枚举，此时这个三元组即可不考虑y值的大小，即为当(i%2==1)枚举前面奇数序列相同的颜色进行算分数即可，算法复杂度为O(N^2/2)。

100分做法

通过上面的观察我们可以发现倒回去算前面的分数可能比较浪费时间，因此，我们采用数学的方法来优化此题(放心，很简单的)。

=============科目分割线==============

(这里只说明了i%2==1的情况，i%2==0是完全相似的)

令S(i,j)为(i,i+j/2,j)所组成的三元组的分数(x+z)*(number_x+number_z)

$colornum(color_i)$为对于一个格子i前方所有与之相同颜色且同奇偶性的格子的g个数 因此，对于一个格子K，有$Score_k=S(1,k)+S(3,k)+...+S(colornum(color_k,k-1),k)

=(1+k)(number_1+number_k)+...+(colornum(color_k)+k)(number(colornum(color_k))+number_k)

=number_1+number_k×1+number_1×k+number_k×k+...+number(colornum(color_k))×colornum(color_k)

+number(colornum(color_k))×number_k+number(colornum(color_k))k+number_kk

=(number_1+3×number_3+...+ number(colornum(color_k))×colornum(color_k)

+k×(number_1+number_3+...+number(colornum(color_k))) +number_k×(1+3+...+colornum(color_k))+colornum(color_k)k×number_k

============科目分割线(打起来好累233...)=============

发现了什么，我们可以记录不同颜色的1×number_1+3×number_3+...+number(colornum(color_k))×colornum(color_k),number_1+number_3+...+number(colornum(color_k)),1+3+...+colornum(color_k)的值，从而快速算出总分数。这样就可以轻易AK了~。算法复杂度O(n)

最后记得将结果不断%10007(是的，不断%%%%%%).

然后所有数都开long long 就可以过了~.

代码实现

我知道你们只看这个...

放个好理解的版本。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
using namespace std;
long long n,m,num[100005],cont[2][100005],cl;
long long sum1[3][100005],sum2[3][100005];
long long ans;
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&num[i]);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&cl);
        if(i%2==1)
        {
            ans=(ans+sum1[0][cl]%10007+i*sum1[1][cl]%10007+num[i]*sum1[2][cl]%10007+cont[0][cl]*i*num[i]%10007)%10007;
            sum1[0][cl]=(sum1[0][cl]+num[i]*i)%10007;
            sum1[1][cl]=(sum1[1][cl]+num[i])%10007;
            sum1[2][cl]=(sum1[2][cl]+i)%10007;
            cont[0][cl]++;
        }
        else
        {
            ans=(ans+sum2[0][cl]%10007+i*sum2[1][cl]%10007+num[i]*sum2[2][cl]%10007+cont[1][cl]*i*num[i]%10007)%10007;
            sum2[0][cl]=(sum2[0][cl]+num[i]*i)%10007;
            sum2[1][cl]=(sum2[1][cl]+num[i])%10007;
            sum2[2][cl]=(sum2[2][cl]+i)%10007;
            cont[1][cl]++;
        }
    }
    printf("%lld",ans%10007);
}