P2671 [NOIP2015 普及组] 求和(前缀和)-阿里云开发者社区

P2671 [NOIP2015 普及组] 求和(前缀和)

2023-07-11 105

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： P2671 [NOIP2015 普及组] 求和(前缀和)

1.描述：

一条狭长的纸带被均匀划分出了nn个格子，格子编号从11到nn。每个格子上都染了一种颜色c o l o r 用[1,m]当中的一个整数表示），并且写了一个数字n u m b e r

定义一种特殊的三元组：(x,y,z)，其中x,y,z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：

fefade5cc938f2bb5b3faff6d8979962_bdbe1703346349aa8719d3fd1f1bc3aa.png

1.xyz是整数 x

2.color x = color z

满足上述条件的三元组的分数规定为

整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以10,007所得的余数即可。

2. 输入：

第一行是用一个空格隔开的两个正整数n和m,n表纸带上格子的个数，m表纸带上颜色的种类数。

第二行有n用空格隔开的正整数，第i数字number表纸带上编号为i格子上面写的数字。

第三行有n用空格隔开的正整数，第i数字color表纸带上编号为i格子染的颜色。

f3096a334fdda82354b8ca17cdb1899c_f96dd08c9dea46afba0fba5ecee91938.png

3.输出：

一个整数，表示所求的纸带分数除以10007所得的余数。

4.样例输入：

15 4
5 10 8 2 2 2 9 9 7 7 5 6 4 2 4
2 2 3 3 4 3 3 2 4 4 4 4 1 1 1

5.样例输出：

6.题目大意：

找所有满足关系的三元对的贡献和

7.思路

80分思路：

所有的三元对与中间元素没什么关系，只要首尾元素满足同奇或同偶且颜色相同即可组对，把所有满足条件元素输入便输入边处理即可

80分代码 O( n*n )

最多 1e⁵ 种颜色，同种颜色 i 奇数放在 i * 2 - 1，偶数放在 i * 2

#include<bits/stdc++.h>
using namespace std;
//ios::sync_with_stdio(false);
const int N = 1e6+10; 
typedef long long ll;
int n,m;
struct node{
  ll num;
  ll n; 
  ll col;
}a[N];
const int p = 1e4+7;
vector<node>ve[N];
ll sum;
int main()
{
  ios::sync_with_stdio(false);
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    a[i].n=i;
    cin>>a[i].num;
  }
  for(int i=1;i<=n;i++)
  {
    cin>>a[i].col;
    if(a[i].n%2!=0)
    {
      ve[2*a[i].col-1].push_back(a[i]);
      int s=2*a[i].col-1;
      int t=ve[s].size()-1;
      for(int j=0;j<t;j++)
      {
        sum=(sum+((ve[s][j].n+ve[s][t].n)*(ve[s][j].num+ve[s][t].num)))%p;  
      }
    }
    else
    {
      ve[2*a[i].col].push_back(a[i]);
      int s=2*a[i].col;
      int t=ve[s].size()-1;
      for(int j=0;j<t;j++)
      {
        sum=(sum+((ve[s][j].n+ve[s][t].n)*(ve[s][j].num+ve[s][t].num)))%p;  
      }
    }
  }
  cout<<sum;
}

复杂度 O( n² ) 1e10，爆了

100分思路：O( n )

化简

那么不难发现，可以维护的东西出来了(有些东西是可以维护累加和(前缀和)的)，对于每种颜色的不同奇偶，我们可以维护一个

对应式子第一列

维护一个s u m x 数组

对应式子第二列的 x的和

维护一个 s u m n 数组

对应式子第三列的的和

维护一个c n t 数组

对应第四列的个数

一百分代码

#include<bits/stdc++.h>
using namespace std;
//ios::sync_with_stdio(false);
const int N = 3*1e5+10; 
typedef  long long ll;
int n,m;
ll num[N],col;
const int p = 10007;
ll sumx[N];
ll sumn[N];
ll sumxn[N];
ll cnt[N];
ll sum;
int main()
{
  ios::sync_with_stdio(false);
  cin>>n>>m;
  for(int i=1;i<=n;i++)  cin>>num[i];
  for(int i=1;i<=n;i++)
  {
    cin>>col;   
    if(i%2!=0)
    {
      int s=col*2-1;
      sum=(sum+sumxn[s]%p+sumx[s]*num[i]%p+sumn[s]*i%p+i*num[i]*cnt[s]%p)%p;
      sumxn[s]=(sumxn[s]+i*num[i])%p;
      sumx[s]=(sumx[s]+i)%p;
      sumn[s]=(sumn[s]+num[i])%p;
      cnt[s]++;
    }
    else
    {
      int s=col*2;
      sum=(sum+sumxn[s]%p+sumx[s]*num[i]%p+sumn[s]*i%p+i*num[i]*cnt[s]%p)%p;
      sumxn[s]=(sumxn[s]+i*num[i])%p;
      sumx[s]=(sumx[s]+i)%p;
      sumn[s]=(sumn[s]+num[i])%p;
      cnt[s]++;
    }
  }
  cout<<sum;
}

8.反思

一开始想出来第二种思路了，没开 long long 调了好久，还把思路又想了好几遍，没开 long long 只有四十分，从八十分到四十分，人傻了，纯纯nt，以后累加要取余的题一定要注意

1.开 long long

2.不断地 %%%%(进行取余)

3.可以用 ios::sync_with_stdio(false) 来加速，前缀和非常好的一道题

最后的最后，觉得写的还不错的，一定要点个赞留个言支持一下~~~