前缀和（Pro Max）

scguo · 2024-07-22 13:55:19 · 算法·理论

这次，我们继续来讲前缀和的进阶应用 。

P3131

• 这题的前缀和采用边走边模，实现获得余数，然后写出两个数组 L 和 R ，分别代表从左往右的余数出现位置 。

• 最后答案为： max（R_i - L_i） 。

注意！

$L_0=0$ ！！！ $L_0=0$ ！！！

Code：

#include<bits/stdc++.h>
using namespace std;
int sum[100005],n,a[100005],l[105],r[105];
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        sum[i]=(sum[i-1]+a[i])%7;
    }
    for(int i=1;i<=n;++i)
    {
        if(!l[sum[i]]) l[sum[i]]=i;
    }
    for(int i=n;i>=1;--i)
    {
        if(!r[sum[i]]) r[sum[i]]=i;
    }
    int mx=-1e9;
    l[0]=0;
    for(int i=0;i<=6;++i)
    {
        mx=max(mx,r[i]-l[i]);
    }
    cout<<mx;
    return 0;
}

P8649 k 倍区间

• 和上一题差不多，不过这题是用一个桶来标记出现过几次，然后加它们加起来，注意，是在加完后再将 vis_{sum_i} 加一 。

Code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k,a[100005];
int sum[100005];
int vis[100005];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        sum[i]=(sum[i-1]+a[i])%k;
    }
    vis[0]=1;
    ll ans=0;
    for(int i=1;i<=n;++i)
    {
        ans+=vis[sum[i]];
        vis[sum[i]]++;
    }
    cout<<ans;
    return 0;
}

CF466C Number of Ways

• 我们先统计出数组内所有数字的和，如果不是 3 的倍数，那么一定不合法，直接输出 0 。

• 如果合法，假设枚举到的前 i 个数的和为 sum （数字总和），那么剩下的一定是 \displaystyle \frac{sum \times 2}{3} 。

• 我们先用一个前缀和算出前 i 个数的和 。 然后再用一个前缀和统计出前 i 个前缀和中和为 \displaystyle \frac{sum \times 2}{3} 的数量 。

• 最后从 1 枚举到 n-1 ，看看有多少个前缀和（第一个）等于 \displaystyle \frac{sum}{3} ，如果找到了一个，就将最后的答案加上 pre_{n-1} - pre_i （这里的 pre 是第二个前缀和） ，最后输出 。

Code：

#include<bits/stdc++.h>
#define short long long
using namespace std;
short n,a[1000005],sum[1000005],pre[1000005],cnt;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(short i=1;i<=n;++i)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        cnt+=a[i];
    }
    if(cnt%3!=0)
    {
        cout<<0;
        return 0;
    }
    for(short i=1;i<=n;++i)
    {
        pre[i]=pre[i-1]+(sum[i]==(cnt*2/3));
    }
    short ans=0;
    for(short i=1;i<n;++i)
    {
        if(sum[i]==cnt/3)
        {
            ans+=(pre[n-1]-pre[i]);
        }
    }
    cout<<ans;
    return 0;
}

The End.