include using namespace std; int n,m,k; int a[505][505]; long long ans=0; int main(){ //ios::sync\_with\_stdio(false),cout.tie(0),cin.tie(0); ``` scanf("%d%d%d",&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){ for(int p=1,q=1;q<=n;++q) { while(p<=q&&a[q][j]-a[q][i-1]-a[p-1][j]+a[p-1][i-1]>k){ p++; //一直让p指针下移到权值和<=k } if(p<=q){ //在当前i,j的情况下，此时p q 之间的所有子矩阵都满足条件,一共q-p+1行 ans+=(q-p+1); } } } ``` } cout<<ans; ``` return 0; ``` }

二维前缀和+双指针 ``` #include<iostream> using namespace std; typedef long long ll; const int N = 510; int n,m,k; int a[N][N]; int main(){ cin >> n >> m >> k; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]; // 计算到当前位置的子矩阵元素和 } } ll ans =0; for(int i=1;i<=m;i++){ for(int j=i;j<=m;j++){ for(int s=1,t=1;t<=n;t++){ while(s<=t && a[t][j]-a[s-1][j]-a[t][i-1]+a[s-1][i-1]>k)s++; // 调整下边界，直到子矩阵的元素和不超过k if(s<=t) ans+= t-s+1; // 如果下边界在上边界之下，累加可能的子矩阵数量 } } } cout << ans << '\n'; } ``` i是左边界，j是右边界 s为上边界，t为下边界 通过 while 循环来实现的，循环会不断地移动下边界 s，直到找到一个和小于或等于 k 的子矩阵为止。

``` #include <bits/stdc++.h> #define int long long using namespace std; const int N = 510; int a[N][N]; int n, m, k; signed main() { cin >> n >> m >> k; for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) { cin >> a[i][j]; a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]; } int ans = 0; for(int i = 1; i <= n; i ++ ) for(int j = i; j <= n; j ++ ) { for(int x = 1, y = 1; x <= m; x ++ ) { while(y <= m && a[j][y] - a[i - 1][y] - a[j][x - 1] + a[i - 1][x - 1] <= k) y ++ ; ans += y - x; } } cout << ans; } ```

``` #include <bits/stdc++.h> #define endl '\n' typedef long long ll; using namespace std; //数据结构在这里定义 const int N =1e3+10; int a[N][N];//原数据 ll sum[N][N];//求和要ll int n,m,k; //求和函数和ans不开long long只能过70% ll pre(int x, int y, int i, int j){ return sum[i][j] - sum[x-1][j] \ - sum[i][y-1] + sum[x-1][y-1]; } void solve(){ cin >> n >> m >> k; for(int i = 1; i <=n;i++){ for(int j = 1;j<=m;j++){ cin >> a[i][j]; sum[i][j] = sum[i-1][j] + sum[i][j-1] \ - sum[i-1][j-1] + a[i][j]; } } ll ans = 0; for(int up = 1; up<=n;up++){ for(int down = up; down <=n;down++){ //上下确定了此时问题压缩为一维 //滑动窗口法 int left = 1,right=1; for(;right<=m;right++){ //right添加元素 while(pre(up,left,down,right)>k && left <= right){ //总和不满足条件,收缩left left++; } if(left<=right){ //合法区间 //计算sublen 这里是最长子区间大小 ans += right - left + 1; } } } } cout << ans << endl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t;//多组数据要cin //cin >> t; t = 1; while(t--){ solve(); } return 0;//必须加return 0 } ```

include using namespace std; const int MAXN = 501; int n, m, k, p[MAXN][MAXN]; long long ans; inline void scan() { cin >> n >> m >> k; for (int i = 1; i > p[i][j]; p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1]; } } } inline int getSum(int i, int j, int u, int v) { return p[u][v] - p[u][j - 1] - p[i - 1][v] + p[i - 1][j - 1]; } int main() { scan(); ``` for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { for (int col_l = 1, col_r = 1; col_r <= m; col_r++) { while (col_l <= col_r && getSum(i, col_l, j, col_r) > k) col_l++; if (col_l <= col_r) ans += col_r - col_l + 1; } } } cout << ans; return 0; ``` }

```cpp // https://dashoj.com/d/lqbproblem/p/77 #include <bits/stdc++.h> #define N 1010 using namespace std; typedef long long ll; ll n, m, k, ans = 0; vector<vector<ll>> vec(N, vector<ll>(N, 0)); vector<vector<ll>> qzh(N, vector<ll>(N, 0)); int getSum(int i, int j, int u, int v) { return qzh[u][v] - qzh[u][j - 1] - qzh[i - 1][v] + qzh[i - 1][j - 1]; } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); cin >> n >> m >> k; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> vec[i][j]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) qzh[i][j] = vec[i][j] + qzh[i - 1][j] + qzh[i][j - 1] - qzh[i - 1][j - 1]; for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) for (int col_l = 1, col_r = 1; col_r <= m; col_r++) { while (col_l <= col_r && getSum(i, col_l, j, col_r) > k) col_l++; if (col_l <= col_r) ans += col_r - col_l + 1; } cout << ans << endl; return 0; } ```