当前位置: 首页 > news >正文

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

题目描述

给定一个 N×M 的矩阵 A,请你统计有多少个子矩阵 (最小 1×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

说明/提示

【样例说明】

满足条件的子矩阵一共有 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≤Aij​≤1000,1≤K≤2.5×10^8.

蓝桥杯 2022 省赛 B 组 F 题。

80代码 O(n^4)

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=1e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
int qsm(int x,int n)
{int res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;} return res;
}
int n,m,k;
int a[510][510];
int sum[510][510];
signed main()
{cin>>n>>m>>k;fp(i,1,n){fp(j,1,m){cin>>a[i][j];sum[i][j]=sum[i][j-1]+sum[i-1][j]+a[i][j]-sum[i-1][j-1];}}int cnt=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int t=i;t<=n;t++){for(int f=j;f<=m;f++){int x=sum[t][f]-sum[i-1][f]-sum[t][j-1]+sum[i-1][j-1];if(x<=k)cnt++;}}}}cout<<cnt<<"\n";return 0;
} 

 100代码O(n^3)

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fp(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
const int N=1e5+10;
const int mod=1e9+7;
const double eps=1e-5;
typedef double db;
int qsm(int x,int n)
{int res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;} return res;
}
int n,m,k;
int a[510][510];
int sum[510][510];
signed main()
{cin>>n>>m>>k;fp(i,1,n){fp(j,1,m){cin>>a[i][j];sum[i][j]=sum[i-1][j]+a[i][j];}}int cnt=0;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){int s=0;for(int l=1,r=1;r<=m;r++){s+=sum[j][r]-sum[i-1][r];while(s>k){s-=sum[j][l]-sum[i-1][l];l++;}cnt+=r-l+1;}}}cout<<cnt<<"\n";return 0;
} 

相关文章:

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

题目描述 给定一个 NM 的矩阵 A&#xff0c;请你统计有多少个子矩阵 (最小 11, 最大 NM) 满足子矩阵中所有数的和不超过给定的整数 K。 输入格式 第一行包含三个整数 N, M和 K。 之后 N 行每行包含 M 个整数, 代表矩阵 A。 输出格式 一个整数代表答案。 输入输出样例 输入 #1 3…...

解决在部署springboot项目的docker中执行备份与之相连接的mysql容器命令

文章目录 问题描述解决思路问题解决容器构建mysql客户端安装容器与主机的交互docker中执行 mysqldump 命令解决mysql8密码验证问题解决密码插件警告 问题描述 由于&#xff0c;使用1panel可视化的面板来部署springboot项目&#xff0c;可以很方便地安装和使用mysql&#xff0c…...

正文Delphi XE Android下让TMemo不自动弹出键盘

用TMemo来显示一段说明文字&#xff0c;可一点Memo,就弹出键盘&#xff0c;找了半天控制键盘的属性&#xff0c;没找到。最后将readOnly设置为True搞定。 如果需要一个form都不显示keyboard,那么可以利用全局变量 VKAutoShowMode来控制&#xff0c;这个全局变量可以有下面三个值…...

[1Panel]开源,现代化,新一代的 Linux 服务器运维管理面板

测评介绍 本期测评试用一下1Panel这款面板。1Panel是国内飞致云旗下开源产品。整个界面简洁清爽&#xff0c;后端使用GO开发&#xff0c;前端使用VUE的Element-Plus作为UI框架&#xff0c;整个面板的管理都是基于docker的&#xff0c;想法很先进。官方还提供了视频的使用教程&…...

PG集合查询

1.运算符 1.1 union并集 连接上下语句 union distinct连接并且去重 all不去重 1.2 intersect交集 上下交集 distinct连接并且去重 all不去重 1.3 except除外 上面除了下面 distinc去重 all不去重...

目标检测应用场景和发展趋势

参考&#xff1a; 目标检测的未来是什么&#xff1f; - 知乎 (zhihu.com)https://www.zhihu.com/question/394900756/answer/32489649815大应用场景 1 行人检测&#xff1a; 遮挡问题&#xff1a;行人之间的互动和遮挡是非常常见的&#xff0c;这给行人检测带来了挑战。非刚性…...

Confluence 自定义博文列表

1. 概述 Confluence 自有博文列表无法实现列表自定义功能&#xff0c;实现该需求可采用页面中引用博文宏标签控制的方式 2. 实现方式 功能入口&#xff1a; Confluence →指定空间→创建页面 功能说明&#xff1a; &#xff08;1&#xff09;页面引用博文宏 &#xff08;…...

chrome历史版本下载

chrome历史版本下载 windows Google Chrome all versions on Windows linux版本 Google Chrome 64bit Linux版_chrome浏览器,chrome插件,谷歌浏览器下载,谈笑有鸿儒...

Messari发布Moonbeam简报,每日交易量稳步增长,首次公布利润数据

区块链数据公司Messari首次发布Moonbeam项目分析简报&#xff0c;从项目市值、链上数据表现、质押以及Moonbeam的技术优势XCM使用量等角度全面分析。这个再熊市初期上线的项目一直在默默开发&#xff0c;并在跨链互操作领域拥有了相当的实操成绩。我们翻译了Messari简报中的部分…...

数据库 锁、索引、在实际开发中怎么设置和优化

数据库锁和索引是数据库管理的两个重要方面&#xff0c;它们对于确保数据的一致性和提高查询性能具有重要作用。在实际开发中&#xff0c;正确地设置和优化锁和索引对于构建高效、稳定的系统至关重要。下面是一些关于如何在实际开发中设置和优化锁和索引的建议&#xff1a; 锁…...

超详细彻底卸载Anaconda详细教程

一、在开始处打开Anaconda Prompt 二、打开后&#xff0c;输入conda install tqdm -f命令并按回车键 conda install tqdm -f三、之后页面会出现一个WANNING&#xff0c;这个我们不用在意&#xff0c;然后会出现一个y/n提示框&#xff0c;在这里我们输入y或者Y y四、输入cond…...

Python--随机出拳(random)--if判断--综合案例练习:石头剪刀布

注&#xff1a;涉及相关链接&#xff1a; Python&#xff1a;if判断--综合案例练习&#xff1a;石头剪刀布-CSDN博客 Python语言非常的强大&#xff0c;强大之处就在于其拥有很多模块&#xff08;module&#xff09;&#xff0c;这些模块中拥有很多别人已经开发好的代码&…...

微信小程序里配置less

介绍 在微信小程序里&#xff0c;样式文件的后缀名都是wxss&#xff0c;这导致一个问题&#xff0c;就是页面样式过多的时候&#xff0c;要写很多的类名来包裹&#xff0c;加大了工作量&#xff0c;还很有可能会写错样式。这时可以配置一个less&#xff0c;会大大提高代码编辑…...

MySq修改配置文件

要修改 MySQL 的配置文件,您可以按照以下步骤进行操作: 1、打开 MySQL 的配置文件 在大多数 Linux 系统上,默认的配置文件路径是 /etc/my.cnf 或 /etc/mysql/my.cnf。您可以使用文本编辑器(如 vim、nano)以管理员权限打开该文件。 sudo vim /etc/my.cnf 2、进行修改 …...

HTML 表格及练习

表格 概述 表格是一种二维结构&#xff0c;横行纵列。 由单元格组成。 表格是一种非常“强” 的结构&#xff1a; 每一行有相同的列数&#xff08;单元格&#xff09;&#xff0c;每一列有相同的行数&#xff08;单元格&#xff09; 同一列的单元格&#xff0c;宽度&#…...

YOLOv5-训练自己的VOC格式数据集(VOC、自建数据集)

YOLOv5&#xff1a;训练自己的 VOC 格式数据集 1. 自定义数据集 1.1 环境安装 pip install -r requirements.txt -i https://pypi.tuna.tsinghua.edu.cn/simple注意&#xff1a; 安装 lxmlPillow 版本要低于 10.0.0&#xff0c;解释链接: module ‘PIL.Image’ has no attri…...

基于Java的考研信息查询系统设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09; 代码参考数据库参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者&am…...

Linux性能优化--性能追踪:受CPU限制的应用程序(GIMP)

10.0 概述 本章包含了一个例子&#xff1a;如何用Linux性能工具在受CPU限制的应用程序中寻找并修复性能问题。 阅读本章后&#xff0c;你将能够&#xff1a; 在受CPU限制的应用程序中明确所有的CPU被哪些源代码行使用。用1trace和oprofile弄清楚应用程序调用各种内部与外部函…...

BERT变体(1):ALBERT、RoBERTa、ELECTRA、SpanBERT

Author:龙箬 Computer Application Technology Change the World with Data and Artificial Intelligence ! CSDNweixin_43975035 *天下之大&#xff0c;虽离家万里&#xff0c;何处不可往&#xff01;何事不可为&#xff01; 1. ALBERT \qquad ALBERT的英文全称为A Lite versi…...

域控操作二:设置域用户使用简单密码

过程太多简单 直接写出路径更改即可 组策略—计算机配置----策略—Windows设置–安全设置----账户策略–密码策略 按自己想法改就行了 注意一点&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 要么自己设置策略&#xff0c;要么从默认策略改&#xff01;&am…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...

高分辨率图像合成归一化流扩展

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 1 摘要 我们提出了STARFlow&#xff0c;一种基于归一化流的可扩展生成模型&#xff0c;它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流&#xff08;TARFlow&am…...