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

这篇具有很好参考价值的文章主要介绍了​ 【蓝桥杯】每日四道编程题(两道真题+两道模拟)​| 第6天。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

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

目录

第一道真题(日志统计)

输出描述

输入输出样例

第二道真题(合根植物)

输出描述

输入输出样例

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

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

题目描述


第一道真题(日志统计)

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

输出描述

按从小到大的顺序输出热帖 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;
}

总结:

双指针的三个关键点

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

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

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

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

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

​ 【蓝桥杯】每日四道编程题(两道真题+两道模拟)​| 第6天 滑动窗口:两个指针分别代表窗口的左边界和右边界,然后根据条件移动两个指针来维护这段区间,就比如上面那道例题。

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

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

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

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

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))
    ...................
}

第二道真题(合根植物)

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

 比如: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

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

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

 运行限制

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

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

#include <iostream>
using namespace std;
 
int n,m,k;
int p[1000010];//要1e6  1000*1000
 
int 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字符串统计

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

输入样例:

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例:

1
0
1

时/空限制:1s / 64MB

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

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

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

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

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

//开始先定义 : 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 个方格区域组成,如下图所示。

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

走廊内部署了 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。

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

 输入样例:

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;
}

 ​ 【蓝桥杯】每日四道编程题(两道真题+两道模拟)​| 第6天文章来源地址https://www.toymoban.com/news/detail-400163.html

到了这里,关于​ 【蓝桥杯】每日四道编程题(两道真题+两道模拟)​| 第6天的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【蓝桥杯选拔赛真题30】C++字母转换 第十三届蓝桥杯青少年创意编程大赛C++编程选拔赛真题解析

    目录 C/C++字母转换 一、题目要求 1、编程实现 2、输入输出

    2024年01月16日
    浏览(44)
  • 【蓝桥杯冲刺】蓝桥杯11届省赛C++b组真题-编程题

    目录 试题F:成绩统计 解题思路: 代码: 试题G:回文日期 解题思路: 代码: 试题H:字串分值 解题思路: 代码:  试题I:平面切分 解题思路: 代码: 试题J:字串排序 解题思路: 写在最后: 【问题描述】 小蓝给学生们组织了一场考试,卷面总分为 100 分, 每个学生的

    2024年02月02日
    浏览(45)
  • 【蓝桥杯冲刺】蓝桥杯12届省赛C++b组真题-编程题

    目录 试题F:时间显示 解题思路 代码 试题G:砝码称重 解题思路 代码 试题H:杨辉三角 解题思路 代码 试题I:双向排序 解题思路 试题J:括号序列 解题思路 【问题描述】 小蓝要和朋友合作开发一个时间显示的网站。 在服务器上,朋友已经获取了当前的时间,用一个整数表

    2023年04月16日
    浏览(41)
  • 【蓝桥杯省赛真题18】python阴影图形面积 青少年组蓝桥杯python编程省赛真题解析

    目录 python阴影图形面积 一、题目要求 1、编程实现 2、输入输出

    2023年04月23日
    浏览(44)
  • 字符串的特殊读取——基于蓝桥杯两道题目(C/C++)

    目录 1  例题 1.1  卡片换位 1.2  人物相关性分析 2  字符串的读取 2.1  综述 2.2  scanf 2.3  getline/getchar/get 2.4  注意 2.5  说明 3  C语言中字符串有关问题 3.1  常用函数 3.2  使用实例 3.3  附一些函数 先看例题 问题描述 你玩过华容道的游戏吗? 这是个类似的,但更简单的游戏

    2023年04月20日
    浏览(36)
  • 第14届蓝桥杯国赛真题剖析-2023年5月28日Scratch编程初中级组

     [导读]:超平老师的《 Scratch蓝桥杯真题解析100讲》 已经全部完成,后续会不定期解读蓝桥杯真题,这是Scratch蓝桥杯真题解析第149讲。 第14届蓝桥杯Scratch国赛真题,这是2023年5月28日上午举办的全国总决赛,比赛仍然采取线上形式。初中级组共用一套试题,试题包括两种题型

    2024年02月10日
    浏览(44)
  • 第十四届蓝桥杯校模拟赛-编程大题详解+代码(二)

    前言: 这几天有不少小伙伴催促我尽快更新后五道编程题题解,然鄙人实在水平有限,实事求是,能力不足,不堪众望。思索良久,第九题有解题思路且已完成部分解题,但未完全完成,第十题尚未有思路。在此愿有大佬指点一二! 目录 一、做不完的核酸 问题描述 1.1 代码

    2024年02月02日
    浏览(53)
  • 石头剪刀布--蓝桥杯大赛青少年创意编程C++高级组模拟题

    石头剪刀布 Description 放假期间,小蓝与电脑对垒,玩起了一款经典的游戏: “石头剪刀布” 。游戏规则想必大家已经非常熟悉了:两边一样则为平局,否则石头胜于剪刀;剪刀胜于布;布胜于石头。小蓝与电脑的对垒一共有 n 个回合,平局或败局得分为 0;胜局得分取决于

    2023年04月12日
    浏览(68)
  • 《Python等级考试(1~6级)历届真题解析》专栏总目录

    ❤️ 专栏名称:《Python等级考试(1~6级)历届真题解析》 🌸 专栏介绍:中国电子学会《全国青少年软件编程等级考试》Python编程(1~6级)历届真题解析。 🚀 订阅专栏:原价 99.9,🔥 火爆订阅中 🔥,前 100 订阅 9.9。订阅后可阅读专栏内所有文章,本专栏持续更新中,欢迎

    2024年02月05日
    浏览(45)
  • 《C/C++等级考试(1~8级)历届真题解析》专栏总目录

    ❤️ 专栏名称:《C/C++等级考试(1~8级)历届真题解析》 🌸 专栏介绍:中国电子学会《全国青少年软件编程等级考试》C/C++编程(1~8级)历届真题解析。 🚀 订阅专栏:订阅后可阅读专栏内所有真题解析,真题持续更新中,限时19.9元,欢迎订阅! C语言解析: 序号 日期 考

    2024年02月11日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包