大家好,我是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;
}
从入门到算法,再到数据结构,查看全部文章请点击此处http://www.bigbigli.com/