网站开发流程中客户的任务是什么,18末年年禁止观看网站,wordpress图片转文字,怎样做才能让网站帮忙送东西题目描述
给定一个 NM 的矩阵 A#xff0c;请你统计有多少个子矩阵 (最小 1111, 最大 NM 满足子矩阵中所有数的和不超过给定的整数 K。
输入格式
第一行包含三个整数 N,M 和 K。
之后 N 行每行包含 M 个整数, 代表矩阵 A。
输出格式
一个整数代表答案。
输入输出样例
…题目描述
给定一个 N×M 的矩阵 A请你统计有多少个子矩阵 (最小 1×11×1, 最大 N×M 满足子矩阵中所有数的和不超过给定的整数 K。
输入格式
第一行包含三个整数 N,M 和 K。
之后 N 行每行包含 M 个整数, 代表矩阵 A。
输出格式
一个整数代表答案。
输入输出样例
输入 #1
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
输出 #1
19
说明/提示
【样例说明】
满足条件的子矩阵一共有 1919包含:
大小为 1×11×1 的有 1010 个。
大小为 1×21×2 的有 33 个。 大小为 1×31×3 的有 22 个。
大小为 1×41×4 的有 11 个。
大小为 2×12×1 的有 33 个。
【评测用例规模与约定】
对于 30% 的数据, N,M≤20.
对于 70% 的数据, N,M≤100.
对于 100% 的数据, 1≤N,M≤500,0≤Aij≤1000,1≤K≤2.5×1e8.
蓝桥杯 2022 省赛 B 组 F 题。 看到要求矩阵和我们首先想到二位前缀和先想出我们的暴力方法首先预处理得出二位前缀和数组然后枚举左上角对每一个左上角都去枚举右下角根据我们的前缀和方程求得当前这个矩阵的和值是多少和我们的k值比较即可。当然这样肯定超时我们可以很轻松的想出第一个优化比如我枚举了右下角在第一行的矩阵之后已经找到一个大于k值的矩阵那么我第二行就不要再包括他了。我们可以设置一个随着枚举而更新的maxc记录这个值这个方案可以大大缩短我们的程序运行时间代码如下
#includebits/stdc.h
using namespace std;
#define int long longint a[505][505] { 0 };
int s[505][505] { 0 };signed main()
{int n, m, k;cin n m k;for (int i 1;i n;i){for (int j 1;j m;j){cin a[i][j];s[i][j] s[i][j - 1] s[i - 1][j] - s[i - 1][j - 1] a[i][j];}}int ans 0;for (int i 1;i n;i){for (int j 1;j m;j){//以上两个循环枚举左上角int maxc m 1;for (int r i;r n;r){for (int c j; c maxc;c){//枚举右下角if (s[r][c] - s[i - 1][c] - s[r][j - 1] s[i - 1][j - 1] k){maxc c;break;}else ans;}}}}cout ans;return 0;
}
不过就算这样还是有两个点过不了只能拿80分。虽然是优化过的但我们这个方法的本质依然是枚举左上角与右下角复杂度还是太高o(m^2*n^2)。第二个优化我是想不出来了这也代表了我们这样用二位前缀和只能拿部分分。
看了题解了解到第二种方法当然还是建立在前缀和的基础上我们不在枚举左上角与右下角而是转为枚举行的范围这是一个o(n^2)的操作。然后我们使用一个双指针去遍历这个范围就像是把二维问题降维成一维一样: 有一个序列 [1,3,4,3]试求出其中有多少个子序列满足该子序列的所有元素之和小于等于 10。具体思路参考P8783 题解 - 洛谷专栏 (luogu.com.cn)
有一个需要解释的点关于ans为什么等于r-l1比如一开始我们l是1r是2sum也就是和值3小于我们的k值。此时我们就可以被r那么相应的ans也就是子矩阵放在这里就是连续子序列的个数增加了多少呢方案从“1,2,12”变成了“1,2,3,12,23,123”可以自己模拟一下会发现原来的数列里所有以i(1ix,x为当前增加的数)为开头以原本的最后一位为结尾的方案都会作为新加入的数的方案之一(也就是上面例子的23和123都是新方案)再加上这个数本身 就是r-l1。
代码如下
#includebits/stdc.h
using namespace std;
#define int long longint a[505][505] { 0 };
int s[505][505] { 0 };signed main()
{int n, m, k;cin n m k;for (int i 1;i n;i){for (int j 1;j m;j){cin a[i][j];s[i][j] s[i][j - 1] s[i - 1][j] - s[i - 1][j - 1] a[i][j];}}int ans 0;for (int i 1;i n;i){for (int j i;j n;j){//以上两个循环枚举两条线int l, r;l r 1;while (r m)//双指针{if (s[j][r] - s[j][l - 1] - s[i - 1][r] s[i - 1][l - 1] k){ans r - l 1;r;}else l;}}}cout ans;return 0;
}
