正文
VIJOS-P1078 松鼠吃果子
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
洛谷 P2069 松鼠吃果子
https://www.luogu.org/problemnew/show/P2069
JDOJ 1256: VIJOS-P1078 松鼠吃果子
https://neooj.com:8082/oldoj/problem.php?id=1256
题目描述
有N个一种松鼠喜欢吃的果子由下向上串排成一列,并标号1,2,...N。一只松鼠从最下果子开始向上跳,并且第i次跳可以一次跳过i*i*i除以5的余数+1个果子(=i*i*i%5+1),并把脚下的果子吃了,如果上面有果子,在重力作用下,都将向下掉下一格。如第1次跳从第一个果子上跳过1*1*1%5+1=2个果子,可跳到第3个果子上,并把第3个果子吃了;第2次从第4个果子上(落在原来第三个果子位置)跳过2*2*2%5+1=4个到第8个果子上,并把第8个吃了;如此...。
当然,总有一次松鼠会跳出这串果子的最前面,设为每K次,它吃不到任何果子了。这时它回到最下面的果子上,重做它的第K次跳,以求吃到果子。如此,问它吃的第m只果子(即第M跳吃到的果子)的标号是什么?
输入输出格式
输入格式:
一共两行,分别为N和m。(1<=m<=n<=200,并且满足能够跳到第m次)
输出格式:
一个数,即它吃的第m只果子的标号
输入输出样例
输入样例#1: 复制
10
4
输出样例#1: 复制
9
说明
输入样例#1: 复制
10
4
输出样例#1: 复制
9
注:吃掉的果子依次为3,8,4(回到下面重做第3跳),9(回到下面重做第4跳)
模拟题。
如果用数组模拟的话,单点删除实在是过于费劲。
然后想到了动态数组,但是模模糊糊地记忆动态数组不支持单点删除。
但是打数组模拟累死了。
看了题解加百度搜索之后,我发现了这么一个函数:a.erase();
括号里加地址,可以删除那个点的元素,其他元素落下来。
简直就是为了这个题而生的啊!!
所以就有了代码,一开始WA了几次,需要一些细节处理。
#include<cstdio>
#include<vector>
using namespace std;
vector<int> a;
int pos=;
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
a.push_back(i);
for(int i=;i<=m;i++)
{
int t=i*i*i%+;
pos+=t;
if(pos>a.size())
pos=t+;
if(i!=m)
a.erase(a.begin()+pos-);
}
printf("%d",a[pos-]);
return ;
}
首先理解好pos=t+1的意思,一开始的位置可不是0,是1,所以要把开始的1加上。
a.begin是指向vector中的第一个元素,这个位置就是1,所以要在后面把pos多加的1减去。
同理,最后输出也是如此。