草庐IT

试题 F: 统计子矩阵

人间花木 2023-08-15 原文

题目链接：

点击跳转

题目描述：

给定一个 N×M 的矩阵 A，请你统计有多少个子矩阵 (最小 1×1，最大 N×M) 满足子矩阵中所有数的和不超过给定的整数 K?

输入格式 第一行包含三个整数 N,M 和 K。

之后 N 行每行包含 M 个整数，代表矩阵 A。

输出格式 一个整数代表答案。

数据范围
对于 30% 的数据，N,M≤20，
对于 70% 的数据，N,M≤100，
对于 100%的数据，1≤N,M≤500;0≤Aij≤1000;1≤K≤250000000。

输入样例：

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 个。

题目分析：

  • 分析：要求整个矩阵中每个矩阵的和小于等于k的有多少个，暴力的做法是枚举每个点为起点，和枚举每个点为终点，这样就可以得到所有的子矩阵（不重不漏），但时间复杂度是O(n 4 {^4} 4),会超时，那么必有优化
  • 思路：可以从枚举每个点转换为枚举每一列，以每一列为起点，和枚举每一列为终点得到所有以起点列为上界，终点列为下届的所有矩阵。枚举每一个矩阵的长度，从 1 ~ m ,这样就可以得到所有的矩阵。
  • 此时题目就变成了求一条矩阵中能的所有子矩阵的和小于等于 k 的个数有多少个，这里就可以用 双指针的思维来做，last 代表左边界，从 1 开始， k 代表右边届，也从 1 开始，那么当前这个矩阵中能满足子矩阵的和小于等于 k 的个数就一共有 k - last + 1 个矩阵，如果当前矩阵的大小大于 k 了，那么
    last 就向前移动，一直到满足小于等于 k 位置，当 last 走到 m 点时，此时所有小于等于 k 的子矩阵的个数已经全部被算出来了。

算法1：

前缀和+双指针 – 时间复杂度O（n 3 {^3} 3）：

代码：

/*
 * @Author: suhuamo
 * @Date: 2022-04-12 11:38:35
 * @LastEditTime: 2022-04-13 15:23:13
 * @FilePath: \algorithm\蓝桥杯\第十三届蓝桥杯省赛B\F.cpp
 * @slogan: 也许散落在浩瀚宇宙的小行星们也知道
 * 知识点: 前缀和+双指针+二维优化
 * 暴力是枚举以每个点为起点,每个点为终点,需要O(n*n*n*n),但是实际上可以优化为
 * 枚举每一行为起点,每一行为终点,然后遍历每一列,并且采取贪心的做法,只会线性遍历当前这一列,
 * 优化为O(n*n*n)
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 510;
int n, m, K;
int a[N][N];
LL s[N][N];
int main()
{
    cin >> n >> m >> K;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];
    for(int j = 1; j <= m; j++)
        for(int i = 1; i <= n; i++)
            s[i][j] = s[i - 1][j] + a[i][j];
    
    LL res = 0;
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
        {
            int last = 1;
            LL sum = 0;
            for(int k = 1; k <= m; k++)
            {
                LL r = s[j][k] - s[i - 1][k];
                if(sum + r <= K)
                {
                    sum += r;
                    res += (k - last + 1);
                }
                else
                {
                    LL l = s[j][last] - s[i - 1][last];
                    while(last != k && sum + r > K)
                    {
                        sum -= l;
                        last++;
                        l = s[j][last] - s[i - 1][last];
                    }
                    if(sum + r <= K)
                    {
                        sum += r;
                        res += (k - last + 1);
                    }
                    else
                    {
                        last++;
                    }
                }
            }
        }
    cout << res << endl;
    return 0;
}
试题统计spanclasstoken算法c++蓝桥杯

有关试题 F: 统计子矩阵的更多相关文章

  1. 旋转矩阵的几何意义 - 2

    点向量坐标矩阵的几何意义介绍旋转矩阵的几何含义之前，先介绍一下点向量坐标矩阵的几何含义点：在一维空间下就是一个标量，如同一条直线上，以任意某一个位置为0点，以一定的尺度间隔为1，2，3...,相反方向为-1，-2，-3...；如此就形成了一维坐标系，这时候任何一个点都可以用一个数值表示，如点p1=5，即即从原点出发沿着x轴正方向移动5个尺度；点p2=-3，负方向移动3个尺度；     在一维坐标系上过原点做垂直于一维坐标系的直线，则形成了二维坐标系，此时描述一个点需要两个数值来表示点p3=（3，2），即从原点出发沿着x轴正方向移动3个尺度，在此基础上沿着y轴正方向移动两个尺度的位置就是点p3。

  2. Hive SQL 五大经典面试题 - 2

    目录第1题连续问题分析：解法：第2题分组问题分析：解法：第3题间隔连续问题分析：解法：第4题打折日期交叉问题分析：解法：第5题同时在线问题分析：解法：第1题连续问题如下数据为蚂蚁森林中用户领取的减少碳排放量iddtlowcarbon10012021-12-1212310022021-12-124510012021-12-134310012021-12-134510012021-12-132310022021-12-144510012021-12-1423010022021-12-154510012021-12-1523.......找出连续3天及以上减少碳排放量在100以上的用户分析：遇到这类

  3. 华为OD机试真题 C++ 实现【带传送阵的矩阵游离】【2023 Q2 | 200分】 - 2

            所有题目均有五种语言实现。C实现目录、C++实现目录、Python实现目录、Java实现目录、JavaScript实现目录题目n行m列的矩阵，每个位置上有一个元素你可以上下左右行走，代价是前后两个位置元素值差的绝对值.另外，你最多可以使用一次传送阵(只能从一个数跳到另外一个相同的数)求从走上角走到右下角最少需要多少时间。输入描述：第一行两个整数n,m，分别代表矩阵的行和列。后面n行，每行m个整数，分别代表矩阵中的元素。输出描述：一个整数，表示最少需要多少时间。

  4. ruby - 如何获取我的 Sinatra 应用程序的代码覆盖率统计信息？ - 2

    我编写了一个Sinatra应用程序(网站)，我想收集网站代码的代码覆盖率信息。我是Ruby的新手，但Google告诉我rcov是一个很好的代码覆盖工具。不幸的是，我在网上可以找到的所有信息只显示了如何获取有关测试用例的代码覆盖率信息-我想要有关我的站点本身的代码覆盖率信息。我想要分析的特定站点文件位于“sdk”和“sdk/vendor”目录中，因此我通常使用“rubysite.rb”运行我的站点的地方我改为尝试以下操作:rcov-Isdk-Isdk/vendorsite.rb它显示了Sinatra启动文本，但随后立即退出，而不是像我的Sinatra应用程序通常那样等待网络请求。有人能告

  5. ruby-on-rails - 收集 Rails 应用程序使用统计信息的最佳方式 - 2

    我有一个Rails应用程序，用户可以在其中设置他们的域并在其中发布内容。我需要收集公共(public)流量统计信息，例如网页浏览量等。此功能的一个很好的例子是我作为客户可以看到的flickr使用统计信息。问题是收集使用信息的最佳方式是什么。应该通过解析日志文件来完成还是应该在运行时收集并存储在数据库中？是否有任何工具或Rails插件已经提供了此功能？此解决方案应该可以很好地扩展，即使每月有数千个域和数百万次网页浏览。 最佳答案 GoogleAnalytics可能是您最好的选择... 关于

  6. 欧拉角表示的姿态矩阵（313和312转序） - 2

    一、习惯约定图片来自PSINS（高精度捷联惯导算法）PSINS工具箱入门与详解.pptx二、基本旋转矩阵绕x轴逆时钟旋转α\alphaα角度Rx(α)=[ 1000cos⁡αsin⁡α0−sin⁡αcos⁡α]R_x(\alpha)=\begin{bmatrix}\1&0&0\\0&\cos\alpha&\sin\alpha\\0&-\sin\alpha&\cos\alpha\end{bmatrix}Rx​(α)=​ 100​0cosα−sinα​0sinαcosα​​绕y轴逆时钟旋转α\alphaα角度Ry(α)=[ cos⁡α0−sin⁡α010sin⁡α0cos⁡α]R_y(\alpha

  7. 欧拉角、旋转矩阵及四元数 - 2

    欧拉角、旋转矩阵及四元数1.简介2.欧拉角2.1欧拉角定义2.2右手系和左手系2.3转换流程3.旋转矩阵4.四元数4.1四元数与欧拉角和旋转矩阵之间等效变换4.2测试Matlab代码5.总结1.简介常用姿态参数表达方式包括方向余弦矩阵、欧拉轴/角参数、欧拉角、四元数以及罗德里格参数等。高分辨率光学遥感卫星主要采用欧拉角与四元数对姿态参数进行描述。这里着重讲解欧拉角、旋转矩阵和四元数。2.欧拉角2.1欧拉角定义欧拉角是表征刚体旋转的一种方法之一，由莱昂哈德·欧拉引入的三个角度，用于描述刚体相对于固定坐标系的方向。在摄影测量、空间科学或其它技术领域，一般用一组（三个）欧拉角描述两个空间坐标之间的旋

  8. 蓝桥杯C/C++VIP试题每日一练之报时助手 - 2

    ?作者主页：静Yu?简介：CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家，前端知识交流社区创建者?社区地址：前端知识交流社区?博主的个人博客：静Yu的个人博客?博主的个人笔记本：前端面试题个人笔记本只记录前端领域的面试题目，项目总结，面试技巧等等。接下来会更新蓝桥杯官方系统基础练习的VIP试题，依然包括解题思路，源代码等等。问题描述：给定当前的时间，请用英文的读法将它读出来。时间用时h和分m表示，在英文的读法中，读一个时间的方法是：　　如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“threeo’clock”。　　如果m不为0，则将时读出来，然后将分读出来，如5

  9. ruby - 如何修改矩阵(Ruby std-lib Matrix 类)？ - 2

    我理解RubystdlibMatrix是不可修改的，也就是说，例如。m=Matrix.zero(3,4)不会写m[0,1]=7但我非常想做...我可以用笨拙的编程来做，比如defmodify_value_in_a_matrix(matrix,row,col,newval)ary=(0...m.row_size).map{|i|m.rowi}.map(&:to_a)ary[row][col]=newvalMatrix[*ary]end...或者作弊，比如Matrix.send:[]=,0,1,7但我想知道，这一定是人们一直遇到的问题。有没有一些标准的、习惯的方法可以做到这一点，而不必使用

  10. 线性代数让我想想：快速求三阶矩阵的逆矩阵 - 2

    快速求三阶矩阵的逆矩阵前言一般情况下，我们求解伴随矩阵是要注意符号问题和位置问题的（如下所示）A−1=1[  ][−[  ]−[  ]−[  ]  −[  ]]=A−1=1[  ][   M11−[M12]   M13−[M21]   M22−[M23]     M31−[M32]   M33]⊤\begin{aligned}&A^{-1}=\frac{1}{[\\]}\left[\begin{array}{cccccc}&-[\\]&\\-[\\]&&-[\\]\\\\&-[\\]&\\\end{array}\right]=\\\\&A^{-1}=\frac{1}{[\\]}\left[\b

随机推荐