题解 P2671 【求和】

xukuan · 2018-10-24 12:55:02 · 题解

40分的的O(n^2)暴力：

#include<bits/stdc++.h>
#define ll long long
#define MOD 10007
using namespace std;

ll n,m,sum,number[100010],colour[100010];

int main(){
    scanf("%lld %lld",&n,&m);
    for(ll i=1; i<=n; i++) scanf("%lld",&number[i]);
    for(ll i=1; i<=n; i++) scanf("%lld",&colour[i]);

    for(ll i=1; i<=n; i++){//穷举x
        for(ll j=i+1; j<=n; j++){//穷举y
            ll k=2*j-i;//算出k
            if(j<k){//i一定小于j，所以不用判断
                if(colour[i]==colour[k]) sum=(sum+(i+k)*(number[i]+number[k]))%MOD;
            }
        }
    }
    printf("%lld",sum);
    return 0;
}

60分的代码：

#include<bits/stdc++.h>
#define ll long long
#define MOD 10007
using namespace std;

ll n,m,sum,Prev[100010];
struct node{
    ll number,colour,place;
}a[100010];

inline bool cmp(node a,node b){//按颜色和原位置排序
    if(a.colour==b.colour) return a.place<b.place;
    return a.colour<b.colour;
}

int main(){
    scanf("%lld %lld",&n,&m);
    for(ll i=1; i<=n; i++) scanf("%lld",&a[i].number);
    for(ll i=1; i<=n; i++) scanf("%lld",&a[i].colour);
    for(ll i=1; i<=n; i++) a[i].place=i;
    sort(a+1,a+1+n,cmp);
    for(ll i=1; i<=n; i++) Prev[a[i].place]=i;
    for(ll i=1; i<=n; i++){//穷举x
        for(ll k=i+1; k<=n; k++){//穷举z
            if((a[i].place+a[k].place)%2==1) continue;
            if(a[i].colour!=a[k].colour) break;
            ll j=Prev[(a[i].place+a[k].place)/2];//算出j
            if(a[i].place<a[j].place&&a[j].place<a[k].place) sum=(sum+(a[i].place+a[k].place)*(a[i].number+a[k].number))%MOD;
        }
    }
    printf("%lld",sum);
    return 0;
}

AC的代码：

本代码的关键在cmp函数

满足的条件：

1.xyz是整数,x<y<z,y-x=z-y

2.color[x]=color[z]

首先，(x+z)%2==0

那么，x和z的奇偶性相同

我们可以做一个排序，把这些东西排序起来，再穷举x和z并吸氧（O2优化），这样就过了！！！(一个点900ms-)

#pragma GCC optimize(2)//优化1：O2优化
#include<bits/stdc++.h>
#define ll long long
#define MOD 10007
using namespace std;

ll n,m,sum;
struct node{
    ll number,colour,place;
    //place代表原来的位置
}a[100010];

inline bool cmp(node a,node b){
    //比较方式：
    //1.按对2取余的结果从小到大
    //2.按颜色，颜色相同的放在一起
    //3.按位置从小到大
    if(a.place%2==b.place%2){
        if(a.colour==b.colour) return a.place<b.place;
        return a.colour<b.colour;
    }
    return a.place%2<b.place%2;
}

int main(){
    scanf("%lld %lld",&n,&m);
    for(ll i=1; i<=n; i++) scanf("%lld",&a[i].number);
    for(ll i=1; i<=n; i++) scanf("%lld",&a[i].colour);
    for(ll i=1; i<=n; i++) a[i].place=i;
    sort(a+1,a+1+n,cmp);

    for(ll i=1; i<=n; i++){//穷举x
        for(ll k=i+1; k<=n; k++){//穷举z
            if((a[i].place+a[k].place)%2==1) break;//求和取余的值已经不为0，说明之后的值都不为0，直接跳出
            if(a[i].colour!=a[k].colour) break;//颜色不同，跳出，理由同上
            //话说为什么要求j呢……
            sum=(sum+(a[i].place+a[k].place)*(a[i].number+a[k].number))%MOD;//数量增加
        }
    }
    printf("%lld",sum);
    return 0;
}