前缀和算法题

学习笔记

这6道题有几道是非常相似的,可以在不同情景中充分认识一个算法思想–前缀和与差分

对于前缀和与差分，我在CSDN找到了一篇比较形象的文章点击跳转

总结:题目很练基本功,第三题因为没有把和数组定义为长整型而导致一直无法AC,改为long long避免了数组溢出才全部通过

6道题:
题目均来自蓝桥云课

1.区间次方和

本题是定义一个二维数组，第二维度存储前第一维度值项前1-5次方的值 在输入的同时计算pre数组

然后以时间复杂度O(n)解决本题所要求的最大10^5的数据量

因为相加过程，取模之前会有大于Int所能存放的最大值，所以数组定义为长整型

C++AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int mol=1e9+7;
int n,m;
ll num[100005];//瀛樺偍绗琲涓暟1-5娆℃柟鐨勫€?
ll pre[100005][7];//存放前i个数字的j次方之和
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>num[i];
        for(int j=1;j<=5;j++) {
            pre[i][j]=pre[i-1][j]+pow(num[i],j);
        }
    }
    cout<<"\n";
    for(int i=1;i<=m;i++) {
        int l,r,k;
        cin>>l>>r>>k;
        cout<<(pre[r][k]-pre[l-1][k]+mol)%mol<<"\n";
    }
    return 0;
}

2,小郑的平衡串

本题本质是求最大平衡子串，我是定义了两个数组，分别存放当前位置字符左右方的L，Q总数量

然后再两层for截取子串（这里不知道有没有不用两层for的方法），选择长度最大的子串，输出其长度

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
int length=-1;//存储最长平衡子串长度
string str;
int preL[1005]={0},preQ[1005]={0};//记录每个字符前面有几个L，几个Q(包括它自己)
int main() {
    cin>>str;
    //构造前缀和数组
    for(int i=1;i<=str.length();i++) {
        if(str[i-1]=='L') {
            preL[i]=preL[i-1]+1;
            //这也意味着Q数量没变
            preQ[i]=preQ[i-1];
        }
        else if(str[i-1]=='Q') {
            preQ[i]=preQ[i-1]+1;
            //这也意味着preL数量没变
            preL[i]=preL[i-1];
        }
    }
    for(int i=1;i<=str.length();i++) {
        for(int j=i+1;j<=str.length();j++) {
            {
                if(preL[j]-preL[i-1]==preQ[j]-preQ[i-1]) {
                    length=max(length,j-i+1);
                }
            }
        }
    }
    cout<<length<<endl;
    return 0;
}

3，大石头的搬运工

本题定义两个数组分别计算左边和右边所有石头搬到此处的总费用，和第二题类似 “两边顾”

然后只需要O(n)的时间复杂度不断更新ans,找出总spend的最小值

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;//把求总价值的数组定义long long防止溢出
int n;
vector<pair<int,int>> ton(100010);
ll ans=1e18;//定义成一个比较大的值
ll suml[100010];//存左边所有石头移动到这里需要花费的金额
ll sumr[100010];//存右边所有哦石头移动到这里需要花费的金额
int main() {
    cin>>n;
    //先初始化一下suml，sumr 防止影响计算真正的第一项
    suml[0]=0,sumr[n+1]=0;
    for(int i=1;i<=n;i++) {
        cin>>ton[i].second>>ton[i].first;//重量，位置
    }
    //题目是先输入重量再输入位置 这是把两者在pair数组中颠倒
    //这样再用快排会比较简单 (默认按首项即位置排序)
    sort(ton.begin()+1,ton.begin()+n+1);//按照位置进行排序
    ll sum=0;//sum是当前移动中的石头的总重量 务必定义为ll防止溢出！
    for(int i=1;i<=n;i++) {
        suml[i]=suml[i-1]+(ton[i].first-ton[i-1].first)*sum;
        sum+=ton[i].second;
    }
    sum=0;
    for(int i=n;i>=1;i--) {
        sumr[i]=sumr[i+1]+(ton[i+1].first-ton[i].first)*sum;
        sum+=ton[i].second;
    }
    for(int i=1;i<=n;i++) {
        ans=min(ans,sumr[i]+suml[i]);//寻找最小花费值
    }
    cout<<ans<<endl;
    return 0;
}

4,最大数组和

这个题也是构造前缀和数组 优化时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
const long long INF = -1e18;
const int N = 1e6 + 9;
long long a[N];
long long pre[N]={0};
long long ans=INF;
int main() {
    int t;
    cin >> t;
    for(int i=0;i<t;i++){
        ans=0;
        int n,k;
        cin >> n >> k;
        for(int i = 1; i <= n; i++) {
            cin>>a[i];
        }
        //鏁扮粍鎺掑簭鍗囧簭
        sort(a+1, a+n+1);
        pre[0]=0;
        for(int i = 1; i <= n; i++) {
            pre[i]=pre[i-1]+a[i];
        }
        //i琛ㄧず鎿嶄綔鎺変簡鍑犱釜鏈€澶у€煎疂鐭?
        for(int i=0;i<=k;i++) {
            long long sum=pre[n-(k-i)]-pre[2*i];
            ans=max(ans, sum);
        }
        cout<<ans<<endl;
    }
    return 0;
}

5，肖恩的头球游戏

我觉得第5，6两题如出一辙，构造前缀和数组的方式和第一次作业的借教室极其相似

洛谷借教室跳转

下面是我的AC代码，网上可能找到更好的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
int n,q;
int a[100010];
int pre[100010];
int main() {
    cin>>n>>q;
    for(int i=0;i<=n;i++) {
        pre[i]=0;
    }
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    for(int i=1;i<=q;i++) {
        int l,r,c;
        cin>>l>>r>>c;
        pre[l]+=c;
        pre[r+1]-=c;
    }
    for(int i=1;i<=n;i++) {
        pre[i]+=pre[i-1];
    }
    for(int i=1;i<=n;i++) {
        a[i]+=pre[i];
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}

6,区间更新

和第5题，借教室是同一个类型

我的AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
int n,m;
int main() {
    while(cin>>n>>m) {
        int a[100010];
        int pre[100010];
        //这里不初始化可能自动初始化为1,影响pre[1]计算
        for(int i=0;i<=n;i++) {
            pre[i]=0;
        }
        for(int i=1;i<=n;i++) {
            cin>>a[i];
        }
        for(int i=1;i<=m;i++) {
            int x,y,z;
            cin>>x>>y>>z;
            pre[x]+=z;
            pre[y+1]-=z;
        }
        for(int i=1;i<=n;i++) {
            pre[i]+=pre[i-1];
        }
        for(int i=1;i<=n;i++) {
            a[i]+=pre[i];
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}
[视频内嵌代码]