个人网站模版,wordpress 4.5.3 ueditor,关键词排名优化易下拉霸屏,txt发布wordpress题目描述
给定一个 N M 的矩阵 A#xff0c;请你统计有多少个子矩阵 (最小 1 1#xff0c;最大 N M) 满足子矩阵中所有数的和不超过给定的整数 K?
输入格式
第一行包含三个整数 N, M 和 K.
之后 N 行每行包含 M 个整数#xff0c;代表矩阵 A.
输出格式
一个整数…题目描述
给定一个 N × M 的矩阵 A请你统计有多少个子矩阵 (最小 1 × 1最大 N × M) 满足子矩阵中所有数的和不超过给定的整数 K?
输入格式
第一行包含三个整数 N, M 和 K.
之后 N 行每行包含 M 个整数代表矩阵 A.
输出格式
一个整数代表答案。
样例输入 3 4 10
1 2 3 4
5 6 7 8
9 10 11 12 样例输出 19 提示 满足条件的子矩阵一共有 19包含 大小为 1 × 1 的有 10 个。 大小为 1 × 2 的有 3 个。 大小为 1 × 3 的有 2 个。 大小为 1 × 4 的有 1 个。 大小为 2 × 1 的有 3 个。 对于 30% 的数据N, M ≤ 20. 对于 70% 的数据N, M ≤ 100. 对于 100% 的数据1 ≤ N, M ≤ 500; 0 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000. 可以用二维前缀和暴力去写 过70%样例
#includeiostream
#includealgorithm
#includecstring
#includequeue
#define int long long
using namespace std;
const int N500;
int a[N][N];
int s[N][N];
signed main()
{int n,m,k;cinnmk;for(int i1;in;i)for(int j1;jm;j) cina[i][j];for(int i1;in;i){for(int j1;jm;j){s[i][j]s[i-1][j]s[i][j-1]a[i][j]-s[i-1][j-1];}}int sum0;for(int x11;x1n;x1){for(int y11;y1m;y1){for(int x2x1;x2n;x2){for(int y2y1;y2m;y2){if(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]s[x1-1][y1-1]k) sum;else break;}}}}coutsumendl;return 0;
}
一维前缀和双指针--该题跟 在一组数中 问能有多少个区间之和小于k 的做法类似 #includeiostream
#includealgorithm
#define int long long
using namespace std;
const int N550;
int a[N][N];
int s[N][N];
signed main()
{int n,m,k;cinnmk;for(int i1;in;i){for(int j1;jm;j){cina[i][j];//计算列的前缀和--一维前缀和s[i][j]a[i][j]s[i-1][j];}}int ans0;for(int i1;in;i)//上边界{for(int i1i;i1n;i1)//下边界{for(int l1,r1,sum0;rm;r){sums[i1][r]-s[i-1][r];//确定右边界while(sumk){sum-s[i1][l]-s[i-1][l];//求符合条件的左边界l;}ansr-l1;}}}coutansendl;return 0;
}
