NOIP-C++大神培养计划Step1.1.1基础算法——模拟算法1

  1. 云栖社区>
  2. 博客>
  3. 正文

NOIP-C++大神培养计划Step1.1.1基础算法——模拟算法1

小笨笨qaq 2018-11-23 21:28:35 浏览574
展开阅读全文

模拟算法,可以说是最基础的算法了。
它的基本定义没太多意思:就是去模拟题目的要求。题意要你怎么做,你就怎么做,看懂了题目,基本上就会做了。

举一个大家耳熟能详的栗子。

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

网友评论

登录后评论
0/500
评论
小笨笨qaq
+ 关注