CSP历年复赛题-P2671 [NOIP2015 普及组] 求和

原题链接：https://www.luogu.com.cn/problem/P2671

题意解读：找到所有符合条件的三元组，累加三元组的分数，结果对10007取模。

解题思路：

仔细读题，并分析数据规模，1~4个数据点可以通过O(n^2)复杂度解决，也就是枚举法。

1、枚举法

要求x < y < z,y − x = z − y，移项可得x + z = 2 * y，并且color[x] = color[z]

只需要枚举所有的x，z（x < z)，然后判断是否符合以下条件：

color[x] = color[z]，x + z是偶数，y = (x + z) / 2不超过n 

如果符合条件，即可计算分值，累加到ans

最后输出ans即可。

50分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005, MOD = 10007;
int n, m, ans;
int num[N], color[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> num[i];
    }
    for(int i = 1; i <= n; i++)
    {
        cin >> color[i];
    }
    
    for(int x = 1; x < n; x++)
    {
        for(int z = x + 1; z <= n; z++)
        {
            if(color[x] == color[z] && (x + z) % 2 == 0 && (x + z) / 2 <= n)
            {
                ans += ((x + z) % MOD) * ((num[x] + num[z]) % MOD);
                ans %= MOD;
            }
        }
    }
    cout << ans;

    return 0;
}

2、推公式

根据以上分析得知，x + z = 2 * y，所以x+z是偶数，x、z必须同奇或者同偶且颜色相同

为了缩减枚举的范围，可以把数据按照颜色分组，每种颜色再分成奇数、偶数

一共有m种颜色，因此一共可以分成m * 2组

这样，每一组里任意两个数都可以组成有效的x，z

设每组里的元素编号为idx[i]，元素数字为num[i]，该组一共有n个元素

则这个组的总的分数为：

(idx[1]+idx[2])*(num[1]+num[2]) + (idx[1]+idx[3])*(num[1]+num[3]) + ... + (idx[1]+idx[n])*(num[1]+num[n]) +

(idx[2]+idx[3])*(num[2]+num[3]) + (idx[2]+idx[4])*(num[2]+num[4]) + ... + (idx[2]+idx[n])*(num[2]+num[n]) + 

(idx[3]+idx[4])*(num[3]+num[4]) + (idx[3]+idx[5])*(num[3]+num[5]) + ... + (idx[3]+idx[n])*(num[3]+num[n]) +

...+

(idx[n-1]+idx[n])*(num[n-1]+num[n])

提取共同的idx因子之后：

idx[1]*(num[1]+num[2]+num[1]+num[3]+num[1]+num[4]+...+num[1]+num[n]) + 

idx[2]*(nun[1]+num[2]+num[2]+num[3]+num[2]+num[4]+...+num[2]+num[n]) +

idx[3]*(num[1]+num[3]+num[2]+nun[3]+num[3]+num[4]+...+num[3]+num[n]) +

...+

idx[n]*(num[1]+num[n]+num[2]+num[n]+num[3]+num[n]+...+num[n-1]+num[n])

进一步合并：

idx[1]*((n-1)*num[1]+num[2]+num[3]...+num[n]) + 

idx[2]*((n-1)*num[2]+num[1]+num[3]+...+num[n]) +

idx[3]*((n-1)*num[3]+num[1]+num[2]+...+num[n]) + 

...+

idx[n]*((n-1)*num[n]+num[1]+num[2]+...+num[n-1])

进一步合并：

idx[1]*((n-2)*num[1]+num[1]+num[2]...+num[n]) + 

idx[2]*((n-2)*num[2]+num[1]+num[2]+...+num[n]) +

idx[3]*((n-2)*num[3]+num[1]+num[2]+...+num[n]) + 

...+

idx[n]*((n-2)*num[n]+num[1]+num[2]+...+num[n])

可以写成：

idx[1]*((n-2)*num[1]+∑num[i]) + 

idx[2]*((n-2)*num[2]+∑num[i]) +

idx[3]*((n-2)*num[3]+∑num[i]) + 

...+

idx[n]*((n-2)*num[n]+∑num[i])

进一步转为：(n-2) * (idx[1]*num[1] + idx[2]*num[2] +...+ idx[n]*num[n]) + (idx[1]+idx[2]+...+idx[n])*∑num[i]

因此，需要提前计算出每一个编号-数字所在分组的元素个数，以及分组所有数字之和

可以设cnt[i][0]记录颜色i的编号偶数组的元素个数，cnt[i][1]记录颜色i的编号奇数组的元素个数

设sum[i][0]为颜色i编号偶数组的元素数字之和，sum[i][1]为颜色i的编号奇数组的元素数字之和

枚举一次每一个格子的颜色，提前预计算cnt、sum

再枚举每一个编号，代入上面公式，累加计算结果即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005, MOD = 10007;
int n, m, ans;
int num[N], color[N];
int cnt[N][2], sum[N][2];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> num[i];
    }
    for(int i = 1; i <= n; i++)
    {
        cin >> color[i];
        cnt[color[i]][i % 2]++;
        sum[color[i]][i % 2] += num[i];
        sum[color[i]][i % 2] %= MOD;
    }
    
    for(int i = 1; i <= n; i++)
    {
        ans += (cnt[color[i]][i % 2]-2) % MOD * i % MOD * num[i] % MOD+ i % MOD * sum[color[i]][i % 2] % MOD;
        ans %= MOD;
    }
    cout << ans;

    return 0;
}