當前位置:網站首頁>練習29,統計子矩陣【二比特前綴和/雙指針】

練習29,統計子矩陣【二比特前綴和/雙指針】

2022-05-13 16:10:07ILECY

4405. 統計子矩陣 - AcWing題庫

給定一個 N×M 的矩陣 A,請你統計有多少個子矩陣 (最小 1×1,最大 N×M) 滿足子矩陣中所有數的和不超過給定的整數 K?

輸入格式
第一行包含三個整數 N,MK

之後 N 行每行包含 M 個整數,代錶矩陣 A

輸出格式
一個整數代錶答案。

數據範圍
對於 30% 的數據,N,M≤20,
對於 70% 的數據,N,M≤100,
對於 100% 的數據,1≤N,M≤500;0≤Aij≤1000;1≤K≤250000000。

輸入樣例:

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

輸出樣例:

19

題解:

用兩個循環枚舉左邊界和右邊界,再用前後指針枚舉上下邊界,複雜度為O(n^{3})

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define lint long long
#define pb push_back
int n,m,k;
lint ans=0;
int a[510][510];
int main(){
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]; //二維前綴和
        }

    for(int i=1;i<=m;i++)
        for(int j=i;j<=m;j++){ //i枚舉左邊界,j枚舉右邊界
            for(int x=1,y=1;x<=n;x++){
                //前指針x和後指針y,分別是下邊界和上邊界
                while(y<=x && (a[x][j]-a[y-1][j]-a[x][i-1]+a[y-1][i-1])>k) y++;
                //邊界內的子矩陣不符合條件,將y指針向下移動
                if(y<=x) ans+=x-y+1;
                //x-y+1代錶從y到x的長度為1~x-y+1的子矩陣的個數
            }
        }
    cout << ans << endl;
    return 0;
}

版權聲明
本文為[ILECY]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/133/202205131609269292.html

隨機推薦