​ 【蓝桥杯】每日四道编程题(两道真题+两道模拟)​| 第6天

news/2024/2/28 11:44:57

专栏: 蓝桥杯——每日四道编程题(两道真题+两道模拟)
“蓝桥杯就要开始了,这些题刷到就是赚到”
₍ᐢ..ᐢ₎
另一个专栏: 蓝桥杯——每日四道填空题(两道真题+两道模拟题)

专题前瞻:复习并查集、Tire字符串、双指针、二分

目录

第一道真题(日志统计)

输出描述

输入输出样例

第二道真题(合根植物)

输出描述

输入输出样例

第三道模拟题(acwing):Trie字符串统计

第四道真题(扫地机器人)

题目描述


第一道真题(日志统计)

 

输出描述

按从小到大的顺序输出热帖 id。每个 id 一行。

输入输出样例

输入:

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出;

1
3

运行限制
最大运行时间:1s
最大运行内存: 256M

双指针思想!(滑动窗口类型)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
pair<int,int> pll[N]; //存时间和id 
int cnt[N]; //存id对应的点赞数;
int n , d, k ;
bool rit[N]; //存满足条件的“热帖”id
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>d>>k;for (int i = 0 ; i < n ; ++i){cin>>pll[i].first>>pll[i].second;}sort(pll , pll + n); //默认是按first进行排序,这里把时间就行排序,方便双指针维护满足要求的时间区间。for (int i = 0 , j = 0 ; i < n ; ++i ) //滑动窗口的类型,i在前, j在后{int t = pll[i].second;//把每个获赞的帖子id存下来cnt[t]++; //出现一次,就给该帖子记录一个赞。while (pll[i].first - pll[j].first >= d) //注意时间是从0开始的,并且是前闭后开!!{cnt[pll[j].second]--;//不满足时间区间了,就可以把它的赞取消啦,它不可能成为热帖了。j++; //j指针记得往前走,保证区间是满足时间要求的。}if (cnt[t] >= k)  rit[t] = true; //记录下满足热帖编号,方便输出哦。}for (int i = 0 ; i < N ; ++i)  //输出满足条件的id{if (rit[i]) cout<<i<<endl;}return 0;
}

总结:

双指针的三个关键点

  • 指针的起始位置的选取
  • 指针的移动方向
  • 指针的移动速度

双指针一般有如如下几种类型;

快慢指针: 两个指针,一个步长大,一个步长小,

 对撞指针两个指针分别指向数组的开头和结尾,通过循环来完成题目。例如求回文串。

 滑动窗口:两个指针分别代表窗口的左边界和右边界,然后根据条件移动两个指针来维护这段区间,就比如上面那道例题。

 总之,这个双指针非常灵活,你不必局限于上述三个大方向。可以相互结合,互相穿插。

就比如 【蓝桥杯】每日四道编程题(两道真题+两道模拟)| 第一天 里面那道统计子矩阵。通过上下边界指针的移动,来搜索每个子矩阵。

所以我认为双指针一般都是将这种形式(O(n^{2}))

for ( int i = 0 ; i < n ; ++i)
{for (int j = 0 ; j < n ; ++j){................}
}

优化成这样的形式(O(n))的。(当然i 和 j 指针不一定都从0起点开始,根据具体体条件而定,反正代码基本都是这种形式的)

for (int i = 0 , j = 0 ; j < n ; ++j)
{while (j < i && check(i ,j))...................
}

第二道真题(合根植物)

 比如:5×4 的小格子,编号:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20

输出描述

输出植物数量。

输入输出样例

输入样例:

5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17

输出样例:

5

样例说明,其合根情况参考下图:

 运行限制

  • 最大运行时间:2s
  • 最大运行内存: 256M

复习并查集(O(n^{})):是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题(即所谓的并、查) ,一般有find()函数(找父节点)、merge()函数(合并集合)、pre[ ]数组(记录每个集合,并且指明其前驱节点是谁?)

#include <iostream>
using namespace std;int n,m,k;
int p[1000010];//要1e6  1000*1000int find(int x)
{return x==p[x]?x:p[x]=find(p[x]);
}int main()
{cin>>n>>m>>k;int  root=n*m;for(int i=1;i<=root;i++) p[i]=i;while(k--){int a,b;cin>>a>>b;if(find(a)!=find(b)){p[find(a)]=find(b);root--;}}cout<<root;return 0;
}

想再检测一下自己,就再做一道2019省赛的真题吧。【蓝桥杯】​蓝桥杯——每日四道编程题(两道真题+两道模拟)​| 第 二 天里面那道修改数组吧

第三道模拟题(acwing):Trie字符串统计

输入样例:

 

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例:

1
0
1

时/空限制:1s / 64MB

复习Tire 字符串的使用:(快速高效查找字符串集合的数据结构

Tire树又称字典树或前缀树,是一种能够快速查找一组字符串含有一个字符串的类似哈希表的树结构,是以空间换时间,利用字符串的前缀来降低查询时间。

与二叉树不同,Tire树26子节点对应26个字母,根节点不包含字符串,从根节点到某个节点,经过的字符连起来的字符串就是对应的字符串。当储存结束一个字符串后,尾节点会用cnt[ ]数组来说明该字符串的次数。

当然你可以根据这个思想,运用在其他方面,例如存二进位,快速查找其最大异或对

//开始先定义 : int son[N][26], cnt[N], idx;//son[N][26]:储存子节点的位置,分支最多26条//cnt[N]:存储以节点结尾的字符串个数//idx:表示当前要插入的节点(新建节点)
#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N][26],b[N],n,idx;
char c[N];
void insert(char c[]){int p=0;for(int i=0;c[i];++i){int u=c[i]-'a';if(!a[p][u]) a[p][u]=++idx;p=a[p][u];}b[p]++;
}
int query(char c[])
{int p=0;for(int i=0;c[i];++i){int u=c[i]-'a';if(!a[p][u]) return 0;p=a[p][u];}return b[p];
}
int main()
{cin>>n;while(n--){char t;cin>>t;if(t=='I'){cin>>c;insert(c);}else{cin>>c;printf("%d\n",query(c));}}return 0;
}

第四道真题(扫地机器人)

题目描述

小明公司的办公区有一条长长的走廊,由 NN 个方格区域组成,如下图所示。

走廊内部署了 KK 台扫地机器人,其中第 ii 台在第 A_iAi​ 个方格区域中。已知扫地机器人每分钟可以移动到左右相邻的方格中,并将该区域清扫干净。

请你编写一个程序,计算每台机器人的清扫路线,使得

  1. 它们最终都返回出发方格,

  2. 每个方格区域都至少被清扫一遍,

  3. 从机器人开始行动到最后一台机器人归位花费的时间最少。

注意多台机器人可以同时清扫同一方块区域,它们不会互相影响。

输出最少花费的时间。 在上图所示的例子中,最少花费时间是 6。第一台路线:2-1-2-3-4-3-2,清 扫了 1、2、3、4 号区域。第二台路线 5-6-7-6-5,清扫了 5、6、7。第三台路线 10-9-8-9-10,清扫了 8、9 和 10。

 

 输入样例:

10 3
5
2
10

输出样例:

6
  • 最大运行时间:1s
  • 最大运行内存: 256M

复习二分(题解来自蓝桥杯)

/*
解题思路:
本题为一道比较明显的二分题目。题目要求最少花费时间。由于每个机器人的工作时间可能不同,那么这些机器人各自的花费时间中的最大值(设为 t )的就是本题要求的答案,
需要做的是使得 t 最小。将最大花费时间(t)最小化,显然需要使用二分求解。假设某个机器人需要清扫 a,b,c,d 四个格子,因为这个机器人清扫完还需要回到最初始的位置,所以无论这个机器人初始位置在什么地方,
其清扫路径的本质都是重复两次 a 到 b,b 到 c,c 到 d 的过程,花费时间为 6,由此,假设某个机器人清扫的格子范围为 l, 
那么这个机器人花费的时间为 (l-1)\times*2。所以只需要对机器人清扫的范围(l)进行二分即可,最后的答案为 t=(l-1)\times*2。显然当每个机器人清扫的范围大小相同时,花费时间最小。
可以对清扫范围进行二分,然后验证其答案的正确性即可,判断条件是清扫范围可以使得每个格子都能够扫到可以明显的知道,最左边的格子由左边第一台机器人清扫,花费时间是最少的,在此可以采用贪心的思想,
让每台机器人都要优先清扫其左边还未扫的到格子,然后再往右扫,在二分得到的范围下往右扫得越多越好,
这样可以减少右边下一个机器人需要往左扫的范围,增加其往右扫的范围,以此类推,可减少清扫时间。综上,本题采用二分加贪心的思想解答。 
*/
#include<bits/stdc++.h>
using namespace std;int robot[1000005];//机器人位置
int n, k;bool check(int len)
{int sweep = 0;//sweep代表清扫到了哪个位置for(int i = 1; i <= k; i++){if(robot[i] - len <= sweep)//如果当前机器人只扫左侧,能够覆盖左侧未清扫的位置,则可进行当前机器人的清扫{if(robot[i] <= sweep)//如果当前机器人已经处于清扫过的位置,则当前机器人只扫右侧区域sweep = robot[i] + len - 1;else//否则从上一个清扫到的位置继续sweep += len;}else//当前机器人只扫左侧,不能覆盖左侧未清扫的位置,当前方案不可行,返回return 0;//cout<<sweep<<endl;}return sweep>=n; //表示当前方案可行
}int main()
{cin >> n >> k;for(int i = 1; i <= k; i++){cin >> robot[i];}sort(robot + 1, robot + k + 1);//首先对机器人的位置进行排序int L=0, R=n, M, ans;while(L <= R)//二分清扫范围{M = (L + R) / 2;if(check(M))//如果当前方案可行,则缩小清扫范围,试图寻找更小的方案{R = M - 1;ans = M;}else//如果方案不可行,则扩大清扫范围,寻找可行方案L = M + 1;}cout << (ans - 1) * 2 << endl;//计算并输出答案return 0;
}

 

 


http://www.ppmy.cn/news/37909.html

相关文章

C++面向对象高级编程(下)

C面向对象高级编程(上) C面向对象高级编程(下) 泛型编程&#xff08;Generic Programming&#xff09;(模板) 和面向对象编程&#xff08;Object-Oriented Programming&#xff09;虽然分属不同思维&#xff0c;但它们正是C的技术主流&#xff1b; 深入探索面向对象之继承关…

电影《铃芽之旅》观后感

这周看了电影《铃芽之旅》&#xff0c;整部电影是新海诚的新作。电影讲述的是女主铃芽为了关闭往门&#xff0c;在日本旅行中&#xff0c;遭遇灾难的故事。 &#xff08;1&#xff09;往昔记忆-往昔之物 电影中&#xff0c;有很多的“往门”&#xff0c;换成中国的话说&#xf…

TiDB入门篇-数据物理备份和恢复

简介 快照备份是集群全量备份的一种实现。它基于 TiDB 的多版本并发控制 (MVCC) 实现&#xff0c;将指定快照包含的所有数据备份到目标存储中。备份下来的数据大小约等于集群&#xff08;压缩后的&#xff09;单副本数据大小。备份完成之后&#xff0c;你可以在一个空集群或不…

工厂模式(简单工厂 工厂方法 抽象工厂)

简单工厂模式 简单工厂模式又叫做静态工厂方法模式&#xff08;static Factory Method pattern&#xff09;,它是通过使用静态方法接收不同的参数来返回不同的实例对象&#xff08;这些产品类继承自一个父类或接口&#xff09;。 简单工厂模式是由一个工厂对象决定创建出哪一种…

VR全景餐厅, 全景VR新颖的沉浸式就餐体验

随着科技的不断发展&#xff0c;餐饮业也在寻求各种创新以满足顾客日益增长的需求。VR全景餐厅应运而生&#xff0c;它结合了虚拟现实技术与美食&#xff0c;为顾客提供了一种前所未有的沉浸式就餐体验。本文将深入探讨VR全景餐厅的核心技术、特色菜品和服务&#xff0c;以及它…

JavaScript之DOM操作

目录一、对元素进行操作1.动态生成元素2.在尾部插入一个元素3.在指定位置插入元素4.替换指定元素5.删除子级元素6.删除自身元素7.innerHTML二、对属性进行操作1.属性的设置&#xff08;setAttribute&#xff09;2.属性的获取&#xff08;getAttribute&#xff09;3.属性的删除&…

nginx--开源免费

nginx开源免费&#xff0c;支持高性能&#xff0c;高并发的web服务和代理服务软件。 apache,nodejs nginx可以提供的服务&#xff1a; 1、web服务 2、负载均衡&#xff08;反向代理&#xff09;&#xff08;动静分离&#xff09; 3、web cache(web缓存&#xff09; nginx…

android studio安装automotive模拟器

添加源 打开android studio的SDK Manager选择SDK Update Sites选项卡点击Add,弹出地址设置界面 添加polestar2-sys-img Name填写&#xff1a;Polestar 2 System Image (可自定义)URL填写&#xff1a;https://developer.polestar.com/sdk/polestar2-sys-img.xml其他保持默认 添…

算法---扫雷游戏

题目 让我们一起来玩扫雷游戏&#xff01; 给你一个大小为 m x n 二维字符矩阵 board &#xff0c;表示扫雷游戏的盘面&#xff0c;其中&#xff1a; ‘M’ 代表一个 未挖出的 地雷&#xff0c; ‘E’ 代表一个 未挖出的 空方块&#xff0c; ‘B’ 代表没有相邻&#xff08;…

Servlet基础

快速入门 创建maven web项目&#xff0c;导入Servlet依赖坐标&#xff1a; <dependencies><dependency><groupId>javax.servlet</groupId><artifactId>javax.servlet-api</artifactId><version>4.0.1</version><scope>…

企业申请的ISO认证证书,证书状态如何辨别?

企业申请的ISO认证证书&#xff0c;证书状态如何辨别&#xff1f; 关于ISO证书的有效期及ISO证书年度监督审核规定&#xff1a; ISO证书的有效期&#xff1a;ISO认证证书的有效期为三年&#xff0c;每年进行年度监督审核。每次的年度监督审核时间间隔不能超过12个月&#xff0…

C++ Primer第五版_第九章习题答案(11~20)

文章目录练习9.11练习9.12练习9.13练习9.14练习9.15练习9.16练习9.17练习9.18练习9.19练习9.20练习9.11 对6种创建和初始化 vector 对象的方法&#xff0c;每一种都给出一个实例。解释每个vector包含什么值。 vector<int> vec; // 0 vector<int> vec(10); //…

云原生Java架构实战 K8s+Docker+KubeSphere+DevOps(上)

简介&#xff1a;摘自 尚硅谷雷锋阳老师的语雀文档 学会使用按量付费的云服务器&#xff0c;开发测试性价比高 私有网络VPC 和网络有关的概念&#xff0c;如何在云服务器开通一个集群 一个云服务器有两个IP&#xff1a;公网IP和私网IP 公网IP&#xff1a;对外暴露资源的访…

SpringBoot源码 | refreshContext方法解析

SpringBoot源码 | refreshContext方法解析SpringBootrefreshContext源码refresh方法prepareRefreshobtainFreshBeanFactoryprepareBeanFactorypostProcessBeanFactoryinvokeBeanFactoryPostProcessorsregisterBeanPostProcessorsinitMessageSourceinitApplicationEventMulticas…

730. 机器人跳跃问题(基础二分)

机器人正在玩一个古老的基于 DOS 的游戏。 游戏中有 N1N1 座建筑——从 00 到 NN 编号&#xff0c;从左到右排列。 编号为 00 的建筑高度为 00 个单位&#xff0c;编号为 ii 的建筑高度为 H(i)H(i) 个单位。 起初&#xff0c;机器人在编号为 00 的建筑处。 每一步&#xff…

如何防止softmax函数overflow和underflow?

上溢出&#xff1a;c极其大的时候&#xff0c;计算ece^cec下溢出&#xff1a;当c趋于负无穷的时候&#xff0c;分母是一个极小的数&#xff0c;导致下溢出 解决方法 令Mmax⁡xi,i1,2,⋯,nM\max{x_i}, i1,2,\cdots,nMmaxxi​,i1,2,⋯,n, 也就是所有xix_ixi​中的最大值&#xff…

android 应用性能监控软件,App性能监控工具,卡顿

(609条消息) android 应用性能监控软件,App性能监控工具_weixin_39940154的博客-CSDN博客 APP性能监测的各种工具 - ClareBaby01 - 博客园 (cnblogs.com) (609条消息) Android App性能监控工具_sdk 性能监测工具_一代小强的博客-CSDN博客 android studio自带Memory Monitor …

Java_Spring:10. 基于注解的 AOP 配置

目录 1 环境搭建 1.1 第一步&#xff1a;准备必要的代码和 jar 包 1.2 第二步&#xff1a;在配置文件中导入 context 的名称空间 1.3 第三步&#xff1a;把资源使用注解配置 1.4 第四步&#xff1a;在配置文件中指定 spring 要扫描的包 2 配置步骤 2.1 第一步&#xff1a…

iOS 文本二维码识别

在 WWDC 2022&#xff0c;苹果发布了VisionKit 中的 DataScannerViewController&#xff0c;这是一个可以在本地无网络状态下识别文本以及条形码的视图控制器&#xff0c;它的相应速度以及精度都是比较高的&#xff0c;他可以支持汉语&#xff08;简繁版均支持&#xff09;、英…

城市新型智慧能源体系建设的初步解决方案

为加快推进国家“双碳”战略和新型能源体系建设&#xff0c;努力实现负荷控制和用户精细化管理&#xff0c;按照“政府主导、电网组织、政企协同、用户实施”的指导原则&#xff0c;多地成立市/县级电力负荷管理中心&#xff0c;包括浙江宁波、慈溪、辽宁大连、湖南株洲、娄底、…
最新文章