小秋的矩阵

server/2025/3/17 22:47:11/

0小秋的矩阵 - 蓝桥云课

问题描述

给你一个 n 行 m 列只包含 0 和 1 的矩阵,求它的所有子矩阵中,是方阵而且恰好包含 k 个 0 的数量。

方阵是行数和列数相等的矩阵

矩阵是从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序),被称为原矩阵的一个子矩阵

输入格式

第 1 行输入 3 个整数 n, m, k,表示矩阵的行数,列数和所求子矩阵包含 0 的数量。

接下来 n 行,每行输入 m 个整数,第 i 行表示给定矩阵的第 i 行。

输出格式

输出仅一行,包含 1 个整数,表示答案。

样例输入

3 4 2
0 1 1 0
1 0 0 1
0 1 0 0

样例输出

4

说明

共有 4 个阶数为 2 的方阵符合条件,左上角的坐标分别为 (1,1), (1,2), (1,3), (2,1)。

评测数据规模

  • 对于 20% 的评测数据,1 ≤ n × m ≤ 10³。
  • 对于 40% 的评测数据,1 ≤ n × m ≤ 10³。
  • 对于 100% 的评测数据,1 ≤ n × m ≤ 10⁶,0 ≤ k ≤ n × m。

运行限制

语言最大运行时间最大运行内存
C1s256M
C++1s256M
Python33s256M
Java2s256M
PyPy33s256M
Go3s256M

思路:

我们可以把0变成1,1变成0.这样计算0的数量就变成计算1的数量。之后就是正常的前缀和>二维前缀和,枚举正方形。

有两个点:

1.找出每一个正方形的(x1,y1),(x2,y2)

2.边长的取值范围
代码如下:

#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e3+10;
int n,m,k,ans;
int a[N][N];
int pre[N][N];
int main() 
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m >> k;for(int i = 1 ; i <= n ; i++){for(int j = 1 ; j <= m ; j++)//0和1变换,然后求出子矩阵包含k个1的数量 {int temp;cin >> temp;if(temp == 1)a[i][j] = 0;else if(temp == 0) a[i][j] = 1; }}for(int i = 1 ; i <= n ; i++){for(int j = 1 ; j <= m ; j++){pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[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 max_len = min(n - i + 1, m - j + 1);for (int l = 1; l <= max_len; l++)// 枚举边长 {int x2 = i + l - 1;int y2 = j + l - 1;int x1 = i;int y1 = j; int sum = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1];if (sum == k) {ans++;}}}}cout << ans;return 0;
}


http://www.ppmy.cn/server/175800.html

相关文章

【TCP】三次挥手,四次挥手详解--UDP和TCP协议详解

活动发起人小虚竹 想对你说&#xff1a; 这是一个以写作博客为目的的创作活动&#xff0c;旨在鼓励大学生博主们挖掘自己的创作潜能&#xff0c;展现自己的写作才华。如果你是一位热爱写作的、想要展现自己创作才华的小伙伴&#xff0c;那么&#xff0c;快来参加吧&#xff01…

【CSS】二、浏览器调试与文字样式

文章目录 1、谷歌调试前端代码2、文字属性控制2.1 字体大小2.2 字体粗细2.3 字体倾斜2.4 行高2.5 字体族2.6 复合属性2.7 文本缩进2.8 文本对齐方式2.9 文本修饰线2.10 文字颜色 3、练习 1、谷歌调试前端代码 CommandOptionI或者F12打开开发者模式&#xff0c;选中元素栏Eleme…

单片机的历史与发展

单片机&#xff08;MCU&#xff09;的发展历程贯穿了从微型计算机雏形到高度集成化智能芯片的技术演进&#xff0c;其历史可分为以下关键阶段&#xff1a; 一、萌芽与探索&#xff08;1971-1976&#xff09; 这是一个从微处理器到单片机的阶段。 1971 年&#xff0c;Intel 推出…

初阶数据结构(C语言实现)——5.2 二叉树的顺序结构及堆的实现

1.二叉树的顺序结构及实现 1.1 二叉树的顺序结构 普通的二叉树是不适合用数组来存储的&#xff0c;因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储&#xff0c;需要注意的是这里的堆和操作系统…

Centos 7 在线磁盘扩容

lsblk df -Th 查看磁盘信息 df -Th 1 查看物理卷 pvs 或者 pvdisplay 或者 pvscan [rootoracledb Thu Mar 13 13:53:44 /]# pvs PV VG Fmt Attr PSize PFree /dev/sda3 centos lvm2 a-- <237.28g 0 /dev/sdb1 centos lvm2 a-- <1…

经历过的IDEA+Maven+JDK一些困惑

注意事项&#xff1a;由于使用过程中是IDEA绑定好另外2个工具&#xff0c;所以报错统一都显示在控制台&#xff0c;但要思考和分辨到底是IDEA本身问题导致的报错&#xff0c;还是maven导致的 标准配置 maven Java Compiler Structure 编辑期 定义&#xff1a;指的是从open pr…

LOWORD(wParam) 与 HIWORD(wParam) 详解

书籍&#xff1a;《Visual C 2017从入门到精通》的2.3.8 Win32控件编程 环境&#xff1a;visual studio 2022 内容&#xff1a;【例2.29】模拟对话框 说明&#xff1a;以下内容大部分来自腾讯元宝。 ​1. 基本概念与作用 LOWORD 和 HIWORD 是 Windows API 中用于分解 32 位…

从零开始的 Kafka 学习(三)| 创建主题

1. 创建主题 Topic 主题是 Kafka 中消息的逻辑分类&#xff0c;但是这个分类不应该是固定的&#xff0c;而是应该由外部的业务场景进行定义&#xff08;注意&#xff1a;Kafka 中其实是有两个固定的&#xff0c;用于记录消费者偏移量和事务处理的主题&#xff09;&#xff0c;…