首页 > 其他分享 >[NEFU ACM大一暑假集训 解题报告]前缀和与差分

[NEFU ACM大一暑假集训 解题报告]前缀和与差分

时间：2022-11-25 19:37:44浏览次数：78  
标签：typedef int sum 大一 ACM NEFU ++ ans LL


[NEFU ACM大一暑假集训 解题报告]前缀和与差分

题量略大，所以解题报告和fjy大佬分了一下工
由我负责A-K部分题解（不是AK部分题解啊，哈哈）
后半部分题解（LM+R~V+XYZ）由fjy大佬发布
剩下的题目烦请有余力的同学自行解决

题目

A - Molly’s Chemicals

题目求区间和为m的幂次的子区间个数，也就是要满足下面这个公式。
[NEFU ACM大一暑假集训 解题报告]前缀和与差分_前缀和
幂次的话想不到啥特性，但是这题m是固定的那么直接把幂次暴力预处理出来就完事了。[NEFU ACM大一暑假集训 解题报告]前缀和与差分_前缀和_02大概为1e19级别，题目弄到1e14就够了，所以弄个几十次就能结束。
然后对于这种找满足条件的等式，我们可以很快想到用map来查询有没有配对的值。但是这里的map需要采用类似前缀和的方式来维护查询，而不是直接在1～n里面搜。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'

int T;
int n,m;
const int N=1e5+10;
LL sum[N],mpow[N];
map<LL,LL>mp;
int main(){

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>sum[i];
        sum[i]+=sum[i-1];
    }

    int cnt=0;
    LL mk=1;
    if(m==1)mpow[++cnt]=1;
    else if(m==-1){mpow[++cnt]=1;mpow[++cnt]=-1;}
    else{
        while(abs(mk)<1e14+10){
        mpow[++cnt]=mk;
        mk*=m;
        }
    }
    LL ans=0;
    mp[0]++;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=cnt;j++){
            if(mp.find(sum[i]-mpow[j])!=mp.end())ans+=mp[sum[i]-mpow[j]];
        }
        mp[sum[i]]++;
    }
    cout<<ans<<endl;
    return 0;
}

B - Balanced Substring

找一个最长的连续子串要求0和1的数量相同。
对于数量相同而且只有01两种，我们一般把0和1做差,预处理前缀和。题目要求0和1数量相同那么就是满足条件：
[NEFU ACM大一暑假集训 解题报告]前缀和与差分_预处理_03
而我们要求的最长的连续字串，考虑区间[NEFU ACM大一暑假集训 解题报告]前缀和与差分_i++_04对答案的贡献为[NEFU ACM大一暑假集训 解题报告]前缀和与差分_i++_05我们固定右端点i,然后找最小的满足条件的j,使得长度最大。
类似A题，我们用map维护i前面，满足条件的j的最小值。维护满足条件的最小值，只需要从前往后遍历一边，把第一个满足条件的标记即可。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'
const int N=100005;
int T;
int t[N];
map<int,int>mp;
int main(){
    int n;cin>>n;
    string s;cin>>s;
    if(s[0]=='1')t[0]=1;
    else t[0]=-1;
    for(int i=1;s[i];i++){
        if(s[i]=='1')t[i]=t[i-1]+1;
        else t[i]=t[i-1]-1;
    }

    for(int i=0;i<n;i++){
        if(mp.find(t[i])==mp.end()){
            mp[t[i]]=i;
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        if(mp[t[i]]!=i)ans=max(ans,i-mp[t[i]]);
        if(t[i]==0)ans=max(ans,i+1);
    }
    cout<<ans;
    return 0;
}

C - White Lines

行和列没分开处理，写公式写吐了，后来看别人的发现分开处理会好很多
​​参考这篇​​[NEFU ACM大一暑假集训 解题报告]前缀和与差分_前缀和_06大小的网格，有黑白两种颜色，要求使用[NEFU ACM大一暑假集训 解题报告]前缀和与差分_前缀和_07的橡皮擦擦一次，求最多的白线(全为白的行和列)数目。
首先读入地图，黑色为1,白色为0。
最暴力的方法是枚举橡皮擦起点，然后[NEFU ACM大一暑假集训 解题报告]前缀和与差分_前缀和_08判是否构成白线算贡献，复杂度为[NEFU ACM大一暑假集训 解题报告]前缀和与差分_前缀和_09
考虑优化算贡献的部分：
我们可以预处理两个数组row[i][j],col[i][j]表示i行j列左边和上边分别有多少黑块

[NEFU ACM大一暑假集训 解题报告]前缀和与差分_预处理_10

我们先把本来就是白线的部分算出来

条件为：

if(row[i][n]==0)cnt++;
if(col[i][n]==0)cnt++;

然后前缀和维护覆盖后的白线数列
[NEFU ACM大一暑假集训 解题报告]前缀和与差分_i++_11维护的是前i行第j个字符到第[NEFU ACM大一暑假集训 解题报告]前缀和与差分_i++_12个字符被覆盖后，组成的白线数量
[NEFU ACM大一暑假集训 解题报告]前缀和与差分_i++_13维护的是前j列第i个字符到第[NEFU ACM大一暑假集训 解题报告]前缀和与差分_前缀和_14个字符被覆盖后，组成的白线数量

如何判断一段被覆盖后这行/列为白线？这一段区间内黑块数量==整行/列黑块数列

最后枚举橡皮擦左上角起点就可以了
区域的贡献为[NEFU ACM大一暑假集训 解题报告]前缀和与差分_i++_15

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'

int T;
const int N=2005;
char a[N][N];
int g[N][N],row[N][N],col[N][N];
int rsum[N][N],csum[N][N];
int main(){
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            row[i][j]+=row[i][j-1]+(a[i][j]=='B');
            col[j][i]+=col[j][i-1]+(a[i][j]=='B');
    }
    LL cnt=0;
    for(int i=1;i<=n;i++){
        if(row[i][n]==0)cnt++;
        if(col[i][n]==0)cnt++;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j+k-1<=n;j++){
            rsum[i][j]=rsum[i-1][j]+(row[i][j+k-1]-row[i][j-1]==row[i][n]&&row[i][n]!=0);
            csum[i][j]=csum[i-1][j]+(col[i][j+k-1]-col[i][j-1]==col[i][n]&&col[i][n]!=0);
        }
    }
    LL ans=0;
    for(int i=1;i+k-1<=n;i++){
        for(int j=1;j+k-1<=n;j++){
            ans=max(ans,cnt+rsum[i+k-1][j]-rsum[i-1][j]+csum[j+k-1][i]-csum[j-1][i]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

D - Monitor

n×m 区域，有p个长方形，q次询问，每次询问一个区域能否完全地被p个长方形覆盖。
本题卡空间，所以使用vector来写，当然也可以采用坐标hash+map的方式压缩空间。
实际上vector目前在大部分评测平台上，性能和数组基本差不了太多，开完[NEFU ACM大一暑假集训 解题报告]前缀和与差分_预处理_16优化后基本一致

思路比较简单，先用二维差分标记p个长方形，然后通过一次前缀和预处理出来。
判断一个区域是否被完全覆盖，我们可以把被覆盖的点都赋值为1,若这个区域被全部覆盖，那么这个区域的区间和等于这个区域的面积。
因此在第一步前缀和预处理后，我们还需要把被覆盖的点值处理为1

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'

int T;
int main(){
    int n,m,p;
    while(cin>>n>>m>>p){
        vector<vector<LL>> a(n + 5, vector<LL>(m + 5, 0));
        while(p--){
            int x1,x2,y1,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            a[x1][y1]++;a[x2+1][y1]--;a[x1][y2+1]--;a[x2+1][y2+1]++;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(a[i][j]>0)a[i][j]=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];

        int q;scanf("%d",&q);
        while(q--){
            int x1,x2,y1,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            int sum=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
            if(sum>=(x2-x1+1)*(y2-y1+1))puts("YES");
            else puts("NO");
        }
    }
    return 0;
}

E - Finding Seats

求一个最小的子矩阵，使得区间和>=k
对于满足条件的最小子矩阵和最大子矩阵，我们的一个思路是把二维问题转化为一维度问题。
我们可以通过合并连续的几行，把他转为一维问题：求最大短连续子序列使得区间和>=k。
对于一维问题，我们容易想到用双指针来解决（尺取法训练A题）
我们枚举合并哪几行，然后维护更新答案即可

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'

int T;
const int N=305;
int n,m,k;
LL s[N][N],g[N][N],merge_mat[N],merge_sum[N];
char a[N][N];
void get_merge(int st,int ed){
    memset(merge_mat,0,sizeof merge_mat);
    memset(merge_sum,0,sizeof merge_sum);
    for(int i=1;i<=m;i++){
        merge_mat[i]=s[ed][i]-s[ed][i-1]-s[st-1][i]+s[st-1][i-1];
        merge_sum[i]=merge_sum[i-1]+merge_mat[i];
   }   
}
LL get_len(){//求和>=k的最短连续序列
    LL ans=1e9+7;
    for(int i=1,j=1;i<=m;i++){
        while(j<=i&&merge_sum[i]-merge_sum[j-1]>=k)j++;
        if(merge_sum[i]-merge_sum[j-2]>=k)ans=min(ans,(LL)(i-(j-1)+1));
    }
    if(ans==1e9+7)return -1;
    return ans;
}
int main(){
    while(~scanf("%d%d%d",&n,&m,&k)){
        if(n==0&&m==0&&k==0)break;
        for(int i=1;i<=n;i++)scanf("%s ",a[i]+1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                if(a[i][j]=='.')g[i][j]=1;
                else g[i][j]=0;
                s[i][j]=s[i][j-1]+s[i-1][j]+g[i][j]-s[i-1][j-1];
            }

        LL ans=n*m;
        for(int i=1;i<=n;i++)
            for(int j=i;j<=n;j++){
                get_merge(i,j);//合并i和j列
                LL len=get_len();
                if(len!=-1)ans=min(ans,(j-i+1)*len);
            }
        cout<<ans<<endl;
    }
    return 0;
}

F - The Number of Products

给你一个非零序列，求满足区间积为正以及区间积为负的区间数量。
前缀积和前缀和有着相似的性质。问题涉及乘积的正负，我们可以联想到这与区间中负数的奇偶性有关。
负数为奇数，区间为负数，负数为偶数，区间为偶数。因此我们首先预处理负数数量的前缀和。
也就是要满足
sum[r]-sum[l-1]=奇数
sum[r]-sum[l-1]=偶数
对于奇偶性，我们考虑加减法和乘法两种形式。
在这里乘法比加减法容易得多，因为只需要奇偶相异就是负数。
也就是说下面两个情况是等效的：
sum[r]奇数，sum[l]偶数
sum[r]偶数，sum[l]奇数
我们只关心l和r配对是不是一奇一偶，不用受到前缀这一定义的限制，我们直接统计sum[0]~sum[n]有多少奇数多少偶数即可。(如果加减法就需要考虑前缀的限制，就变得很麻烦）
负数的答案为[NEFU ACM大一暑假集训 解题报告]前缀和与差分_前缀和_17
正数只需用把所有配对方式减去负数的答案即可,答案为[NEFU ACM大一暑假集训 解题报告]前缀和与差分_预处理_18

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'
const int N=2e5+10;
int T;
int sum[N],odd[N],even[N];
int main(){
    LL n;cin>>n;
    for(int i=1,x;i<=n;i++){
        cin>>x;
        if(x<0)sum[i]=sum[i-1]+1;
        else sum[i]=sum[i-1];
    }
    LL odd=0,even=0;
    for(int i=0;i<=n;i++){
        if(sum[i]%2)odd++;
        else even++;
    }
        
    cout<<odd*even<<" "<<(n+1)*n/2-odd*even<<endl;

    return 0;
}

G - 最大子矩阵

求区间和最大的子矩阵。
板子题，预处理前缀和后枚举更新就完事了。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'

int T;
const int N=1005;
LL s[N][N],g[N][N];
int main(){
    scanf("%d",&T);
    while(T--){
        int n,m,x,y;scanf("%d%d%d%d",&n,&m,&x,&y);
        memset(g,0,sizeof g);
        memset(s,0,sizeof s);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%lld",&g[i][j]);
                s[i][j]=s[i-1][j]+s[i][j-1]+g[i][j]-s[i-1][j-1];
            }
        }
        LL ans=0;
        for(int i=1;i+x-1<=n;i++){
            for(int j=1;j+y-1<=m;j++){
                ans=max(ans,s[i+x-1][j+x-1]-s[i+x-1][j-1]-s[i-1][j+y-1]+s[i-1][j-1]);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

H - Color the ball

每次给一个区间的数加一，查询一个数的值。
差分板子题，差分数组预处理标记，前缀和还原即可

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'

int T;
const int N=1e6+10;
int b[N];
int main(){
    int n;
    while(~scanf("%d",&n),n){
        memset(b,0,sizeof b);
        int sum=0;
        for(int i=1;i<=n;i++){
            int l,r;scanf("%d%d",&l,&r);
            b[l]++,b[r+1]--;
        }
        for(int i=1;i<n;i++){
            sum+=b[i];
            printf("%d ",sum);
        }
        printf("%d\n",sum+b[n]);
    }
    return 0;
}

I - Subsequence

区间和>=k的最短连续子序列，尺取法训练A题，不讲了

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'

int T;
const int N=1e5+10;
LL sum[N],a[N];
int main(){
    scanf("%d",&T);
    while(T--){
        LL n,k;scanf("%lld%lld",&n,&k);
        memset(sum,0,sizeof sum);
        for(int i=1;i<=n;i++){
            scanf("%lld",&sum[i]);
            sum[i]+=sum[i-1];
        }
        LL ans=1e9+7;
        for(int i=1,j=1;i<=n;i++){
            while(j<=i&&sum[i]-sum[j-1]>=k)j++;
            if(sum[i]-sum[j-2]>=k)ans=min(ans,(LL)i-j+2);
        }
        if(ans!=1e9+7)cout<<ans<<endl;
        else cout<<0<<endl;
    }
    return 0;
}

J - Best Cow Fences

建议看蓝书（算法竞赛进阶指南），二分答案求最值转为存在性问题。
给一个正整数序列A,求平均值最大的，长度不小于L的连续子段。
即：在长度不小L这一限制下，让连续子段平均值最大。
最值问题转化为存在性问题：最大，就是不存在某一个操作比当前操作获得答案更大了。
我们二分答案，对平均值做二分。
接下里的问题是如何快速判断是否有满足条件的解。
我们可以数列中每个数都减去二分的之，就转化为判定是否存在一个长度不小于L的子段和非负。
存在非负也就是说，长度不小于L的最大子段和>=0。
在sum[0]~sum[n]找 令[NEFU ACM大一暑假集训 解题报告]前缀和与差分_预处理_19最大的并且满足[NEFU ACM大一暑假集训 解题报告]前缀和与差分_i++_20的i和j
类似B题，我们枚举i，在[NEFU ACM大一暑假集训 解题报告]前缀和与差分_预处理_21的范围内找最小的[NEFU ACM大一暑假集训 解题报告]前缀和与差分_i++_22,更新答案

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
#define endl '\n'

int T;
const int N=1e6+10;
const double eps=1e-5;
double a[N],b[N],sum[N];
int main(){
    int n,len;scanf("%d%d",&n,&len);
    for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
    double l=-1e6,r=1e6;
    while(r-l>eps){
        double mid=(l+r)/2;
        for(int i=1;i<=n;i++)b[i]=a[i]-mid;
        for(int i=1;i<=n;i++)sum[i]=sum[i-1]+b[i];
        double ans=-1e10;
        double min_val=1e10;
        for(int i=len;i<=n;i++){
            min_val=min(min_val,sum[i-len]);
            ans=max(ans,sum[i]-min_val);
        }
        if(ans>=0)l=mid;
        else r=mid;
    }
    cout<<int(r*1000)<<endl;
    return 0;
}

K - Cornfields

感觉不应出现在这个专题里

要快速查询k*k区域内最大值和最小值差值。

多次区间最值查询我们可以想到RMQ,一般有下面这几种

[NEFU ACM大一暑假集训 解题报告]前缀和与差分_预处理_23

我们选用单调队列（滑动窗口）

一维度滑动窗口解决这一类问题：[NEFU ACM大一暑假集训 解题报告]前缀和与差分_前缀和_08预处理出不同起点，长度固定的区间内的最值。

这道题是二维的，那么二维度滑动窗口怎么写？

我们只需要先对行做滑动窗口，然后把行合并，再对列求滑动窗口即可。具体原理和实现各位可以参考​​这道题目的题解（理想的正方形）​​

fjy大佬用优先队列写的，你们可以问问他。
搞笑的是ph大佬写了个朴素暴力过去了hh,数据太弱了。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 250;
int row_min[N][N],row_max[N][N],res[N][N];
//row_min[i][j]表示当前第i行，第[j - m + 1,j]这个区间的最小值，row_max同理
int n,k,Q;  //表示n * m的矩阵，选出k * k矩阵的最大整数和最小整数的差值”的最小值
int w[N][N]; 
int q[N]; //优先队列

void get_min(int a[], int b[], int tot){
    int hh = 0, tt = -1;
    for (int i = 1; i <= tot; i ++ )
    {
        if (hh <= tt && q[hh] < i - k + 1) hh ++ ;
        while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
        q[++tt] = i;
        b[i] = a[q[hh]];
    }
}

void get_max(int a[], int b[], int tot)
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= tot; i ++ )
    {
        if (hh <= tt && q[hh] <= i - k) hh ++ ;
        while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[ ++ tt] = i;
        b[i] = a[q[hh]];
    }
}

int main(){
    cin >> n >> k >> Q;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j){
            scanf("%d",&w[i][j]);
        }
    }

    for(int i = 1;i <= n;++i){
        get_min(w[i],row_min[i],n);
        get_max(w[i],row_max[i],n);
    }

    int ans[N],col_min[N],col_max[N];
    for(int j = k;j <= n;++j){ //枚举列
        for(int i = 1;i <= n;++i) ans[i] = row_min[i][j];
        get_min(ans,col_min,n);   
        for(int i = 1;i <= n;++i) ans[i] = row_max[i][j];
        get_max(ans,col_max,n);

        for(int i = k;i <= n;++i){
            res[i][j]=col_max[i]-col_min[i];//以i,j为右下角的长度为k的矩形
        }
    }
    
    while(Q--){
        int x,y;cin>>x>>y;
        cout<<res[x+k-1][y+k-1]<<endl;
    }

    return 0;
}


标签：typedef,int,sum,大一,ACM,NEFU,++,ans,LL
From： https://blog.51cto.com/u_15891800/5887542

相关文章

  • [NEFU ACM] 2020级暑期训练 解题报告
    [NEFUACM]2020级暑期训练解题报告Author:2020-计6-zslID：FishingRod阅读须知需求指向：NEFU2020级ACM暑期训练参与人员解题报告博客偏向题解代码展示，解题视频偏向思路讲解......
  • [NEFU ACM大一暑假集训 解题报告]尺取法
    [NEFUACM大一暑假集训解题报告]尺取法前四题为例题，学长讲过了，直接贴代码了。题谱题目A-Subsequence求总和>=s的最短区间#include<cstdio>#include<cstdlib>#include<cma......
  • [NEFU 数据结构] 第 2 章 线性表 知识点整理
    [NEFU数据结构]第2章线性表知识点整理阅读须知需求指向：此博客用于应付NEFU数据结构考试，基于题目进行整理，不适合想深入学习数据结构与算法艺术的同学。前置知识：C语言......
  • [NEFU]数据结构 知识点整理和代码实现
    [NEFU]数据结构知识点整理和代码实现Author:2020-计6-zslID：Fishingrod阅读须知需求指向：此博客用于应付NEFU数据结构考试，基于题目进行整理，不适合想深入学习数据结构与算法......
  • [NEFU 数据结构] 第 1 章 绪论 知识点整理
    [NEFU数据结构]第1章绪论知识点整理阅读须知需求指向：此博客用于应付NEFU数据结构考试，基于题目进行整理，不适合想深入学习数据结构与算法艺术的同学。前置知识：C语言参......
  • 【ACM】1.亲和数——中等
    题目描述 古希腊数学家毕达哥拉斯在自然数研究中发现，220的所有真约数(即不是自身的约数)之和为： 1+2+4+5+10+11+20+22+44+55+110＝284。 而284的所有真约数为1、2、4、71......
  • 弈悟计划——大一C程期末实验之五子棋AI的开发日志
    写在前面大一C程的期末作业，因为觉得从头学C太没意思，因此报了学校的什么挑战班（早知道不换了去混绩点了）由于本人懒得要死，刚开始想手搓GUI，然后看了各种图形界面感觉徒增烦恼......
  • RocketMq消息体过大一站式解决方案
    普及RocketMq消息体大小限制相关知识如下：1.消息体大小最大为4MB,一般建议发送的消息体在4kb之内(性能最佳)。2.消息属性最大为32kb，一般建议发送的消息属性在......
  • 华东交通大学2022双基ACM竞赛
    比赛链接：https://ac.nowcoder.com/acm/contest/44482签到：AEI碎碎念：好家伙，题目里全是心怡。A：心怡的魔法城堡原题链接：心怡的魔法城堡题意：闯入者可以选择到达上出口或......
  • ACM预备队week4(搜索)
    1.迷宫题目链接：P1605迷宫-洛谷|计算机科学教育新生态(luogu.com.cn)dfs1#include<bits/stdc++.h>2usingnamespacestd;3intsx,sy,fx,fy;4intn,m,......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99