模拟算法 蓝桥杯备赛系列 acwing

文章目录:

基础知识


什么是模拟?


例题



一、错误票据

1.解题思路

2.代码


二、移动距离


1.解题思路

2.代码


三、航班时间


1.解题思路

2.代码

四、外卖优先级

1.解题思路

2.代码

前面为了目录好看大家就当个玩笑看吧哈哈哈。下面上正文。

                                              正文

基础知识
什么是模拟?
模拟一个很宽泛的内容,比如字符串处理,日期处理。凡是不是很复杂但是没有标准归类的题目都可以称为模拟。

枚举和模拟是没有什么算法可言的,按照题目说的意思去模拟一下即可,要求对语法代码的熟练度比较高。

模拟题是有唯一解的,而不是求最优解的问题,只不过模拟题实现起来比较麻烦。

      这个是引用某个大佬的内容: 模拟算法是一种最基本的算法思想,是对程序员基本编程能力的一种考查,其解决方法就是根据题目给出的规则对题目要求的相关过程进行编程模拟。在解决模拟类问题时,需要注意字符串处理、特殊情况处理和对题目意思的理解。我们知道在C语言中,通常使用函数srand()和rand()来生成随机数。其中函数srand()用于初始化随机数发生器,然后使用函数rand()来生成随机数。如果要使用上述两个函数,则需要在源程序头部包含time.h文件。在程序设计过程中,可使用随机函数来模拟自然界中发生的不可预测情况。在解题时,需要仔细分析题目给出的规则,要尽可能地做到全面地考虑所有可能出现的情况,这是解模拟类问题的关键点。

二、错误票据
1.解题思路

步骤:
①输入:都输入到一个数组中

本题比较坑的是注意输入,只告诉了有多少行,没告诉每行有多少个数。每行有多少个数需要自己处理 。

int a[100010];    
int k=0;
int x;
while(cin>>x)  //这行会把每个出现的数都存到a[]数组中
{
    a[k++]=x;
}

②从小到大排序

③循环遍历数组

找重号:如果相邻两个数相等,那么这个就是重号

找断号 :如果相邻的两个数相差2,那么两数中间的就是断号

2.代码

做题先暴力,下面是暴力代码

//另一种方法:暴力模拟法

#include <iostream>
#include <algorithm>
using namespace std;
int a[100010];
int main()
{
    int n;
    cin>>n;
    
    int k=0;
    
    //第一步:输入数据,合并到一个数组中
    int x;
    while(cin>>x)
    {
        a[k++]=x;
    }
   // for(int i=0;i<k;i++) cout<<a[i]<<" ";
   
   //第二步:排序
   sort(a,a+k);
   
   //第三步:求重号:利用桶的思想,找到第一个重复的数据,记录
   int t[100010],ans2=0;
   for(int i=0;i<k;i++)
   {
       t[a[i]]++;
   }
   for(int i=0;i<=100000;i++)
   {
       if(t[i]>=2)
       {
           ans2=i;
           break;
       }
   }
    
    //第四步:求断号:先给序列去重,再利用下标和排好序的序列,找断号,注意边界
    int z[100010],j=0;
    for(int i=0;i<k;i++)
    {
        if(a[i]==a[i-1]) continue;
        else z[j++]=a[i];
    }
    //for(int i=0;i<j;i++) cout<<z[i]<<" ";
    int q=z[0],ans1=0;
    for(int i=0;i<j;i++)
    {
        if(z[i]==q) 
        {
            q++;
            continue;   
        }
        else 
        {
            ans1=q;
            break;
        }
        
    }
    
    cout<<ans1<<" "<<ans2;
    
    return 0;
    
}


下面这是正常做法 

#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
int a[N];

int main()
{
    int cnt;
    cin >> cnt;
    string line;

    getline(cin, line); // 忽略掉第一行的回车
    while (cnt -- )
    {
        getline(cin, line);
        stringstream ssin(line);

        while (ssin >> a[n]) n ++ ;
    }

    sort(a, a + n);

    int res1, res2;
    for (int i = 1; i < n; i ++ )
        if (a[i] == a[i - 1]) res2 = a[i];  // 重号
        else if (a[i] >= a[i - 1] + 2) res1 = a[i] - 1; // 断号

    cout << res1 << ' ' << res2 << endl;

    return 0;
}

二、移动距离
1.解题思路

题目中遇到距离一般有两种:曼哈顿距离 和 欧几里得距离

曼哈顿距离:|x1-x2|+|y1-y2| 两点之间走过的折线距离
欧几里得距离:sqrt((x1-x2) * (x1-x2)+(y1-y2) * (y1-y2)) 两点间的直线距离

本题所有点的坐标其实就是行号和列号

可以借鉴c++中二维数组的行号和列号下标表示:让编号从0开始标号,所以让m,n一开始都-1,不需要特判边界了。所以 行号:n/w m/w ,列号:n%w m%w

又因为本题编号是蛇形递增+1的,所以只需要判断是奇数行还是偶数行

偶数行不用变,奇数行逆序:if n/w 是奇数 ,w-1-n%w
2.代码

//时间复杂度O(1)
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int w, m, n;
    cin >> w >> m >> n;
    m --, n -- ; //让编号从0开始

    int x1 = m / w, x2 = n / w;  //两个点的行号
    int y1 = m % w, y2 = n % w;  //两个点的列号
    if (x1 % 2) y1 = w - 1 - y1; //第一个点行号如果是奇数行,列号就反转一下
    if (x2 % 2) y2 = w - 1 - y2; //第二个点行号如果是奇数行,列号就反转一下

    cout << abs(x1 - x2) + abs(y1 - y2) << endl;  //求出两点之间的曼哈顿距离

    return 0;
}
三、航班时间
1.解题思路

通过分析,可以得到:

飞行时间=[(去的结束时间-去的起始时间)+(回的结束时间-回的起始时间)]/2

步骤:

①字符串格式化输入:这道题目麻烦就是麻烦在字符串的格式处理上

getline(cin,line);//忽略第一行的回车
int fh1,fm1,fs1,fh2,fm2,fs2,fd=0;
scanf("%d:%d:%d %d:%d:%d (+%d)",&fh1,&fm1,&fs1,&fh2,&fm2,&fs2,&fd);//注意输入时(+%d),不匹配后就会跳过了

②将所有时间转化为距离当天00:00:00的秒数,得到飞行时间秒数time

int time1,time2,t;
time1=fd*24*3600+fh2*3600+fm2*60+fs2-(fh1*3600+fm1*60+fs1);
time2=ed*24*3600+eh2*3600+em2*60+es2-(eh1*3600+em1*60+es1);
t=(time1+time2)/2;

③再将飞行时间time转化为00:00:00这一规定时间格式:

hour=time/3600;
minute=time%3600/60
second=time%3600%60

④格式化输出:

printf("%02d:%02d:%02d\n", t/3600, t%3600/60, t%3600%60);

2.代码

#include<iostream>
#include <cstdio>
using namespace std;

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        //输入去的时候起始时间和结束时间
        int fh1,fm1,fs1,fh2,fm2,fs2,fd=0;
        scanf("%d:%d:%d %d:%d:%d (+%d)",&fh1,&fm1,&fs1,&fh2,&fm2,&fs2,&fd);
        
        //输入回的时候起始时间和结束时间
        int eh1,em1,es1,eh2,em2,es2,ed=0;
        scanf("%d:%d:%d %d:%d:%d (+%d)",&eh1,&em1,&es1,&eh2,&em2,&es2,&ed);
        
        //计算两次分别的飞行时间,和除以2为最终的飞行时间
        int time1,time2,t;
        time1=fd*24*3600+fh2*3600+fm2*60+fs2-(fh1*3600+fm1*60+fs1);
        time2=ed*24*3600+eh2*3600+em2*60+es2-(eh1*3600+em1*60+es1);
        t=(time1+time2)/2;
        
        //将秒数转化为规定格式输出
        printf("%02d:%02d:%02d\n", t/3600, t%3600/60, t%3600%60);
    }
    return 0;
}
//封装为函数

#include<iostream>
#include<cstdio>
using namespace std;
int getTime()
{
    int h1,m1,s1,h2,m2,s2,d=0;
    scanf("%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);
    int time=d*24*3600+h2*3600+m2*60+s2-(h1*3600+m1*60+s1);
    return time;
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int i = 0; i < t; i++)
    {
        int time1=getTime();
        int time2=getTime();
        int t=(time1+time2)/2;
        printf("%02d:%02d:%02d\n", t/3600, t/60%60, t%60);
    }
    return 0;
}
四、外卖优先级
1.解题思路

在这里插入图片描述

伪代码如下:

score[i]:表示第i个店铺当前的优先级 
last[i]: 表示第i个店铺上一次有订单的时刻
st[i]:表示第i个店铺当前是否处于优先缓存中

将所有订单按时间顺序排序;
for 每个订单
{
    每次处理一批相同的订单;
    id,t,cnt;
    //第一部分,是上一个拿到订单的时间last[id]和t之间,中间没订单所以要−1,没订单的数量是t−last[i]−1 (比如第3和第6时刻都有订单,没有订单的时候就是4,5)
    score[id]=t-last[id]-1;
    if(score[id]<0) score[id]=0;//计算优先权,如果为负值更新为0。如果小于等于3,更新优先缓存 st[id]=false
    if(score[id]<=3) st[id]=false;
    
    //第二部分,是此时,tt时刻拿到订单,并且拿到的数量为cntcnt,要加上2∗cnt
    score[id]+=cnt*2;
    if(score[id]>5) st[id]=true;//计算优先权,如果大于5,更新优先缓存 st[id]=true
}
for(int i=1;i<=n;i++)
{
    if(last[i]<T) 
    {
        score[i]-=T-last[i];
        if (score[i] <= 3) st[i] = false;
    }
}

res = 0;
for(int i=1;i<=n;i++)
{
    res+=st[i];
}

2.代码 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, m, T;
int score[N], last[N];
bool st[N];

PII order[N];

int main()
{
    scanf("%d%d%d", &n, &m, &T);
    for (int i = 0; i < m; i ++ ) scanf("%d%d", &order[i].x, &order[i].y);
    sort(order, order + m);

    for (int i = 0; i < m;)
    {
        int j = i;
        while (j < m && order[j] == order[i]) j ++ ;
        int t = order[i].x, id = order[i].y, cnt = j - i;
        i = j;
/*
while (j < m && order[j] == order[i]) j ++ ;和cnt = j - i;是为了算出来同一时刻同一家店的订单数量,数量就是cnt的值,这个数量可能不唯一。
第一次while()循环中的order[j] == order[i]是一定成立的,然后j ++,j 就变成 i + 1,再比较order[i]和order[i + 1]是否相等,含义就是下一个订单与当前这个订单是不是同一时刻同一家店的,直到时刻或者 id 不同时,结束while循环,最后 j 就指向“不重复”的第一个订单,然后令 i = j,继续枚举所有订单
写成:int j = i + 1;,其它语句都不改动,也是对的,我感觉更好理解
*/
        
        score[id] -= t - last[id] - 1;
        if (score[id] < 0) score[id] = 0;
        if (score[id] <= 3) st[id] = false; 

        score[id] += cnt * 2;
        if (score[id] > 5) st[id] = true;

        last[id] = t;
    }

    for (int i = 1; i <= n; i ++ )
        if (last[i] < T)
        {
            score[i] -= T - last[i];
            if (score[i] <= 3) st[i] = false;
        }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res += st[i];

    printf("%d\n", res);

    return 0;
}

最近博主有事,暂且停更,一天一篇博客确实很有压力的,所以说待博主沉淀亿下给大家更多优质内容哈哈哈!元旦过后见! 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/274337.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Amazon CodeWhisperer 免费 AI 代码生成助手体验分享

今年上半年&#xff0c;亚马逊云科技正式推出了实时AI编程助手 Amazon CodeWhisperer&#xff0c;还提供了供所有开发人员免费使用的个人版版本。经过一段时间的体验&#xff0c;我觉得 CodeWhisperer 可以处理编程工作中遇到的很多问题&#xff0c;并且帮助开发人员提高编程效…

websocket 介绍

目录 1&#xff0c;前端如何实现即时通讯短轮询长轮询 2&#xff0c;websocket2.1&#xff0c;握手2.2&#xff0c;握手过程举例2.3&#xff0c;socket.io 3&#xff0c;websocket 对比 http 的优势 1&#xff0c;前端如何实现即时通讯 在 websocket 协议出现之前&#xff0c;…

Ubuntu20.04服务器使用教程(安装教程、常用命令、故障排查)持续更新中.....

安装教程&#xff08;系统、驱动、CUDA、CUDNN、Pytorch、Timeshift、ToDesk&#xff09; 制作U盘启动盘&#xff0c;并安装系统 在MSDN i tell you下载Ubuntu20.04 Desktop 版本&#xff0c;并使用Rufus制作UEFI启动盘&#xff0c;参考UEFI安装Ubuntu使用GPTUEFI模式安装&am…

hql、数据仓库、sql调优、hive sql、python

SQL/HQL HQL(Hibernate Query Language) 是面向对象的查询语言 SQL的操作对象是数据列、表等数据库数据 ; 而HQL操作的是类、实例、属性 #FROM String hql "from com.demo.bean.User" "select * from user" #WHERE "form User u where u.id 1…

Filter过滤器的使用!!!

什么是过滤器 当浏览器向服务器发送请求的时候&#xff0c;过滤器可以将请求拦截下来&#xff0c;完成一些特殊的功能&#xff0c;比如&#xff1a;编码设置、权限校验、日志记录等。 过滤器执行流程 过滤器的使用&#xff1a; /** Copyright (c) 2020, 2023, All rights …

【AIGC】AIGC——真正意义的智能,颠覆性的变革

AIGC——真正意义的智能&#xff0c;颠覆性的变革 AIGC&#xff08;AI Generated Content&#xff0c;即人工智能生成的内容&#xff09;可以通过以下几个方面来实现跨越&#xff1a; 技术跨越&#xff1a;AIGC可以通过不断的技术创新和进步&#xff0c;实现从简单的生成内容…

电脑键盘大小写切换按哪个键?正确操作分享!

“我在工作时&#xff0c;经常需要输入英文文档&#xff0c;但我不知道输入大小字母时应该按哪个键切换&#xff0c;有朋友可以教教我吗&#xff1f;” 在我们使用电脑时&#xff0c;输入英文文档是经常会遇到的事。当输入某些单词时&#xff0c;我们可能需要切换大小写。电脑键…

ASUS华硕ROG幻16 2023款GU603VU VV VI笔记本电脑原厂Win11.22H2系统

链接&#xff1a;https://pan.baidu.com/s/1AgevUZleCHBJgCBcIp5CFQ?pwdhjxy 提取码&#xff1a;hjxy 华硕笔记本2023款幻16原厂Windows11系统自带所有驱动、出厂主题壁纸、Office办公软件、MyASUS华硕电脑管家、Armoury Crate奥创控制中心等预装程序 文件格式&#xff1…

Centos开启防火墙和端口命令

Centos开启防火墙和端口命令 1 课堂小知识1.1 centos7简介1.2 iptables方式开启防火墙 2 操作步骤2.1 开启查看关闭firewalld服务状态2.2 查看端口是否开放2.3 新增开放端口2.4 查看开放的端口 3 防火墙的其他指令 1 课堂小知识 1.1 centos7简介 CentOS 7是CentOS项目发布的开…

.NET 使用Camunda快速入门

一.工作流介绍 1. 什么是工作流 工作流&#xff08;Workflow&#xff09;&#xff0c;是对工作流程及其各操作步骤之间业务规则的抽象、概括描述。 工作流将一套大的业务逻辑分解成业务逻辑段&#xff0c; 并统一控制这些业务逻辑段的执行条件&#xff0c;执行顺序以及相互通…

48道Linux面试题

本博客将汇总 Linux 面试中常见的题目&#xff0c;并提供详细的解答。 文章目录 1、绝对路径用什么[符号表](https://so.csdn.net/so/search?q符号表&spm1001.2101.3001.7020)示&#xff1f;当前目录、上层目录用什么表示&#xff1f;主目录用什么表示? 切换目录用什么命…

GBASE南大通用 GCDW阿里云计算巢:自动化部署云原生数据仓库

目前&#xff0c;GBASE南大通用已与阿里云计算巢合作&#xff0c;双方融合各自技术优势&#xff0c;助力企业用户实现云上数据仓库的自动化部署&#xff0c;让用户在云端获取数据仓库服务“更简单”&#xff0c;让用户在云端使用数据仓库服务“更便捷”&#xff0c;满足企业用户…

数据挖掘(作业3

任务一 对以下数据集使用K均值聚类算法&#xff1a; 1&#xff09;观察实验结果是否符合预期&#xff1b; 2&#xff09;利用SSE标准确定K值&#xff1b; 3&#xff09;自行调参并观察对聚类结果的影响。 注意&#xff1a;需要把类别信息去掉。 “tutorial3_Data Explorat…

Oracle 12c rac 搭建 dg

环境 rac 环境 &#xff08;主&#xff09;byoradbrac 系统版本&#xff1a;Red Hat Enterprise Linux Server release 6.5 软件版本&#xff1a;Oracle Database 12c Enterprise Edition Release 12.1.0.2.0 - 64bit byoradb1&#xff1a;172.17.38.44 byoradb2&#xff1a;…

车路协同中 CUDA 鱼眼相机矫正、检测、追踪

在车路协同中,鱼眼一般用来补充杆件下方的盲区,需要实现目标检测、追踪、定位。在目标追踪任务中,通常的球机或者枪机方案,无法避免人群遮挡的问题,从而导致较高的ID Swich,造成追踪不稳定。但是鱼眼相机的顶视角安装方式,天然缓解了遮挡的问题,从而实现杆件下方的盲区…

关于“Python”的核心知识点整理大全46

目录 16.1.3 提取并读取数据 highs_lows.py highs_lows.py 16.1.4 绘制气温图表 highs_lows.py 16.1.5 模块 datetime ​编辑 16.1.6 在图表中添加日期 highs_lows.py 16.1.7 涵盖更长的时间 highs_lows.py highs_lows.py 16.1.9 给图表区域着色 highs_lows.py …

Linux操作系统(Crontab计划任务+NTP时间同步服务器)

如何修改linux系统时间 与时间相关的命令&#xff0c;查看当前的时间 运行 date 即可 cal 查看当前月份的日历 运行 timedatectl 查看时间详细参数 &#xff08; NTP&#xff1a; network time protocol 网络时间协议 &#xff09; &#xff08; local time : 本地时间 &#x…

搭建APP应用程序如何选择服务器

我经常收到许多关于如何搭建 APP 的询问。其中&#xff0c;如何选择服务器是许多初创企业和开发者经常面临的问题。带着这些问题我也通过一些科技手段收集整理了些知识&#xff0c;今天我就和大家来来探讨如何选择服务器&#xff0c;帮助您搭建一个稳定、高效、安全的 APP。 Ap…

MariaDB单机多实例的配置方法

1、什么是数据库的单机多实例 数据库的单机多实例是指在一台物理服务器上运行多个数据库实例。这种部署方式允许多个数据库实例共享相同的物理资源&#xff0c;如CPU、内存和存储&#xff0c;从而提高硬件利用率并降低成本。每个数据库实例可以独立运行&#xff0c;处理不同的…

python如何通过日志分析加入黑名单

python通过日志分析加入黑名单 监控nginx日志&#xff0c;若有人攻击&#xff0c;则加入黑名单&#xff0c;操作步骤如下&#xff1a; 1.读取日志文件 2.分隔文件&#xff0c;取出ip 3.将取出的ip放入list&#xff0c;然后判读ip的次数 4.若超过设定的次数&#xff0c;则加…