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，我很乐意为您解答！