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

蓝桥杯刷题冲刺 | 倒计时24天

作者:指针不指南吗
专栏:蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了,最后的这几天尤为重要,不可懈怠哦🐾

文章目录

  • 1.修剪灌木
  • 2.统计子矩阵

1.修剪灌木

  • 题目

    链接: 修剪灌木 - 蓝桥云课 (lanqiao.cn)

    找到一个蓝桥官网相比acwing刷题的优点:蓝桥官网可以看ac的占比

    爱丽丝要完成一项修剪灌木的工作。

    N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌 木, 让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始, 每天向右修剪一棵灌木。当修剪了最右侧的灌木后, 她会调转方向, 下一天开 始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。

    灌木每天从早上到傍晩会长高 1 厘米, 而其余时间不会长高。在第一天的 早晨, 所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。

    输入格式

    一个正整数 N, 含义如题面所述。

    输出格式

    输出 N 行, 每行一个整数, 第 i 行表示从左到右第 i 棵树最高能长到多高。

    样例输入

    3
    

    样例输出

    4
    2
    4
    
  • 第一次

    #include<bits/stdc++.h>
    using namespace std;const int N=1e4+10;
    int a[N],m[N];int main()
    {int n;scanf("%d",&n);int k=pow(n,2)+2;while(k>0){for(int i=0;i<n;i++){for(int j=0;j<n;j++)  //每天长1{a[j]++;m[j]=max(m[j],a[j]);} a[i]=0;  //轮到的灌木,变0}for(int i=n-2;i>=1;i--)  //边界条件处理好{for(int j=0;j<n;j++){a[j]++;m[j]=max(m[j],a[j]);}a[i]=0;}k-=2;}for(int i=0;i<n;i++)printf("%d\n",m[i]);return 0;
    }
    

    简单暴力,只能 ac 30%

    我感觉 每次 所有数组元素+1,可以优化成差分

  • 第二次

    #include<bits/stdc++.h>
    using namespace std;int main()
    {int n;cin>>n;for(int i=1;i<=n;i++){cout<<max(n-i,i-1)*2<<endl; //找规律:当剪刀离灌木最远的时候,长的很高,然后返回马上要剪它的时候,最高,两倍高度;画图可知,到两个端点返回来的时候,最高}return 0;
    }
    

    在这里插入图片描述

  • 反思

    纯纯规律题,感觉错了

    发散性思维,在做蓝桥杯的时候,遇到这种 数 的题,先静下心来,找找规律

2.统计子矩阵

  • 题目

    链接: 4405. 统计子矩阵 - AcWing题库

    给定一个 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≤2.5×10810^8108

    输入样例:

    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 个。
  • 第一次

    #include<bits/stdc++.h>
    using namespace std;const int N=510;
    int s[N][N];
    int n,m,k;int sum(int dx,int dy,int x,int y)
    {int res=0;res=s[x][y]-s[x-dx][y]-s[x][y-dy]+s[x-dx][y-dy];return res;
    }int main()
    {int cnt=0;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&s[i][j]);s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];  //前缀和}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){for(int l=1;l<=n;l++)  // l,r 表示 每个小矩阵,右下角的元素for(int r=1;r<=m;r++){if(sum(i,j,l,r)<=k) cnt++;}}cout<<cnt;return 0;
    }
    

    答案错误,样例都过不了,目前还没有找出来 bug

  • 正确题解 ->前缀和+双指针

    思路

    前缀和 把数组 存起来

    用 四个指针 把 整个矩阵 分成 一小块一小块的

    左右使用 i,j 指针,上下 使用 u,d 指针

    在这里插入图片描述

    #include<bits/stdc++.h>
    using namespace std;const int N=510;
    int s[N][N];
    int n,m,k;int main()
    {scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&s[i][j]);s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];}//i表示左边界,j表示右边界,u 表示上边界,d表示下边界long long ans=0;for(int i=1;i<=m;i++)for(int j=i;j<=m;j++){for(int u=1,d=1;d<=n;d++){while(u<=d&&s[d][j]-s[u-1][j]-s[d][i-1]+s[u-1][i-1]>k) u++; //u++ 表示上边界下移,区间变小,递减if(u<=d) ans+=d-u+1;  //表示这段区间的矩阵,满足条件}}cout<<ans;return 0;
    }
    
  • 反思

    及时复习前面的知识,忘光了

    遇到矩阵和,优先想到前缀和,然后,有区间的移动问题,使用双指针

    定义变量之前,先想清楚,它的数据类型和范围

Alt

相关文章:

蓝桥杯刷题冲刺 | 倒计时24天

作者&#xff1a;指针不指南吗 专栏&#xff1a;蓝桥杯倒计时冲刺 &#x1f43e;马上就要蓝桥杯了&#xff0c;最后的这几天尤为重要&#xff0c;不可懈怠哦&#x1f43e; 文章目录1.修剪灌木2.统计子矩阵1.修剪灌木 题目 链接&#xff1a; 修剪灌木 - 蓝桥云课 (lanqiao.cn) 找…...

真正理解微软Windows程序运行机制——什么是消息

我是荔园微风&#xff0c;作为一名在IT界整整25年的老兵&#xff0c;今天说说Windows程序的运行机制。经常被问到MFC到底是一个什么技术&#xff0c;为了解释这个我之前还写过帖子&#xff0c;但是很多人还是不理解。其实这没什么&#xff0c;我在学生时代也被这个问题困绕过。…...

HTTP 缓存的工作原理

缓存是解决http1.1当中的性能问题主要手段。缓存可能存在于客户端浏览器上&#xff0c;也可以存在服务器上面&#xff0c;当使用过期缓存可能给用户展示的是错误的信息而导致一些bug。 HTTP 缓存&#xff1a;为当前请求复用前请求的响应 • 目标&#xff1a;减少时延&#xff1…...

RK3568在Android上进行驱动模块开发(源码外)

文章目录 前言一、ARCH架构二、编译器三、建立自己的Makefile文件总结前言 本文记录在驱动开发时,由于编译内核时间较长,经常会选择单独编译一个模块,这里主要讲解,makefile文件如何编写(主要是编译器和架构) 提示:以下是本篇文章正文内容,下面案例可供参考 一、ARCH…...

操作技巧 | 在Revit中借用CAD填充图案的方法

在建模过程中&#xff0c;有时需要达到多种填充效果&#xff0c;而CAD中大量的二维填充图案&#xff0c;便是最直接的资源之一。 使用 填充图案之前 使用 填充图案之后 其中要用到主要命令便是对表面填充图案的添加与编辑 简单效果 如下 模型填充与绘图填充 区别 模型填…...

Java的二叉树、红黑树、B+树

数组和链表是常用的数据结构&#xff0c;数组虽然查找快&#xff08;有序数组可以通过二分法查找&#xff09;&#xff0c;但是插入和删除是比较慢的&#xff1b;而链表&#xff0c;插入和删除很快&#xff08;只需要改变一些引用值&#xff09;&#xff0c;但是查找就很慢&…...

昨天某读者拿到华为OD岗位offer,今天来分享一下经验,包含华为OD机试

来自读者投稿&#xff0c;已经拿到华为 OD 开发岗位 offer&#xff0c;询问了一些问题&#xff0c;下面是他的一些经验。 文章目录华为 OD 投递简历华为 OD 机试分数OD 机试通过之后&#xff0c;收到综合测评OD 技术面&#xff08;时长 1 小时左右&#xff09;主管/HR 面试&…...

树的遍历方式(前中后,层序遍历,递归,迭代,Morris遍历)-----直接查询代码

目录 一.前序遍历 1.递归 2.栈迭代 3.Morris遍历 二.中序遍历 1.递归 2.栈迭代 3.Morris遍历 三.后序遍历 1.递归 2.栈迭代 3.Morris遍历 四.前中后序的统一迭代法 1.前序遍历 2.中序遍历 3.后序遍历 五.层序遍历 1.队列迭代 2.之字形层序遍历 3.锯齿形层序…...

Docker Registry部署镜像私有仓库及鉴权认证

文章目录一、Docker Registry是什么&#xff1f;二、Docker Registry部署私有仓库2.1、Docker Registry安装2.2、Docker Registry配置2.3、启动Docker Registry2.4、Docker客户端配置2.5、向Docker Registry上传和下载镜像三、Docker Registry鉴权和认证3.1、基本认证3.2、Bear…...

stm32外设-中断详解

0. 写在最前 本栏目笔记都是基于stm32F10x 1. 中断是啥&#xff1f; 什么是中断&#xff1a;CPU在处理某一事件A时&#xff0c;发生的另外某一事件B请求CPU去处理&#xff08;产生了中断&#xff09;&#xff0c;随后CPU暂时中断当前正在执行的任务&#xff0c;去对事件B进行处…...

第十四届蓝桥杯三月真题刷题训练——第 13 天

目录 第 1 题&#xff1a;特殊日期 问题描述 答案提交 运行限制 代码&#xff1a; 思路&#xff1a; 第 2 题&#xff1a;重合次数 问题描述 答案提交 运行限制 代码&#xff1a; 第 3 题&#xff1a;左移右移 问题描述 输入格式 输出格式 样例输入 样例输出…...

webgl_gpgpu_birds 样例分析

webgl_gpgpu_birds 是一个 three.js 的官方样例&#xff0c;这个例子模拟了鸟群的运动&#xff0c;是一个群组动画&#xff0c;并且动画的帧率也很高&#xff1b;鸟群的运动很自然&#xff0c;非常值得研究。类似的群组动画还有鱼群&#xff0c;boid是‘类鸟群’的英文 大概两…...

以业务行为驱动的反入侵安全能力建设

0x0 背景 最近听到一些甲方安全领域的专家分享了部分安全建设的经验&#xff0c;对安全运营下的反入侵技术能力建设有了些新的看法&#xff0c;依靠单个/多个异构的安全产品的关联能力形成的安全中台并不能在实际的攻防对抗当中占据主动地位&#xff0c;且很容易达到一个天花板…...

Unity3d C#使用DOTween插件的Sequence实现系列动画OnComplete无效和颜色设置无效的问题记录

前言 最近在弄一个文字动画效果的动画&#xff0c;使用了DOTween插件的Sequence来实现&#xff0c;主要就是对一个Text进行的文字打字、缩放和颜色设置等动画&#xff0c;功能是先对Text实现打字的动画&#xff0c;打字完成后&#xff0c;延时几秒对文字进行缩小、颜色变淡&am…...

【蓝桥杯-筑基篇】排序算法

&#x1f353;系列专栏:蓝桥杯 &#x1f349;个人主页:个人主页 目录 前言&#xff1a; 一、冒泡排序 二、选择排序 三、插入排序 四、图书推荐 前言&#xff1a; 算法工具推荐&#xff1a; 还在为数据结构发愁吗&#xff1f;这款可视化工具&#xff0c;帮助你更好的了解…...

编辑器进化 VSCode + Vim

本文作者为 360 奇舞团前端工程师VSCode 是一款非常流行的代码编辑器。它支持多种编程语言&#xff0c;拥有丰富的插件和调试功能&#xff0c;不论是处理前端工程还是后端工程&#xff0c;VSCode 都能提供给开发者优秀的用户体验。鉴于 VSCode 超高的流行度&#xff0c;我会默认…...

LearnOpenGL-高级OpenGL-6.天空盒

本人刚学OpenGL不久且自学&#xff0c;文中定有代码、术语等错误&#xff0c;欢迎指正 我写的项目地址&#xff1a;https://github.com/liujianjie/LearnOpenGLProject 文章目录天空盒介绍如何采样OpenGL纹理目标例子0&#xff1a;天空盒效果环境映射反射例子1&#xff1a;Cube…...

Printk打印内核日志

一、背景 Linux 内核中提供了内核日志打印的工具printk。它的使用方式C语言中的printf是类似的。接下来我们介绍一下printk的使用方式。本文以打印Binder中的日志为例&#xff0c;进行演示。 printk的方法声明和日志级别binder驱动中增加 打印代码android系统中查看日志信息 …...

界面控件DevExpress WPF 202计划发布的新功能合集

DevExpress WPF拥有120个控件和库&#xff0c;将帮助您交付满足甚至超出企业需求的高性能业务应用程序。通过DevExpress WPF能创建有着强大互动功能的XAML基础应用程序&#xff0c;这些应用程序专注于当代客户的需求和构建未来新一代支持触摸的解决方案。本文将介绍今年DevExpr…...

Spring Cloud Alibaba 微服务2,注册中心演变 + Nacos注册中心与配置中心

目录专栏导读一、什么是Nacos&#xff1f;二、注册中心演变及其设计思想1、RestTemplate调用远程服务2、通过Nginx维护服务列表&#xff08;upStream&#xff09;3、通过Nacos实现注册中心4、心跳版Nacos三、Nacos Discovery四、Nacos核心功能1、服务注册2、服务心跳3、服务同步…...

Navicat 图形化界面工具

Navicat 介绍 Navicat是一套可创建多个连接的数据库管理工具&#xff0c;用以方便管理 MySQL、Oracle、SQL Server等不同类型的数据库 目录 Navicat 介绍 Navicat 下载 Navicat 安装 Navicat 使用 Navicat连接MySQL数据库 Navicat创建数据库和表 Navicat 下载 1、点击这…...

2023年网络安全比赛--attack(新)数据包分析中职组(超详细)

一、竞赛时间 180分钟 共计3小时 任务环境说明: 1 分析attack.pcapng数据包文件,通过分析数据包attack.pcapng找出恶意用户第一次访问HTTP服务的数据包是第几号,将该号数作为Flag值提交; 2.继续查看数据包文件attack.pcapng,分析出恶意用户扫描了哪些端口,将全部的端口号…...

C语言之extern(七十)

extern同一个文件&#xff1a;修饰变量声明#include <stdio.h>int add(){extern int x,y;return x y; }int main(){printf("%d\n", add()); }int x 10; int y 20;extern文件之间&#xff1a;修饰函数声明<1>.add.cint sum(){extern int x ;extern in…...

树的前中后序的Morris遍历

目录 一.Morris遍历 1.什么是Morris遍历 2.基本思想 3.Morris遍历的优点和缺点 4.知识回顾----二叉树的线索化 二.中序Morris遍历 1.中序Morris遍历的分析 2.中序Morris遍历的思路 3.具体的代码实现 三.前序Morris遍历 1.前序Morris遍历的思路 2.具体的代码实现 四…...

到底什么是线程?线程与进程有哪些区别?

上一篇文章我们讲述了什么是进程&#xff0c;进程的基本调度 http://t.csdn.cn/ybiwThttp://t.csdn.cn/ybiwT 那么本篇文章我们将了解一下什么是线程&#xff1f;线程与进程有哪些区别&#xff1f;线程应该怎么去编程&#xff1f; 目录 http://t.csdn.cn/ybiwThttp://t.csdn…...

你真的知道如何系统高效地学习数据结构与算法吗?

文章目录前言&#xff1a;什么是数据结构&#xff1f;什么是算法&#xff1f;学习这个算法需要什么基础&#xff1f;学习的重点在什么地方&#xff1f;一些可以让你事半功倍的学习技巧1.边学边练&#xff0c;适度刷题2.多问、多思考、多互动3.打怪升级学习法4.知识需要沉淀&…...

Linux操作系统基础的常用命令

1&#xff0c;Linux简介Linux是一种自由和开放源码的操作系统&#xff0c;存在着许多不同的Linux版本&#xff0c;但它们都使用了Linux内核。Linux可安装在各种计算机硬件设备中&#xff0c;比如手机、平板电脑、路由器、台式计算机。1.1Linux介绍Linux出现于1991年&#xff0c…...

Jasypt加密库基本使用方法

目录 1 Jasypt简介... 2 基础知识回顾... 3 Jasypt基本加密器... 4 JasyptPBE加密器... 5 Jasypt池化加密器... 6 Jasypt客户端工具... 7 JasyptSpringboot基本用法... 8 JasyptSpringboot自定义加密器... 9 JasyptSprin…...

C++并发编程之五 高级线程管理

文章目录5.1.1 线程池5.1.1 线程池 在前面我们引入了线程的通信和同步手段&#xff0c;那么为什么还要引入线程池呢&#xff1f; 线程池是一种管理多个线程的技术&#xff0c;它可以减少线程的创建和销毁的开销&#xff0c;提高并发性能。线程池中有一定数量的空闲线程&#x…...

单片机——IIC协议与24C02

1、基础知识 1.1、IIC串行总线的组成及工作原理 I2C总线只有两根双向信号线。一根是数据线SDA&#xff0c;另一根是时钟线SCL。 1.2、I2C总线的数据传输 I2C总线进行数据传送时&#xff0c;时钟信号为高电平期间&#xff0c;数据线上的数据必须保持稳定&#xff0c;只有在时钟…...