第十三届蓝桥杯 C++ B 组省赛 F 题——统计子矩阵
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
【问题描述】
给定一个 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 ≤ A i j ≤ 1000; 1 ≤ K ≤ 250000000 .
Java代码AC
import java.io.*;
public class Main {
static int N=510;
static int n,m,k;
static int[][] a=new int[N][N];
static int[][] s=new int[N][N];
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String[] ts = br.readLine().split(" ");
n=Integer.parseInt(ts[0]);
m=Integer.parseInt(ts[1]);
k=Integer.parseInt(ts[2]);
for (int i=1;i<=n;i++){
ts=br.readLine().split(" ");
for (int j=1;j<=m;j++){
a[i][j]=Integer.parseInt(ts[j-1]);
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
long res=0;
for (int x1=1;x1<=n;x1++){
for (int x2=x1;x2<=n;x2++){
int l=1;
int r=1;
while (r<=m){
while (l<=r&&!check(x1,l,x2,r)) l++;
res+=(long)r-l+1;
r++;
}
}
}
System.out.println(res);
}
public static boolean check(int x1,int y1,int x2,int y2){
return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<=k;
}
}