P8783 [蓝桥杯 2022 省 B] 统计子矩阵

92 阅读 0 评论 61 点赞

我是靠谱客的博主凶狠篮球，最近开发中收集的这篇文章主要介绍P8783 [蓝桥杯 2022 省 B] 统计子矩阵，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

给定一个 N times MN×M 的矩阵 AA，请你统计有多少个子矩阵 (最小 1 times 11×1, 最大 N times M)N×M) 满足子矩阵中所有数的和不超过给定的整数 KK。

输入格式

第一行包含三个整数 N, MN,M 和 KK。

之后 NN 行每行包含 MM 个整数, 代表矩阵 AA。

输出格式

一个整数代表答案。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

【样例说明】

满足条件的子矩阵一共有 1919，包含:

大小为 1 times 11×1 的有 1010 个。

大小为 1 times 21×2 的有 33 个。大小为 1 times 31×3 的有 22 个。

大小为 1 times 41×4 的有 11 个。

大小为 2 times 12×1 的有 33 个。

【评测用例规模与约定】

对于 30 %30% 的数据, N, M leq 20N,M≤20.

对于 70 %70% 的数据, N, M leq 100N,M≤100.

对于 100 %100% 的数据, 1 leq N, M leq 500,0 leq A_{i j} leq 1000,1 leq K leq 2.5times10^81≤N,M≤500,0≤Aij≤1000,1≤K≤2.5×108.

蓝桥杯 2022 省赛 B 组 F 题。

暴力解法

（1）改变滑动窗口的大小来获得不同大小的矩阵和

（2）使用滑动窗口，横向和纵向两个方向进行窗口扫描；

结果（洛谷直接WA）Jesus

package newPro;
import java.util.*;
public class pro11 {
static int N,M,K;
static int A[][];
static int cnt=0;
public static void main(String []args)
{
Scanner in=new Scanner(System.in);
N=in.nextInt();
M=in.nextInt();
K=in.nextInt();
A=new int[N][];
for(int i=0;i<N;i++)
A[i]=new int[M];
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
A[i][j]=in.nextInt();
}
int i,j;
for(int n=1;n<=N;n++)
{
for(int m=1;m<=M;m++)
{
for(i=0,j=0;i<N&&j<M;i=i+n,j=j+m)
{
find(i,j,n,m);
}
}
}
System.out.print(cnt);
}
public static void find(int px,int py,int n,int m)
{
//横向滑动窗口
for(int i=px,j=py;j<M;j++)
{
int t=sumAll(i,j,n,m);
if(t!=-1&&t<=K) cnt++;
}
//纵向滑动窗口
for(int i=px+n,j=py;i<N;i++)
{
int t=sumAll(i,j,n,m);
if(t!=-1&&t<=K) cnt++;
}
}
public static int sumAll(int px,int py,int n,int m)
{
int sum=0;
if(px+n>N||py+m>M) return -1;
for(int i=px;i<n+px;i++)
{
for(int j=py;j<m+py;j++)
{
sum+=A[i][j];
}
}
return sum;
}
}

前缀二维数组，搬运：二维前缀和简单总结_做一只大熊猫的博客-CSDN博客_二维前缀和

双指针+前缀和：（答主的思路太优秀了）第十三届蓝桥杯 C++ B 组省赛 F 题——统计子矩阵（AC）_执梗的博客-CSDN博客

package newPro;
import java.util.*;
public class pro11 {
static int N,M,K;
static int num[][];
static int s[][];
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
N=in.nextInt();
M=in.nextInt();
K=in.nextInt();
num=new int[N+1][M+1];
s=new int[N+1][M+1];
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{num[i][j]=in.nextInt();
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+num[i][j];
}
}
long cnt=0;
int x1,x2,l,r;
for(x1=1;x1<=N;x1++)
{
for(x2=x1;x2<=N;x2++)//从下一个指标开始
{
for(l=1,r=1;r<=M;r++)
{
while(l<=r&&Mysum(x1,l,x2,r)>K) l++;
cnt+=(r-l+1);
}
}
}
System.out.println(cnt);
}
public static int Mysum(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];
}
}