找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法专题(2)-模拟

admin 2019-6-4 22:29 204人围观 C++相关

点击上面微信号关注我

关注我哟
定期推送帐号信息学新闻,竞赛自主招生,信息学专业知识,信息学疑难解答,信息学训练营信息等诸多优质内容的微信平台,欢迎分享文章给你的朋友或者朋友圈!有任何问题请联系小编!

NOI2019 夏令营课程报名中!<点击查看




摘要

    本次系列文章主要介绍信息学以下知识点:



今天我们主要学习 模拟 这部分内容:

二、 模拟

概述:


模拟题在NOIP中十分常见,一般属于简单题,需要拿满分。模拟题需要理解题意,按照题目要求的直接进行模拟过程,或者按照题目要求模拟一些数据结构。模拟题最关键的是理解题意与细心。

1.知识点梳理:


Ø 模型建立与算法设计

模拟题题目可能会很繁琐,需抽取关键词,建立模型,再设计算法。算法设计过程中,需要考虑其完整性,即包含题目中所给的全部条件。

Ø 代码编写与调试

代码编写时,在题目条件相关的部分应写注释。调试时,需要根据题目中的条件构造数据测试。

2.重难点分析:


u 题意理解非常重要,必须考虑题目中的所有条件。

u 做题时要细心,并构造数据仔细测试,简单题必须拿满分。

3. 例题解析:

例题2-1:铺地毯(NOIP2011)


【问题描述】为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有n (n≤10000) 张地毯,编号从 1 到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后,组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意:在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

下图显示了一个三张地毯的铺地毯方式,其中实线为1号地毯,虚线为2号地毯,双实线为3号地毯,红点为所求点。

【分析】本题为简单模拟题,只要从前往后扫描所有地毯,模拟盖地毯的过程。如果当前地毯覆盖了所求点,则更新地毯编号。最后输出地毯编号即可。算法复杂度为O(n)。

例题2-2:机器翻译(NOIP2010)


【问题描述】小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。

假设内存中有M (M≤100) 个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过M-1,软件会将新单词存入一个未使用的内存单元;若内存中已存入M个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。

假设一篇英语文章的长度为N (N≤1000) 个单词(实际上是一个长度为N的数列)。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。

【分析】本题为模拟题,模拟队列形式。维护一个长度为M的队列,每次查找时,先查找队列内的数字是否包含,若不是,则将该数字插入队列,读取次数加一。算法复杂度为O(NM)。

例题2-3:字符串展开(NOIP2007)


【问题描述】在初赛普及组的“阅读程序写结果”的问题中,我们曾给出一个字符串展开的例子:如果在输入的字符串中,含有类似于“d-h”或者“4-8”的字串,我们就把它当作一种简写,输出时,用连续递增的字母获数字串替代其中的减号,即,将上面两个子串分别输出为“defgh”和“45678”。在本题中,我们通过增加一些参数的设置,使字符串的展开更为灵活。具体约定如下:

(1) 遇到下面的情况需要做字符串的展开:在输入的字符串中,出现了减号“-”,减号两侧同为小写字母或同为数字,且按照ASCII码的顺序,减号右边的字符严格大于左边的字符。

(2) 参数p1:展开方式。p1=1时,对于字母子串,填充小写字母;p1=2时,对于字母子串,填充大写字母。这两种情况下数字子串的填充方式相同。p1=3时,不论是字母子串还是数字字串,都用与要填充的字母个数相同的星号“*”来填充。

(3) 参数p2:填充字符的重复个数。p2=k表示同一个字符要连续填充k个。例如,当p2=3时,子串“d-h”应扩展为“deeefffgggh”。减号两边的字符不变。

(4) 参数p3:是否改为逆序:p3=1表示维持原来顺序,p3=2表示采用逆序输出,注意这时候仍然不包括减号两端的字符。例如当p1=1、p2=2、p3=2时,子串“d-h”应扩展为“dggffeeh”。

(5) 如果减号右边的字符恰好是左边字符的后继,只删除中间的减号,例如:“d-e”应输出为“de”,“3-4”应输出为“34”。如果减号右边的字符按照ASCII码的顺序小于或等于左边字符,输出时,要保留中间的减号,例如:“d-d”应输出为“d-d”,“3-1”应输出为“3-1”。

【输入】

输入包括两行:

第1行为用空格隔开的3个正整数,一次表示参数p1,p2,p3。

第2行为一行字符串,仅由数字、小写字母和减号“-”组成。行首和行末均无空格。

【输出】

输出只有一行,为展开后的字符串。

【样例输入】

1 2 1

abcs-w1234-9s-4zz

【样例输出】

abcsttuuvvw1234556677889s-4zz

【分析】本题为模拟题,应全面分析题目中的五个条件。条件(1)说明了展开序列特点,条件(2)(3)(4)说明了三个参数的用途,条件(5)说明了另一种展开情况。题意理解后,本题就分类讨论即可。

需要注意的是,由于本题中条件较多,需要对于每个条件构造相应的样例(或构造一个样例拥有所有的条件),并构造不同的参数样例来测试程序。





往期精选内容

(点击标题即可查看)

NOI2019 夏令营课程报名中!

2019年NOI省队选拔规定及NOI2019名额分配方案发布!

信息学竞赛入选!2019年度面向中小学生全国性竞赛活动名单公示

关于举办第34届全国青少年科技创新大赛的通知

最详细解析低分进名校三大途径:自主招生、综合评价、高校专项计划!

2018年自主招生高校对信息学奖项报考要求及优惠政策参考!报考时要注意哪些问题?


2019年保送生资格名单公示

NOIP2018复赛提高组各省中学 获一等奖人数排行榜及分析!

NOIP2018复赛提高组各省各中学获奖总数排行榜

NOIP2018各省各中学复赛普及组获奖总数分析!

CCF NOI2019冬令营报到通知及冬令营名额分配方案!

再见,OI-大牛HZW亲笔,分享OI生涯记录,不变的是坚持和热爱!

NOIP复赛知识点简述及复赛算法总结!

重磅!NOIP2018初赛普及组提高组真题及答案发布

NOIP2018提高组试题解析


根据信息学竞赛之路带你了解信息学竞赛流程

清华“姚班”2018级名单-看50名学霸到底多牛,同学们又如何能进姚班?

全国自主招生高校对各项学科竞赛奖项要求大汇总!签约路径

教育部出台高中新课标,信息学竞赛相关内容被编入必修课程!


北京大学自主招生初审通过1719人名单公布,看清华北大更青睐哪些省市中学?

IOI 2018国际信息学奥林匹克竞赛中国代表队选拔结果揭晓,看大牛们的竞赛之路!
2018年五大学科竞赛国家队名单全部出炉,各省中学大比拼!

从搜狗CEO王小川(信息学金牌),看这二十几年中国奥赛金牌的去向

揭晓高薪专业排行榜,计算机专业薪资最高!哪些专业最具潜力?

2018中国大学排行榜出炉,北大清华连续11年蝉联冠亚军


一个清华保送生妈妈对竞赛的感受,自主招生家长都要看看!

计算机科学与技术专业全国大学排行榜!


为什么这些孩子初中就能被清华北大签约

2018五大学科竞赛国家集训队成员及所在学校名单


(1)为什么有“编程思维”和数学能力强的人更优秀?
(2)清北独家录制NOIP成功者说学习视频!!!

(3)我们为什么要对孩子进行编程教育?

(4)信息学竞赛答家长问题

1.信息学竞赛,你想了解的知识都在这里

2.信息学奥赛(NOIP)初赛学习方法推荐

3.信息学奥赛(NOIP)复赛学习方法推荐

4.大牛为你推荐十本最适合信息学竞赛的书籍

5.信息学奥赛有那么重要吗?

6.参加编程竞赛对实际工作的用处

7.清北学堂独家录制NOIP考试技巧讲座

8.在线编程挑战赛第一名:我是这么学算法的

9.信息学竞赛如何学习及准备攻略!

10.凭什么我得了信息学奥赛国家一等奖

11.榜样 | 北大降200分要这个诸暨天才少年

12.OI金牌教练胡芳:爱和成长的故事

13.信息学竞赛,一个让孩子不需要再去挤独木桥的方向

14.新学期必须了解的学科竞赛与自主招生时间!

15.北大录取生陈代超:在信息学中找到“思维图谱”

16.国务院发文支持编程教育进入中小学,中国人工智能厚积薄发

(1)NOIP报名,申诉,查成绩方式介绍

(2)NOIP复赛考前需要注意的那些事儿!!!

(3)NOIP测评环境,数据提交你都了解吗?请注意这些问题!

(4)关于NOI系列赛编程语言使用限制的规定



关注「信息学竞赛」

看更多信息学趣闻与知识

↓↓↓




----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:信息学竞赛,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......