算法基础训练 50 题（五）前缀和与差分

发表于 更新于 分类于 ，

#JC0501.# Subsequences Summing to Sevens S

题目描述

先对输入数据求前缀和，同时将前缀和模7。从头开始遍历，对于每一个数，再从末尾往前寻找，找到和模7为0的数，并记录区间长度。直接这样会导致超时。实际上由于记录前缀和时进行了模7，所以前缀和只会是0-6中的数，区间开始位置的数相同时区间的结尾也相同，但是后遍历的开始位置区间长度必定比第一次遍历时的短，所以可以记录下已经遍历过哪些区间开始时的数，再次遇到相同的数时跳过。

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>
int n,x,ans,z;
int a[500005],b[7];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n;
    F(i,1,n)
    {
        CI x;
        a[i]=(a[i-1]+x)%7;
    }

    F(i,1,n)
        if (!b[a[i-1]])
        {
            b[a[i-1]]=1;
            z++;
            for (int j=n;j>=i+1&&(j-i+1)>ans;j--)
            {
                if ((a[j]-a[i-1]+7)%7==0)
                {
                    ans=j-i+1;
                    break;
                }
            }
            if (z==7) break;
        }

    CO ans L;
    return 0;
}

#JC0502.# 地毯

题目描述

此题套用二维差分的模版即可

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
#include<bits/stdc++.h>
int n,m,a[10001][10001],d[10001][1001];
int main()
{
    int x1,y1,x2,y2;
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>x1>>y1>>x2>>y2;
        d[x1][y1]+=1;
        d[x2+1][y1]-=1;
        d[x1][y2+1]-=1;
        d[x2+1][y2+1]+=1;
    }

    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + d[i][j];
            cout<<a[i][j]<<" ";
        }
    cout<<endl;
    } 
    return 0;
}

#JC0503.# 激光炸弹

题目描述

利用二维前缀和即可，是输入的坐标范围从0开始，为了方便计算，统一将所有坐标+1，这样坐标就从1开始了。同时会存在多个目标处于同一个坐标的情况，所以不能直接将目标价值覆盖到地图上而要累加。然后生成二维前缀和数组，最后根据左上角坐标和m值遍历每一个可能，记录最大值。

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
#include<bits/stdc++.h>
int n,m,a,b,c;
int p[5003][5003],v;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n>>m;
    F(i,1,n)
    {
        CI a>>b>>c;
        p[a+1][b+1]+=c;
    }
    F(i,1,5001)
    {
        F(j,1,5001)
            p[i][j]=p[i][j]+p[i-1][j]+p[i][j-1]-p[i-1][j-1];
    }
  
    F(i,0,5001-m)
    {
        F(j,0,5001-m)
            v=max(v,p[i+m][j+m]-p[i][j+m]-p[i+m][j]+p[i][j]);
    }
    CO v L;
    return 0;
}

#JC0504.# IncDec Sequence

题目描述

让每个数都一样，即对应的差分数组除了第一个，其他都是0。根据差分数组的操作方式，修改区间[l,r]时d[l]+=c,d[r+1]-=c，可以发现，区间开始和区间结尾的运算符相反。所以为了求出最小操作数，要让区间开始和结尾的差分数符号相反，这样一次操作可以改变两个差分值，直到其中一个符号完全被消掉，也就是只剩下一种符号的差分值了，这时每次操作只能改变一个差分值。假设从下标2开始的差分数组中正数和为sum1，负数和的绝对值为sum2，则区间开始和结尾的差分数符号相反的操作共有min(sum1,sum2)次，操作完后只剩下一种符号的差分值，另一种符号的差分值被完全消掉，于是还需要进行max(sum1,sum2)-min(sum1,sum2)=abs(sum1-sum2)次操作。所以总共是max(sum1,sum2)次操作。对于第二问，假设sum1>sum2，则进行min(sum1,sum2)次操作后负数的差分值被全部消掉，只剩下正差分值。接下来的sum1-sum2次操作就是将除下标1外的正差分值全部改为0。由于只剩下正差分值，所以整个数组是单调递增的，而将差分值变为0,的过程就是不断让后面元素向第一个元素靠拢。这时有两种靠拢方式，第一种是将大于第一个数的元素-1，第二种就是将第一个数以及和他相等的数都+1。于是就能得到不同的结果。由于每一次操作都有2中方法，所以总共能得到abs(sum1,sum2)+1种结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
LL n,a[100005],d[100005],sum1,sum2;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n;
    F(i,1,n)
    {
        CI a[i];
        d[i]=a[i]-a[i-1];
    }
    F(i,2,n)
    {
        if (d[i]>0) sum1+=d[i];
        else sum2+=-d[i];
    }
    cout<<max(sum1,sum2)<<endl<<abs(sum1-sum2)+1<<endl;
    return 0;
}

#JC0505.# 水壶

题目描述

此题就是求长度为k+1的区间和的最大值为多少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
int n,k;
LL x,p[1000006],ans;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n>>k;
    F(i,1,n)
    {
        CI x;
        p[i]=p[i-1]+x;
    }
    F(i,1,n-k)
        ans=max(p[i+k]-p[i-1],ans);
    CO ans L;
    return 0;
}