算法基础训练 50 题(五)前缀和与差分

#JC0501. Subsequences Summing to Sevens S

题目描述

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

#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. 地毯

题目描述

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

#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值遍历每一个可能,记录最大值。

#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种结果。

#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的区间和的最大值为多少。

#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;
}
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇