蓝桥杯每日一题2023.9.18

╰半橙微兮° 2024-03-02 08:39 4阅读 0赞

[蓝桥杯2022年第十三届省赛真题-统计子矩阵 - C语言网 (dotcpp.com)][2022_-_ - C_ _dotcpp.com]

### 题目描述 ###

给定一个 N × M 的矩阵 A，请你统计有多少个子矩阵 (最小 1 × 1，最大 N × M) 满足子矩阵中所有数的和不超过给定的整数 K?

### 分析 ###

如果不考虑范围问题等，可以用二位前缀和，一步一步列举

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e4 + 10;
    int n, m, k, ans, a[N][N], s[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];
    		}
    	}
    	for(int i = 1; i <= n; i ++)
    	{
    		for(int j = 1; j <= m; j ++)
    		{
    			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    		}
    	}
    	ans = 0;
    	for(int x1 = 1; x1 <= n; x1 ++)
    	{
    		for(int y1 = 1; y1 <= m; y1 ++)
    		{
    			for(int x2 = x1; x2 <= n; x2 ++)
    			{
    				for(int y2 = y1; y2 <= m; y2 ++)
    				{
    					if (s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] <= k)ans ++;
    				}
    			}
    		}
    	}
    	cout << ans;
    	return 0;
    }

但是四重循环会使时间超限

故可以考虑优化

将上下边界进行循环，使用双指针来列出左右边界，由于范围一定 <= k,故超过这个的话就移动指针

将上下枚举出来就可以看成一个一维问题，可以将每一列看成一个元素，相当于一个一维数组，在这个数组里找到哪些区间 <= k

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e4 + 10;
    int n, m, k, sum, ans, a[N][N], s[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];
    		}
    	}
    	for(int i = 1; i <= n; i ++)
    	{
    		for(int j = 1; j <= m; j ++)
    		{
    			s[i][j] = s[i - 1][j] + a[i][j];//算出这一列的前缀和 
    		}
    	}
    	for(int i = 1; i <= n; i ++)//枚举上边界 
    	{
    		for(int j = i; j <= n; j ++)//枚举下边界 
    		{
    			for(int l = 1, r = 1, sum = 0; r <= m; r ++)//枚举左右边界 
    			{
    			 	sum += s[j][r] - s[i - 1][r];
    			 	while(sum > k)
    			 	{
    			 		sum -= s[j][l] - s[i - 1][l];
    			 		l ++;
    				}
    				ans += r - l + 1;
    			} 
    		}
    	}
    	cout << ans;
    	return 0;
    }

[2022_-_ - C_ _dotcpp.com]: https://www.dotcpp.com/oj/problem2659.html