模拟，简单的说，就是题目让你干什么，你就按照它的要求一步一步的做，没有固定的套路，每一个题都可以说是模拟，但是有的题会因为它的时间和空间的限制，从而选择不同的算法。原则上，在蓝桥杯中，能够按照模拟的过程写出代码的题，都能得到一定的分数。

下面，我们简答的来做几道典型的模拟的题。

洛谷P1003 [NOIP2011 提高组] 铺地毯

我就不写题干了，自己点进去看，我们直接开始解析这道题。

首先，要抓住题干里的关键点，在矩形地毯边界和四个顶点上的点也算被地毯覆盖，这里明确的给出了边界条件，不能够忽视。

接下来，就开始按照题目的意思开始写代码，看它给的输入格式

第一行，一个整数$n$，表示总共有$n$张地毯。

#include <iostream>
using namespace std;
int main(){
    int n=0;//根据题意，定义一个n，不要忘记初始化。
    cin>>n;
    return 0;
}

接下来的 n行中，第$ i+1$行表示编号$i$的地毯的信息，包含四个整数 $a ,b ,g ,k$每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标$ (a,b) $以及地毯在$x$轴和$y$轴方向的长度。

#include <iostream>
using namespace std;
struct ditan{
    //定义地毯的结构体，具体原因看下面
	int a;
	int b;
    //a,b表示地毯左下角的坐标
	int g;
	int k;
    //g,k含义和题里相同
}A[10005];//根据题目最后给的范围，我们知道，地毯最多有10^4个，这里定义的数组大小稍微大于这个数即可
int main(){
    int n=0;
    cin>>n;
    for(int i=1;i<=n;++i){
        //按照题意，此时循环输入n组地毯的信息，因为地毯从一开始标号，所以循环也从1开始，又最后才给出要求的坐标，所以我们需要将每一组地毯的坐标存储起来，因为地毯有四个属性，所以我们可以定义一个结构体来进行存储
        cin>>A[i].a>>A[i].b>>A[i].g>>A[i].k;//按照题目要求，输入每组地毯的信息
    }
    return 0;
}

下面，第$n+2$行包含两个整数$x$和$y$，表示所求的地面的点的坐标$(x,y)$。

#include <iostream>
using namespace std;
struct ditan{
	int a;
	int b;
	int g;
	int k;
}A[10005];
int main(){
    int n=0;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>A[i].a>>A[i].b>>A[i].g>>A[i].k;
    }
    int x=0,y=0;//根据题意，定义要求的坐标x,y
    cin>>x>>y;
    return 0;
}

接下来，就是如何解题了，相信大家都很容易想到，当前的坐标被地毯覆盖，就说明这个坐标在地毯的范围内，通过中学的数学，我们知道，$x>=a,y>=b,x<=a+g,y<=b+k$这四个条件同时满足的时候，这个点就在地毯的范围内，所以，我们直接这样写就行

#include <iostream>
using namespace std;
struct ditan{
	int a;
	int b;
	int g;
	int k;
}A[10005];
int main(){
    int n=0;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>A[i].a>>A[i].b>>A[i].g>>A[i].k;
    }
    int x=0,y=0;
    cin>>x>>y;
    int ans=0;//定义一个变量，用来存储最后的答案
    for(int i=1;i<=n;i++){
        //循环前面的存储的每一个地毯，判断坐标是否在当前地毯的覆盖之下
		if(x>=A[i].a&&x<=A[i].a+A[i].g&&y>=A[i].b&&y<=A[i].b+A[i].k){
            //根据分析出来的判断条件，满足条件的，就将当前的答案更新为目前的地毯编号
			ans=i;
		}
	}
    //这里，根据题目最后给出的输出要求，如果有地毯覆盖，输出地毯编号，没有就输出-1
	if(ans==0){
        //如果没有地毯覆盖，ans的值就不会变化，那么它就应该等于0
		cout<<"-1";
	}else{
		cout<<ans;
	}
    return 0;
}

至此，这题结束，一个完整模拟的过程差不多就是这样了。

下面，我们看第二题

洛谷P1540 [NOIP2010 提高组] 机器翻译

首先，还是提炼题目中的重点信息

先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

若内存中已存入$M$个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。

给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

通过题目的描述，我们很容易想到队列这个数据结构，而且，一定要注意，最后求的是需要去多少次外存进行查找。

接下来，就开始按照题目的意思开始写代码

#include <iostream>
using namespace std;
int main(){
    int m,n;//定义题中要求的m和n两个变量
    cin>>m>>n;
    return 0;
}

第二行为$N$个非负整数，按照文章的顺序，每个数（大小不超过$1000$)代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

因为每次输入的一个数，其实是在和队列$m$里的元素进行比较，所以，我们不必将每个输入的数都存起来，只需要构建一个“队列”来模拟题目中所谓的“内存”，这时，我们就可以想到STL里的queue这个模板。同时，再思考，如果每次输入的数，我们都去队列里进行遍历查找的话，在队列很长的情况下，时间复杂度会非常的大，所以，我们可以想到用STL里的map来进行快速的查找。下面，开始完善我们的程序。

#include <iostream>
#include <queue>//引入queue
#include <map>//引入map
using namespace std;
queue<int>Q;//定义一个队列Q
map<int,int>M;//定义M
int main(){
    int m=0,n=0;
    cin>>m>>n;
    int ans=0;//定义最终答案的变量。
    while(n--){
        int t=0;//定义一个临时变量，用来存储每次输入的数
        cin>>t;
        //思考我们每次输出变量后需要进行什么步骤，按照题目的要求一步一步的来
        if(M[t]==1){
            //首先，我们肯定要判断这个数在不在内存里面，如果在,什么都不用管，当做无事发生
        }else{
            //如果不在，我们首先需要判断，当前内存的长度是否达到了上限
            if(Q.size()==m){
                //如果达到了上限，就将队首的元素出队
                M[Q.front()]=0;//在出队前，标记当前元素已经不在队列中了
                Q.pop();//将队首元素出队
                M[t]=1;//将新添加的元素标记存入了内存队列
                Q.push(t);//将其添加到队列末尾
                ans++;//查找次数+1
            }else{
                //如果没有满，就直接将当前元素添加到队尾
                M[t]=1;//将新添加的元素标记存入了内存队列
                Q.push(t);//将其添加到队列末尾
                ans++;//查找次数+1
            }            
        }
    }
    cout<<ans;//最后，输出要求的答案
    return 0;
}

至此，这题结束

最后，我们看这次讲解的最后一题

洛谷P1012 [NOIP1998 提高组] 拼数

这题十分的简单，但是一定要注意认真读题，将题目中的重点信息抓出来

这道题，我唯一想让你们了解的知识点是字典序这个概念，以及熟悉string这个类的使用和sort函数的使用，字典序十分简单，建议自行百度进行学习。

这题，要求组成的数字最大，而且它是将每一组数进行链接得到的，所以，只需要按照每组数据的第一位数从大到小将他们链接起来就行了，而对所有的数据进行字典序排序后，恰巧满足这个条件。

#include <iostream>
#include <cstring>//引入string
#include <algorithm>//引入algorithm以便使用sort
using namespace std;
bool cmp(string a,string b){
    //sort使用的cmp函数，相信通过sort的学习，同学们都应该理解
	return a>b;
}
int main(){
    int n=0;
	cin>>n;
	string A[n];
	for(int i=0;i<n;i++){
		cin>>A[i];
	}
	sort(A,A+n,cmp);//使用前面的规则，用sort进行排序
	for(i=0;i<n;i++){
		cout<<A[i];//按题目要求进行输出
	}
    return 0;
}

我想讲的就这么多了，谢谢大家！

2021-LQC-Trainning

Southwest University Lanqiao Cup Training Repository, April 2021

洛谷P1003 [NOIP2011 提高组] 铺地毯

洛谷P1540 [NOIP2010 提高组] 机器翻译

洛谷P1012 [NOIP1998 提高组] 拼数