算法总结--前缀和进阶1

feizhu_QWQ · 2024-07-21 13:23:01 · 算法·理论

(｡･∀･)ﾉﾞ嗨，飞竹小课堂第13课开课喽！

好滴，今天我们来学习之前算法的进阶--前缀和进阶！
小前：打嫁豪，我四小前，今天我们来学前缀和。

前缀和，主要求解区间求和问题，运用预处理的思想，节省大量时间复杂度，题目一般为T组数据。
小前：说得好！

那么我们今天吃满前全席。
先来一道开胃的小炒牛肉

这道题我们有两种做（chi）法。
①因为他是一个环，所以我们把这个环复制一个拼起来，简称copy
这样方便判断这个答案在圆环的交界处。
②我们先用前缀和，把不考虑圆的答案找出来，在和过了交界线的答案作比较，思路较难。

代码过于简单，不做展示。

接着是剁椒腊肉
这道题看似就是把符合要求的字符数量加起来做前缀和，可这道题的翻译是真的la ji 有一个重要信息都没翻译出来：

那么我们只找范围内的满足01串的数量
不过为了满足l,r在范围内，我们先把l- -,r- -

代码比较简单，懒得做展示

子串牛肉
怎么说又是求解字串，O(n^2)的时间复杂度不能少一点！
同理，把范围内满足字串与b相等的数量前缀和，就阔以啦！

这道题有个特别恶心的地方，他的边界特特特特特别难受，得一发一发的WA:

代码还是展示一下吧：

#include<bits/stdc++.h>
using namespace std;
int sum[1000005];
int main()
{
    int n,m,t;
    cin>>n>>m>>t;
    string s;
    cin>>s;
    string x;
    cin>>x;
    s="#"+s;
    x="#"+x;
    for(int i=1;i<=n-m+1;i++)
    {
        int flag=1;
        for(int j=1;j<=m;j++)
        {
            if(s[i+j-1]!=x[j])
            {
                flag=0;
                break;
            }
        }
        sum[i]=sum[i-1]+flag;
    }
    for(int i=max(1,n-m+2);i<=n;i++) sum[i]=sum[i-1];
    for(int i=1;i<=t;i++)
    {
        int l,r;
        cin>>l>>r;
        if(r-l<m-1)
        {
            cout<<0<<endl;
            continue;
        }
        r=r-m+1;
        cout<<sum[r]-sum[l-1]<<endl;
    }
    return 0;
}

小前：不行，再吃就吐了<@_@>

好的，饭后点心来了！
巧克力ice cream
好家伙，这道题你以为就是单纯的前缀和

这道题要两个前缀和。
一个统计从左往右走，一个统计从右往左走
问题迎刃而解......

这道题奇数和偶数的前缀和简单实现，不过这个枚举L,R
你想O(n^2)？
我不要我不要！
看看这个公式：

俗话说的好，万物皆可方程！
解：sum1_r - sum2_r=sum1_{l-1} - sum2_{l-1}

我们完全可以只枚举r了，可他有10^9，貌似桶也无能为力。
别怕！map驾到，统统闪开！