NOIP-C++大神培养计划Step1.1.1基础算法——模拟算法1
模拟算法，可以说是最基础的算法了。
它的基本定义没太多意思：就是去模拟题目的要求。题意要你怎么做，你就怎么做，看懂了题目，基本上就会做了。
举一个大家耳熟能详的栗子。
A+B Problem
给定两个整数A和B，输出他们的和。
这是学习C++的最简单的例题之一。
代码如下：
#include<iostream>
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
cout<<a+b<<endl;
return 0;
}那为什么要举这么简单的栗子呢？
不知你有没有注意，其实这就是一个模拟。
题目要你算A+B，你就算，这就是模拟。
我们在学习C++语言时做的题很多都有模拟的气息，所以，这一个算法大家应该会比较熟悉了。
有些简单的模拟题呢，很快就能做出来，当然个别难题还是要绞尽脑汁来想了。
下面，我们就来讲解一下往年NOIP中，考到的一些模拟。
栗1.1.1-1 洛谷1003 铺地毯
https://www.luogu.org/problemnew/show/P1003
题目描述
为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 n 张地毯，编号从 1。到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
输入输出格式
输入格式：
输入共n+2行
第一行，一个整数n，表示总共有n张地毯
接下来的n行中，第 i+1行表示编号i的地毯的信息，包含四个正整数
a,b,g,k ，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标(a,b)以及地毯在x轴和y轴方向的长度第n+2行包含两个正整数x和y，表示所求的地面的点的坐标(x,y)
输出格式：
输出共1行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出−1
输入输出样例
输入样例#1：
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2
输出样例#1：
3
输入样例#2：
3
1 0 2 3
0 2 3 3
2 1 3 3
4 5
输出样例#2：
-1
说明
【样例解释1】
如下图，
1 号地毯用实线表示，
2 号地毯用虚线表示，
3 号用双实线表示，覆盖点(2,2)的最上面一张地毯是 3 号地毯。
【数据范围】
对于30% 的数据，有
n≤2 ；
对于50% 的数据，
0≤a,b,g,k≤100；
对于100%的数据，有
0≤n≤10,000 ，
0≤a,b,g,k≤100,000。
noip2011提高组day1第1题
一般来说，Day1T1总是最简单的。那么，我们就来分析一下，这题该怎么去模拟。
解题思路：
首先，我们看到了题目，第一眼就想到了用二维数组，枚举每一个地毯，再给数组赋值便好！
来看一看代码：
#include<iostream>
using namespace std;
int s[10001][10001],n;//二维数组用于存每一点的覆盖情况
int x,y,a,b;//地毯的大小
int X,Y;//询问坐标
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x>>y>>a>>b;
for(int j=x;j<=x+a;j++)//枚举X轴
{
for(int t=y;t<=y+b;t++)//枚举Y轴
{
s[j][t]=i;//二维数组赋值
}
}
}
cin>>X>>Y;
if(s[X][Y])
cout<<s[X][Y]<<endl;
else
cout<<"-1"<<endl;
return 0;
}但是，注意：
0≤n≤10,000 ，
0≤a,b,g,k≤100,000。
数据范围是阻止我们AC的重要敌人，你要是开一个像
s 100001
的数组，空间会爆啊啊啊！
那怎么办呢？我们来想一想办法吧。
有一个真理：NOIP真题一定有标程，也就是答案，所以，我们珂以根据数据范围来选择算法或数据类型。
10^6啊，很大，100000*100000是绝对不可能的。
那我们想一想：
如果我们用数组来存x,y,a,b,在倒序枚举每一块地板，判断（X,Y）是否在地毯所覆盖的区间内。若没有，则输出-1
这个可以堪称完美算法了。我们只需要开100000*4的数组就可以了，复杂度是O(n)，完虐上一个算法QAQ
接下来我们来证明一下这个算法。
若一个点存在于一块地毯内（不是最上面的），那么他一定不存在与比它所在的地毯上层的地毯上，否则就跳出循环了。
这个算法证明很容易。记住，在考场上证明你的算法很重要。
那么，我们来看代码：
#include<iostream>
using namespace std;
int s[10001][5],n;//二维数组存x,y,a,b
int X,Y;//所求坐标
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s[i][1]>>s[i][2]>>s[i][3]>>s[i][4];
s[i][3]+=s[i][1];
s[i][4]+=s[i][2];
}
//s数组作用为：s[i][1]:第i张地毯起始点的x轴;s[i][2]：第i张地毯起始点的y轴;s[i][3]：第i张地毯终点的x轴;s[i][4]：第i张地毯终点的x轴
cin>>X>>Y;
for(int i=n;i>=1;i--)
{
if(s[i][1]<=X&&s[i][2]<=Y&&s[i][3]>=X&&s[i][4]>=Y)
{
cout<<i<<endl;
return 0;
}
}
cout<<-1<<endl;//没搜到输出-1.
return 0;
}这一题就算是完整地讲完了。
大家可以好好品味，去洛谷上AC这题吧！
栗1.1.1-2
洛谷P1008 三连击
https://www.luogu.org/problemnew/show/P1008
题目描述
将1,2,⋯,9共9个数分成3组，分别组成3个三位数，且使这3个三位数构成1:2:3的比例，试求出所有满足条件的3个三位数。
输入输出格式
输入格式：
木有输入
输出格式：
若干行，每行3个数字。按照每行第1个数字升序排列。
输入输出样例
输入样例#1：
无
输出样例#1：
192 384 576
...
（输出被和谐了）QAQ
这就是一道大模拟题，连输入都没有！
怪不得是普及组，来练练水
那么，这题怎么来做呢？
我们来思考一下：
让我们依次枚举三个三位数的个、十、百位，若遇见满足a:b:c=1:2:3时就输出，其实就行了。
我们来看看代码吧：
#include<cstdio>
#include<cstring>
int i,j,a;
bool v[10];//a[i]表示第i个数已经用过了
int main()
{
for(i=192;i<=327;i++)//第一个数最小192，最大327。用数学计算的，可以减小复杂度。
{
memset(a,0,sizeof(a));
a=0;
v[i%10]=v[i/10%10]=v[i/100]=v[i*2%10]=v[i*2/10%10]=v[i*2/100]=v[i*3%10]=v[i*3/10%10]=v[i*3/100]=1;//统计数字
for(j=1;j<=9;j++)
a+=v[j];//a表示1-9这些数字是否全部齐了
if(a==9)
printf("%d %d %d\n",i,i*2,i*3);//如果齐了就输出
/*
算法介绍：
这里的i表示第一个数，上面那个很长的语句就是将3个三位数的个、十、百位统计，a来计算用了几个数，若用了9个，输出。
*/
}
return 0;
}这就是这题的解法。题目本身没有太大的难度，只是要求一个思维的缜密，详解已经在代码中了，我想这题的理解应该没什么问题。
照常，去AC一下吧！
好了，今天的课程就到这里了，下一次我们将继续通过例题讲解熟悉模拟算法。我们下次见！
如果大家有问题或者想和我讨论，可以加我的QQ：907916611，我很乐意为您解答！
