一、題目描述

P8783 [藍橋杯 2022 省 B] 統計子矩陣

二、算法簡析

2.1 二維前綴和

我們知道，只要確定了矩陣的左上頂點和右下頂點，一個矩陣就被固定了。因此，我們可以遍歷這兩個頂點，達到遍歷所有子矩陣的目的，復雜度會達到 $O(N^2?M^2)$。確定了子矩陣，就要判斷子矩陣的值是否不大于 $K$。 如何能高效地得到子矩陣的值呢？答案是二維前綴和。
與普通的前綴和不同，二維前綴和 $\text{psum[i][j]}=$ 左上頂點 $(1,1)$、右下頂點 $(i,j)$ 確定的子矩陣的值。通過以下表達式，可以得到二維前綴和：

$$\text{psum[i][j]?=?psum[i][j?-?1]?+?psum[i?-?1][j]?-?psum[i?-?1][j?-?1]?+?A[i][j]}$$

有了二維前綴和，就可以以 $O(1)$ 確定左上角 $(x1,y1)$、右下角 $(x2,y2)$ 的子矩陣的值：

$$\text{matrix\_val?=?psum[x2][y2]?-?psum[x1?-?1][y2]?-?psum[x2][y1?-?1]?+?psum[x1?-?1][y1?-?1]}$$

但是，該算法的復雜度仍然有 $O(N^2?M^2)$，會 LTE。

---

2.2 壓縮維度 + 雙指針

壓縮維度：我們可以把二維矩陣壓縮至一維：畫兩條線，high 表示矩陣上界（左上點只能在該行）、low表示矩陣下界（右下點只能在該行）。因此，由 high 和 low 確定的子矩陣只能由列矩陣組合而成，所以按列壓縮，即按列求和。

通過遍歷 high 和 low，我們可以得到所有組成子矩陣的列矩陣。

雙指針：通過上文的壓縮，我們得到了“子矩陣的零件”。為了得到該情況下的所有子矩陣，肯定要用雙指針遍歷壓縮數組，得到所有組合方式。

int B[4];   // 壓縮后的結果for (int i = 0; i < 4; i++)for (int j = i; j < 4; j++)\\ ...

顯然，指針 j 發生了回溯，導致復雜度達到了 $O(n^2)$。如何避免發生回溯呢？利用單調性，我們可以把復雜度降為 $O(n)$。
我們規定 $\text{area(left,?right)?=?B[left]?+?B[left?+?1]?+?...?+?B[right]}$。
若 $\text{area(left,?right)?<=?K}$ 且 $\text{left?+?1?<=?right}$，則 $\text{area(left?+?1,?right)?<=?K}$。
若 $\text{area(left,?right)?>?K}$ 且 $\text{right?+?1?<=?M}$，則 $\text{area(left,?right?+?1)?>?K}$。
顯然，$\text{area(left,?right)}$ 隨 $\text{left}$ 單調遞減，隨 $\text{right}$ 單調遞增。

利用單調性，我們可以得到以下結果：

• 1、隨 $\text{left}$ 單調遞減，若 $\text{area(left,?right)?<=?K}$，則一共有 $\text{right?-?left?+?1}$ 種組合方式。
• 2、我們只需要遍歷 right 就能得到所有子矩陣。因為單調性，若 $\text{area(left,?right)?>?K}$，只需要 $\text{left++}$，直到 $\text{area(left,?right)?<=?K}$。

int B[4];   // 壓縮后的結果int left = 1, right = 1;
ll tmp = 0;
for (; right <= 4; right++)
{tmp += B[right];if (tmp <= K)ans += right - left + 1;else{while (tmp > K){tmp -= B[left];left++;	}ans += right - left + 1;}	
} 

---

三、AC代碼

#include <bits/stdc++.h>using namespace std;const int MAX = 505;
typedef long long ll;int A[MAX][MAX], N, M, K;
ll ans, psum[MAX][MAX], B[MAX];int quickin(void)
{int ret = 0;char ch = getchar();while (ch < '0' || ch > '9')ch = getchar();while (ch >= '0' && ch <= '9' && ch != EOF){ret = ret * 10 + ch - '0';ch = getchar();}return ret;
}void init(void)
{for (int i = 1; i <= N; i++)for (int j = 1; j <= M; j++)psum[i][j] = psum[i - 1][j] + A[i][j];
}void solve(void)
{for (int high = 1; high <= N; high++){for (int low = high; low <= N; low++){for (int i = 1; i <= M; i++)B[i] = psum[low][i] - psum[high - 1][i];int left = 1, right = 1;ll tmp = 0;for (; right <= M; right++){tmp += B[right];if (tmp <= K)ans += right - left + 1;else{while (tmp > K){tmp -= B[left];left++;	}ans += right - left + 1;}	} }}cout << ans << endl;
}int main()
{#ifdef LOCALfreopen("test.in", "r", stdin);#endifN = quickin(), M = quickin(), K = quickin();for (int i = 1; i <= N; i++)for (int j = 1; j <= M; j++)A[i][j] = quickin();init();solve();return 0;
}

---

完