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： 31 0 2 30 2 3 32 1 3 32 2输出样例#1： 3 输入样例#2：31 0 2 30 2 3 32 1 3 34 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，我很乐意为您解答！
