算法专题（2）-模拟

摘要

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

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

二、 模拟

概述：

模拟题在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)说明了另一种展开情况。题意理解后，本题就分类讨论即可。

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