NOIP2015普及组 T3 求和

80pts

利用 y - x = z - y，我们能够发现x和z应该是同奇同偶的，我们把每个颜色，分成奇数、偶数两类，然后分别进行枚举，枚举选两个点即可，局部暴力

这样可以T3获得80pts的好成绩

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10, mod = 10007;

int n, m, number[N], color[N];
vector<int> odd[N], even[N];
ll ret;

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &number[i]);
    for (int i = 1; i <= n; i++){
        scanf("%d", &color[i]);
        if (i & 1) odd[color[i]].push_back(i);
        else even[color[i]].push_back(i);
    }

    for (int idx = 1; idx <= m; idx++){
        if ((int)odd[idx].size() >= 2){
            int len = (int)odd[idx].size();
            for (int i = 0; i < len; i++)
                for (int j = i + 1; j < len; j++){
                    ret += 1ll * (odd[idx][i] + odd[idx][j]) * 
                           (number[odd[idx][i]] + number[odd[idx][j]]);
                    if (ret >= mod) ret %= mod;
                }
        }


        if ((int)even[idx].size() >= 2){
            int len = (int)even[idx].size();
            for (int i = 0; i < len; i++)
                for (int j = i + 1; j < len; j++){
                    ret += 1ll * (even[idx][i] + even[idx][j]) * 
                        (number[even[idx][i]] + number[even[idx][j]]);
                    if (ret >= mod) ret %= mod;
                }
        }
    }

    cout << ret << '\n';

    return 0;
}

100pts

局部暴力，如果某个颜色的分类，比较大，就会T掉。那么，当知道了这个规律后，如何降低时间复杂度，进行优化呢。我们可以继续观察这个选取两个的暴力枚举部分。

具体观察过程，需要在草稿纸上，推导。

下面举例这些分组，以某个颜色的奇数点分组为例
比如[1, 3] ，求和是(1+3)*(n1+n3)
比如[1, 3,5]，求和是(1+3)*(n1+n3), (1+5)*(n1+n5), (3+5)*(n3+n5)
比如[1, 3, 5, 7], 求和是...

展开，把1提出来，会发现 关于1的部分，是 1 * ((num - 2) * n1 + {n1 + n3 + ...+n5})
推广一下
i * ((num - 2) * n_i + {sum of n_i})

这样维护出来，每个分类的个数，还有总和，就可以O(1)的时间，计算得出

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10, mod = 10007;

int n, m, number[N], color[N];
vector<int> odd[N], even[N];
ll cnt[N][2], sum[N][2];
ll ret;

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &number[i]);
    for (int i = 1; i <= n; i++){
        scanf("%d", &color[i]);

        int j = color[i];
        cnt[j][i % 2]++;
        sum[j][i % 2] += number[i]; 
        sum[j][i % 2] %= mod;
    }

    for (int i = 1; i <= n; i++){
        int j = color[i];
        if (cnt[j][i % 2] >= 2){
            ret += 1ll * i * ((cnt[j][i % 2] - 2) * number[i] + sum[j][i % 2]);
            ret %= mod;
        }
    }

    cout << ret << '\n';

    return 0;
}