求和-题解

Azuree · 2019-06-25 15:58:06 · 题解

查看原题请戳这里

前言
没有什么是吸一口氧气解决不了的，如果有，就再吸一口……
算法
朴素暴力
首先，看到这道题的第一时间就想到了一个暴力的方法——枚举每一个x点和x与z的间距（只需要枚举偶数间接即可，否则无法满足y−x=z−y）。然而，这个算法是O(n^2)的，我们无法承受这个时间复杂度。
优化暴力
思路
其实感觉还是挺慢的，需要吸一口氧气才能过 由于朴素的暴力需要枚举每一个起点和间接，但是如果我们对数据排一下序呢？
是的，这样我们就可以不必枚举每一个间距了。但是呢，由于这个方法本质还是一个暴力，我们在统计答案的时候速度会比较慢qwq

那么，我们怎么去进行排序呢？
我们可以发现，y的值对于答案是没有任何影响的，只要x和z的编号同为奇数或偶数，那么就一定存在一个y使得y−x=z−y。所以，我们在排序时的关键字的优先级应该时这样的：

1. 颜色
2. 序号的奇偶（可以偶数在前，也可以奇数在前，但必须保证统一颜色的奇数和偶数编号的点是挨着的）
3. 序号的大小（感觉这个其实没什么用qwq）

然后我们只需要枚举每一个颜色和奇偶均相同的区间并统计答案即可

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register
#define mod 10007

using namespace std;

int read()
{
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

struct number{
    ll num,col,x;
}a[100005];

ll n,m,s,ans;

int mysort(number a, number b){
    if(a.col != b.col) return a.col < b.col;
    if(a.num % 2 == b.num % 2) return a.num < b.num;
    return a.num % 2 < b.num % 2;
}

int main()
{
    n = read(); m = read();
    for(re int i = 1; i <= n; i++) a[i].num = i;
    for(re int i = 1; i <= n; i++) a[i].x = read();
    for(re int i = 1; i <= n; i++) a[i].col = read();
    sort(a + 1, a + n + 1, mysort);
    int i = 1;
    while(i <= n){
        s = i;
        while(a[i].col == a[i + 1].col && a[i].num % 2 == a[i + 1].num % 2 && i < n) i ++;
        for(int j = s; j < i; j++)
            for(int k = j + 1; k <= i; k++)
                ans = (ans + (a[j].num + a[k].num) * (a[j].x + a[k].x)) % mod;
        i++;
    }
    printf("%lld\n",ans);
    return 0;
}