前缀和&暴力指针

Hai_Ker · 2024-04-30 14:55:52 · 题解

P8783暴力前缀和&前缀和指针

题目传送门

暴力前缀和

本题可以用前缀和做（but!只能得80分） 不会前缀和？？？

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rip(a,b,c) for(ll i=a;i<=b;i+=c)
#define rjp(a,b,c) for(ll j=a;j<=b;j+=c)
#define rrp(a,b,c) for(ll r=a;r<=b;r+=c)
int n,m,k,cnt;
int a[505][505],sum[505][505];
ll z(ll a,ll b){//矩阵右下角坐标 
    ll cut=0;
    rip(a+1,n,1){//右上x 
        rjp(b+1,m,1){//右上y
            if((sum[i][j]-sum[i][b]-sum[a][j]+sum[a][b])<=k){//图一... (加左加上减左上)
                cut++;
            }
        }
    }
    return cut;
}
int main() {
    cin>>n>>m>>k;//输入n,m,k
    rip(1,n,1){
        rjp(1,m,1){
            cin>>a[i][j];//输入数组
            sum[i][j] = a[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];//前缀和
        } 
    }
    rip(1,n,1){
        rjp(1,m,1){
            cnt+=z(i-1,j-1);//用函数枚举亿下 
        }
    }
    cout<<cnt;
    return 0;
}
1←+2←+3
↑↖↑↖↑
+ -+ -+ 
4←+5←+6
↑↖↑↖↑
+ -+ -+ 
7←+8←+9

结果\ ↑\ T了,O(n^4)是%100T的\ 然后...\ 我同学说这个可以用

双指针

100代码！！！:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rip(a,b,c) for(ll i=a;i<=b;i+=c)
#define rjp(a,b,c) for(ll j=a;j<=b;j+=c)
#define rrp(a,b,c) for(ll r=a;r<=b;r+=c)
ll n,m,k,cnt;
ll a[505][505],sum[505][505];
/*
ll z(ll a,ll b){
    ll cut=0;
    rip(a+1,n,1){
        rjp(b+1,m,1){
            if((sum[i][j]-sum[i][b]-sum[a][j]+sum[a][b])<=k){//加左加上减左上 
                cut++;
            }
        }
    }
    return cut;
}
*/
int main() {
    //scanf("%d%d%d",&n,&m,&k);
    cin>>n>>m>>k;
    rip(1,n,1){
        rjp(1,m,1){
            //scanf("%d",&a[i][j]);
            cin>>a[i][j];
            sum[i][j] = a[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];//前缀和
        } 
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            for(int l=1,r=1;r<=m;r++){
                while(l<=r&&sum[j][r]-sum[i-1][r]-sum[j][l-1]+sum[i-1][l-1]>k){//在不"<="k时l++ 
                    l++;
                }
                if(l<=r)cnt+=r-l+1;//区间
            }
        }
    }
    /*
    rip(1,n,1){
        rjp(1,m,1){
            cnt+=z(i-1,j-1);
        }
    }
    */
    //printf("%d",cnt);
    cout<<abs(cnt);//闲的
}

其实核心思路都一样，都是前缀和\ 也就是a1=a_-a2-a3+a4 如果不太会本题，建议先做P3397 地毯