app要有网站做基础,建筑设计专业是干什么的,如何制作一个简单的网页链接,怎么制作图片文件大家好#xff0c;我是bigbigli#xff0c;模拟算法我们将分为几个章节来讲#xff0c;今天我们只看一维数组相关的题目 目录
模拟的概念
训练#xff1a;开关灯
解析
参考代码
训练#xff1a;数组变化
解析
参考代码
训练#xff1a;折叠游戏
解析
参考代码 … 大家好我是bigbigli模拟算法我们将分为几个章节来讲今天我们只看一维数组相关的题目 目录
模拟的概念
训练开关灯
解析
参考代码
训练数组变化
解析
参考代码
训练折叠游戏
解析
参考代码 模拟的概念
模拟算法就是模拟题目给的操作用代码一步一步的描述出来即可。在过程中使用的都是我们已知的各种方法如数组元素调用、排序、枚举等等只是这些过程一般比较复杂。本次课程主要针对一维数组的模拟。
在各类算法竞赛中包括CSP-J/SNOIP等竞赛经常会出现各类“模拟题目”遇到这种题大家不需要害怕甚至可以将其作为“送分题”因为你只需要按照题目叙述的方式来写程序就能得到最终答案。模拟不是一种算法而是一种技巧要想掌握模拟题目就需要多读题、多整理细节问题。 训练开关灯
有n盏灯从1到n按顺序依次编号初始时所有灯都处于开启状态有m个人从1到m依次编号。
第一个人将灯全部关闭第二个人将编号为2的倍数的灯打开第三个人将编号为3的倍数的灯做相反处理即将打开的灯关闭将关闭的灯打开。依照编号递增顺序以后的人都一样将凡是自己编号倍数的灯做相反处理。
请问当第m个人操作之后哪几盏灯是关闭的按从小到大输出其编号用逗号间隔。
【输入描述】一行n和m空格隔开
【输出描述】顺次输出关闭的灯的编号,用逗号隔开
【输入样例】10 1010
【输出样例】1,4,9 解析
因为灯只会出现0和1两种情况我们可以使用数组元素来表示类似桶随后只需要重复m次每次寻找当前序号的倍数为下标的元素进行更改如果是1就变成0是0就变成1。
最后对数组元素进行判断找出是0的元素就行数组元素下标的输出。
输出时要注意的问题是用逗号隔开不同于用空格隔开。 参考代码
#includeiostream
using namespace std;
int a[1010];//全部是0表示关闭
int main()
{int n,m;cinnm;for(int i2;im;i)//从第二个人开始操作for(int ji;jn;ji)//编号对应倍数下标if(a[j]1) a[j]0;else a[j]1;//更改状态cout1;//1号肯定关闭for(int i2;in;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[i1]a[i]的操作而删除则需要当前位置后面所有的数字向前移动一步实现a[i]a[i1]。这里需要注意移动的方向要从头移动。 参考代码
#includeiostream
using namespace std;
int a[1001];
int main()
{int n,m,p,q,v;cinn;for(int i1;in;i)cina[i];cinm;for(int i0;im;i){cinp;if(p1){cinq;couta[q]endl;}else if(p2){cinqv;for(int jn;jq;j--)//挨个向后移动a[j1]a[j];a[q]v;//单独把插入的数字放入位置n; //数组长度加1}else if(p3){cinq;for(int jq;jn;j)//挨个向前移动a[j]a[j1];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哦。 参考代码
#includeiostream
using namespace std;
int a[10010];
int main()
{int n,m;cinnm;for(int i1;in;i) cina[i];for(int i1;im;i){for(int j1;jn/2;j)a[j]a[n-j1];if(n%2!0)n;n/2;}for(int i1;in;i)couta[i] ;return 0;
}
从入门到算法再到数据结构查看全部文章请点击此处http://www.bigbigli.com/
