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

简介: 模拟算法,可以说是最基础的算法了。它的基本定义没太多意思:就是去模拟题目的要求。题意要你怎么做,你就怎么做,看懂了题目,基本上就会做了。 举一个大家耳熟能详的栗子。 A+B Problem给定两个整数A和B,输出他们的和。

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

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

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

相关文章
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
360 2
|
存储 算法 C++
Windows共享文件:探秘C++实现的B树索引算法奇境
在数字化时代,Windows共享文件的高效管理至关重要。B树算法以其自平衡多路搜索特性,在文件索引与存储优化中表现出色。本文探讨B树在Windows共享文件中的应用,通过C++实现具体代码,展示其构建文件索引、优化数据存储的能力,提升文件检索效率。B树通过减少磁盘I/O操作,确保查询高效,为企业和个人提供流畅的文件共享体验。
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
410 17
|
存储 机器学习/深度学习 算法
基于 C++ 的局域网访问控制列表(ACL)实现及局域网限制上网软件算法研究
本文探讨局域网限制上网软件中访问控制列表(ACL)的应用,分析其通过规则匹配管理网络资源访问的核心机制。基于C++实现ACL算法原型,展示其灵活性与安全性。文中强调ACL在企业与教育场景下的重要作用,并提出性能优化及结合机器学习等未来研究方向。
430 4
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
388 0
|
存储 算法 安全
企业员工数据泄露防范策略:基于 C++ 语言的布隆过滤器算法剖析[如何防止员工泄密]
企业运营过程中,防范员工泄密是信息安全领域的核心议题。员工泄密可能致使企业核心数据、商业机密等关键资产的流失,进而给企业造成严重损失。为应对这一挑战,借助恰当的数据结构与算法成为强化信息防护的有效路径。本文专注于 C++ 语言中的布隆过滤器算法,深入探究其在防范员工泄密场景中的应用。
414 8
|
存储 监控 算法
基于 C++ 哈希表算法的局域网如何监控电脑技术解析
当代数字化办公与生活环境中,局域网的广泛应用极大地提升了信息交互的效率与便捷性。然而,出于网络安全管理、资源合理分配以及合规性要求等多方面的考量,对局域网内计算机进行有效监控成为一项至关重要的任务。实现局域网内计算机监控,涉及多种数据结构与算法的运用。本文聚焦于 C++ 编程语言中的哈希表算法,深入探讨其在局域网计算机监控场景中的应用,并通过详尽的代码示例进行阐释。
388 4
|
机器学习/深度学习 存储 算法
基于 C++ 布隆过滤器算法的局域网上网行为控制:URL 访问过滤的高效实现研究
本文探讨了一种基于布隆过滤器的局域网上网行为控制方法,旨在解决传统黑白名单机制在处理海量URL数据时存储与查询效率低的问题。通过C++实现URL访问过滤功能,实验表明该方法可将内存占用降至传统方案的八分之一,查询速度提升约40%,假阳性率可控。研究为优化企业网络管理提供了新思路,并提出结合机器学习、改进哈希函数及分布式协同等未来优化方向。
507 0
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
编译器 C++ 容器
【c++11】c++11新特性(上)(列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式)
C++11为C++带来了革命性变化,引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式,initializer_list简化了容器多元素初始化;右值引用和移动语义优化了资源管理,减少拷贝开销;类新增移动构造和移动赋值函数提升性能;lambda表达式提供匿名函数对象,增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展,提升了开发效率与程序性能。
733 12