当前位置: 首页 > news >正文

算法04 模拟算法之一维数组相关内容详解【C++实现】

大家好,我是bigbigli,模拟算法我们将分为几个章节来讲,今天我们只看一维数组相关的题目

目录

模拟的概念

训练:开关灯

解析

参考代码

训练:数组变化

解析

参考代码

训练:折叠游戏

解析

参考代码


模拟的概念

模拟算法就是模拟题目给的操作,用代码一步一步的描述出来即可。在过程中使用的都是我们已知的各种方法,如数组元素调用、排序、枚举等等,只是这些过程一般比较复杂。本次课程主要针对一维数组的模拟。

在各类算法竞赛中,包括CSP-J/S,NOIP等竞赛,经常会出现各类“模拟题目”,遇到这种题大家不需要害怕,甚至可以将其作为“送分题”,因为你只需要按照题目叙述的方式来写程序就能得到最终答案。模拟不是一种算法,而是一种技巧,要想掌握模拟题目,就需要多读题、多整理细节问题。

训练:开关灯

有n盏灯,从1到n按顺序依次编号,初始时所有灯都处于开启状态;有m个人,从1到m依次编号。

第一个人将灯全部关闭,第二个人将编号为2的倍数的灯打开,第三个人将编号为3的倍数的灯做相反处理(即将打开的灯关闭,将关闭的灯打开)。依照编号递增顺序,以后的人都一样,将凡是自己编号倍数的灯做相反处理。

请问:当第m个人操作之后,哪几盏灯是关闭的,按从小到大输出其编号,用逗号间隔。

【输入描述】一行,n和m,空格隔开

【输出描述】顺次输出关闭的灯的编号,用逗号隔开

【输入样例】10 1010

【输出样例】1,4,9

 

解析

因为灯只会出现0和1两种情况,我们可以使用数组元素来表示(类似桶),随后只需要重复m次,每次寻找当前序号的倍数为下标的元素进行更改,如果是1就变成0,是0就变成1。

最后对数组元素进行判断,找出是0的元素,就行数组元素下标的输出。

输出时要注意的问题是用逗号隔开不同于用空格隔开。

 

参考代码

#include<iostream>
using namespace std;
int a[1010];//全部是0,表示关闭
int main()
{int n,m;cin>>n>>m;for(int i=2;i<=m;i++)//从第二个人开始操作for(int j=i;j<=n;j+=i)//编号对应倍数下标if(a[j]==1)    a[j]=0;else a[j]=1;//更改状态cout<<1;//1号肯定关闭for(int i=2;i<=n;i++)if(a[i]==0)    cout<<","<<i;//间隔逗号输出return 0;
}

训练:数组变化

现有一个长度为n的数组,对这个数组进行m次操作,可以对数组进行的操作分为以下三类:

输入1 i:   表示输出数组中第i个元素的值;

输入2 i v: 表示在数组中第i个元素前加入新的元素v;

输入3 i:   表示删除数组中的第i个元素。

注意:三类操作都要满足 i <= n。

【输入描述】第1行:n,表示数组的初始长度

第2行:n个用空格间隔的数,表示原始的数组

第3行:m,表示操作的次数

接下来的m行分别是每次对数组进行的操作(题目描述中的三类操作中的一种)

【输出描述】对于第一种操作输出对应的答案,一行输出一个数。

【样例输入】

5
6 7 8 9 10
5
1 2
2 2 12
1 2
3 3
1 3

【样例输出】

7
12
8

解析

对题目的要求一步一步的实行,先保证数组的输入以后,需要对三种情况进行分类处理。第一种处理里面有输出,后面两种都是在操作。操作的要点是数组的插入和删除。插入的话,就要求插入位置后面所有数字向后移动一步,实现a[i+1]=a[i]的操作;而删除则需要当前位置后面所有的数字向前移动一步,实现a[i]=a[i+1]。这里需要注意移动的方向,要从头移动。

参考代码

#include<iostream>
using namespace std;
int a[1001];
int main()
{int n,m,p,q,v;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];cin>>m;for(int i=0;i<m;i++){cin>>p;if(p==1){cin>>q;cout<<a[q]<<endl;}else if(p==2){cin>>q>>v;for(int j=n;j>=q;j--)//挨个向后移动a[j+1]=a[j];a[q]=v;//单独把插入的数字放入位置n++; //数组长度加1}else  if(p==3){cin>>q;for(int j=q;j<n;j++)//挨个向前移动a[j]=a[j+1];n--;//数组长度减1}}return 0;
}

训练:折叠游戏

小明和小华在玩数组折叠游戏,游戏规则是,给出n个整数,按照从左到右的顺序排列,现在需要将这列整数从中间折叠m次,右边的叠加到左边,每次折叠后,重合的两个数字会相加变成一个新的数字。请你输出折叠m次后的s数组。

【输入描述】第1行:输入一个整数n表示序列的长度,输入一个整数m表示折叠的次数。

第2行:输入n个空格隔开的整数,整数不超过100。

【输出描述】输出折叠m次后的数组。

【输入样例】

5 2
1 2 3 4 5

【输出样例】

9 6

解析

数组对折,需要把后半部分移动到前半部分对应位置进行数组相加,所以移动次数为n/2(即循环次数)。

然后需要进行的就是数组加法。

最后要对数组长度也做n/2的操作。

但是这里需要注意的是,如果长度是奇数不能只是简单的n/2哦。

 

参考代码

#include<iostream>
using namespace std;
int a[10010];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)    cin>>a[i];for(int i=1;i<=m;i++){for(int j=1;j<=n/2;j++)a[j]+=a[n-j+1];if(n%2!=0)n++;n/=2;}for(int i=1;i<=n;i++)cout<<a[i]<<' ';return 0;
}

从入门到算法,再到数据结构,查看全部文章请点击此处​icon-default.png?t=N7T8http://www.bigbigli.com/

相关文章:

算法04 模拟算法之一维数组相关内容详解【C++实现】

大家好&#xff0c;我是bigbigli&#xff0c;模拟算法我们将分为几个章节来讲&#xff0c;今天我们只看一维数组相关的题目 目录 模拟的概念 训练&#xff1a;开关灯 解析 参考代码 训练&#xff1a;数组变化 解析 参考代码 训练&#xff1a;折叠游戏 解析 参考代码 …...

【技术解码】百数SRM:如何助力企业快速优化供应链管理?

SRM应用是企业优化供应链管理的重要工具&#xff0c;它帮助企业全面管理供应商关系&#xff0c;从评估、选择到协同合作和绩效监控&#xff0c;确保供应链的稳定性和效率。 对于企业来说&#xff0c;通过全面管理供应商关系&#xff0c;可以降低采购风险&#xff0c;提升产品质…...

想要用tween实现相机的移动,three.js渲染的canvas画布上相机位置一点没动,如何解决??

&#x1f3c6;本文收录于「Bug调优」专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收藏&&…...

SQL连接与筛选:解析left join on和where的区别及典型案例分析

文章目录 前言数据库在运行时的执行顺序一、left join on和where条件的定义和作用left join on条件where条件 二、left join on和where条件的区别原理不同left join原理&#xff1a;where原理&#xff1a; 应用场景不同执行顺序不同&#xff08;作用阶段不同&#xff09;结果集…...

oliva-bruteforce-luks

olivaeasyLUKS v2破解、bruteforce-luks工具使用、cryptsetup使用、cap_dac_read_searcheip、mysql使用 主机发现 ┌──(kali㉿kali)-[~/桌面/OSCP] └─$ sudo netdiscover -i eth0 -r 192.168.44.148/24服务扫描 ┌──(kali㉿kali)-[~/桌面/OSCP] └─$ sudo nmap -sV -…...

图像超分辨率重建

一、什么是图像超分辨 图像超分辨是一种技术&#xff0c;旨在通过硬件或软件的方法提高原有图像的分辨率。这一过程涉及从一系列低分辨率的图像中获取一幅高分辨率的图像&#xff0c;实现了时间分辨率向空间分辨率的转换。超分辨率重建的核心思想是利用多帧图像序列的时间带宽来…...

小米上架遇到的隐私协议问题

1. 找到【APP权限设置】&#xff0c;点击详情&#xff0c;一一对照&#xff0c;删除没用的&#xff0c;新增小米商家必须要有的内容 2. APP 存在未经用户同意读取“OAID”的行为 uniapp官方文档对应内容处...

【区分vue2和vue3下的element UI Message 消息提示组件,分别详细介绍属性,事件,方法如何使用,并举例】

在 Vue 2 中&#xff0c;我们通常使用 Element UI 的 this.$message 方法来显示消息提示&#xff0c;而不是作为一个组件直接在模板中使用。然而&#xff0c;在 Vue 3 的 Element Plus 中&#xff0c;虽然 this.$message 的使用方式仍然保留&#xff0c;但官方文档可能更倾向于…...

架构设计 - Nginx Lua 缓存配置

摘要: web 应用业务缓存通常3级: 一级缓存:JVM 本地缓存 二级缓存:Redis集中式缓存 三级缓存:Nginx Proxy Cache 缓存 或 Nginx Lua 缓存 四级缓存:静态资源CDN缓存 页面静态化 本文主要分享 Nginx Lua 缓存配置开发 鉴于 Nginx Proxy Cache 缓存的劣势,在生产项目…...

lua的GC

关于lua的gc云风大佬在 Lua GC 的源码剖析 系列文章中讲得很清楚&#xff0c;这里做一下简单的记录。 分步gc lua使用的是一种三色标记清除算法&#xff08;tri-color incremental mark & sweep&#xff09;&#xff0c;大体步骤如下&#xff1a; 初始阶段&#xff0c;所…...

基于python爬虫对豆瓣影评分析系统的设计与实现

基于python爬虫对豆瓣影评分析系统的设计与实现 Design and Implementation of a Python-based Web Crawler for Analyzing Douban Movie Reviews 完整下载链接:基于python爬虫对豆瓣影评分析系统的设计与实现 文章目录 基于python爬虫对豆瓣影评分析系统的设计与实现摘要第一…...

想让梦想照进现实?六西格玛绿带培训为你架起桥梁

六西格玛&#xff0c;这个源自摩托罗拉的质量管理方法论&#xff0c;如今已成为全球众多企业追求卓越的秘诀。它强调以数据为基础&#xff0c;通过减少变异和浪费&#xff0c;提高流程效率和质量&#xff0c;进而提升企业整体绩效。而六西格玛绿带培训&#xff0c;则是这个强大…...

大数据面试题之HDFS

目录 HDFS文件写入和读取流程 HDFS组成架构 介绍下HDFS&#xff0c;说下HDFS优缺点&#xff0c;以及使用场景 HDFS作用 HDFS的容错机制 HDFS的存储机制 HDFS的副本机制 HDFS的常见数据格式&#xff0c;列式存储格式和行存储格式异同点&#xff0c;列式存储优点有哪些? …...

(9)农作物喷雾器

文章目录 前言 1 必要的硬件 2 启用喷雾器 3 配置水泵 4 参数说明 前言 Copter 包括对农作物喷雾器的支持。该功能允许自动驾驶仪连接到一个 PWM 操作的泵和&#xff08;可选&#xff09;旋转器&#xff0c;根据飞行器速度控制液体肥料的流动速度。 稍微过时的视频显示了…...

智慧互联:Vatee万腾平台展现科技魅力

随着科技的迅猛发展&#xff0c;我们的生活正逐渐变得智能化、互联化。在这个信息爆炸的时代&#xff0c;一个名为Vatee万腾的平台正以其独特的魅力&#xff0c;引领我们走向一个更加智能的未来。 Vatee万腾&#xff0c;这个名字本身就充满了对科技未来的憧憬与期待。作为一家专…...

Charles抓包工具系列文章(四)-- Rewrite 重写工具

一、背景 这是一款比Map Local/Remote 还强大的工具&#xff0c;更加灵活&#xff0c;体现在以下几点&#xff1a; 重写request报文重写response报文header 字段的增删改query param 字段的增删改重写 body 字段改写http 响应状态status重写host/url/path 从这也可以看出其强…...

【PB案例学习笔记】-24创建一个窗口图形菜单

写在前面 这是PB案例学习笔记系列文章的第24篇&#xff0c;该系列文章适合具有一定PB基础的读者。 通过一个个由浅入深的编程实战案例学习&#xff0c;提高编程技巧&#xff0c;以保证小伙伴们能应付公司的各种开发需求。 文章中设计到的源码&#xff0c;小凡都上传到了gite…...

环境配置的相关问题

一、shap安装踩坑 遇到错误&#xff1a; A module that was compiled using NumPy 1.x cannot be run in NumPy 2.0.0 as it may crash. To support both 1.x and 2.x versions of NumPy, modules must be compiled with NumPy 2.0. Some module may need to rebuild instead…...

github配置可拉取项目到本地

首先配置用户名和邮箱&#xff1a; git config --global user.name 自己的名字git config --global user.email 自己的邮箱配置完之后检查一下&#xff1a; git config --global user.namegit config --global user.email如果提示的是自己配置好的名字和邮箱就Ok 然后拉取githu…...

Snippet-AndroidFontWeight

常用FontWeight值 <?xml version"1.0" encoding"utf-8"?> <resources><integer name"font_weight_Thin">100</integer><integer name"font_weight_ExtraLight">200</integer><integer name…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...