P2671 [NOIP2015 普及组] 求和 题解

· · 个人记录

P2671 [NOIP2015 普及组] 求和 题解

前言

此篇题解不是正解，如果想看正解请前往其他题解。

题目传送门

可能更好的阅读体验

讲解

题都看了吧，第一个反应是暴力求解。

我是这样暴力的：先输入数据，在输入颜色的时候就顺便枚举到了 z 了，然后从后往前遍历，考虑到 y − x = z − y 这个条件，说明了要么 x 和 z 都是奇数，要么 x 和 z 都是偶数，所以说从后往前遍历的时候是依次减二的。

代码：

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    vector<pair<int,int>> a;
    for (int i=0;i<n;++i){
        int t;
        cin >> t;
        a.emplace_back(t%10007,0);
    }
    long long ans=0;
    for (int i=0;i<n;++i){
        cin >> a[i].second;
        for (int j=i-2;j>=0;j-=2){
            if (a[i].second==a[j].second){
                ans+=((i+1)%10007+(j+1)%10007)*(a[i].first+a[j].first)%10007;
                ans%=10007;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

氧气都救不了我。

开了氧气都是只拿了一半的分。

我们考虑优化，不丢弃只遍历 x 和 z 的思路，把所有颜色相同的每一个下标放在一个地方，当输入到这个颜色的时候遍历之前跟自己同一个颜色的格子，然后进行是否奇偶性相同的判断，如果符合就加在一起。

代码：

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    vector<int> a(n+1);
    vector<vector<int>> qwq(m+1);
    for (int i=1;i<=n;++i){
        cin >> a[i];
    }
    long long sm=0;
    for (int i=1;i<=n;++i){
        int t;
        cin >> t;
        for (const auto &item : qwq[t]){
            if ((item+i)%2==0){
                sm+=((i+item)%10007)*(a[i]+a[item])%10007;
                sm%=10007;
            }
        }
        qwq[t].emplace_back(i);
    }
    cout<<sm<<endl;
    return 0;
}

氧气仍然救不了我。

继续在上一步优化下想，因为每次都要遍历一遍又要判断，会多遍历很多次，于是我们将奇数和偶数区分开来放，每次就省去了判断的过程。

代码：

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n,m;//定义。
    scanf("%d%d",&n,&m);//输入。
    vector<int> a(n+1);//数字。 
    vector<pair<vector<int>,vector<int>>> v(m+1);//第一个放奇数的下标，第二个放偶数的下标。 
    for (int i=1;i<=n;++i){//输入每一个格子上的数字。
        scanf("%d",&a[i]);//输入。
    }
    int sm=0;//答案。
    for (int i=1;i<=n;++i){//边输入边操作。
        int t;//定义颜色。
        scanf("%d",&t);//输入每一位的颜色。
        if (i%2==1){//如果位数是奇数。
            for (const auto &item : v[t].first){//遍历。
                sm+=((i+item)%10007)*(a[i]+a[item])%10007;//计算。
                sm%=10007;//再模一次。
            }
            v[t].first.emplace_back(i);//添加。
        }else{//如果位数是偶数。
            for (const auto &item : v[t].second){//遍历。
                sm+=((i+item)%10007)*(a[i]+a[item])%10007;//计算。
                sm%=10007;//再模一次。
            }
            v[t].second.emplace_back(i);//添加。
        }
    }
    printf("%d\n",sm);//输出。
    return 0;
}

氧气终于救我了。

注：这个代码必须要开氧气才能过，不知道是因为卡常还是本身代码问题，不开氧气有两个点过不去。