HYSBZ-2002弹飞绵羊
某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往后弹ki步,达到第i+ki个装置,若不存在第i+ki个装置,则绵羊被弹飞。绵羊想知道当它从第i个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。
Input
第一行包含一个整数n,表示地上有n个装置,装置的编号从0到n-1,接下来一行有n个正整数,依次为那n个装置的初始弹力系数。第三行有一个正整数m,接下来m行每行至少有两个数i、j,若i=1,你要输出从j出发被弹几次后被弹飞,若i=2则还会再输入一个正整数k,表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000,对于100%的数据n<=200000,m<=100000
Output
对于每个i=1的情况,你都要输出一个需要的步数,占一行。
Sample Input4 1 2 1 1 31 12 1 11 1
Sample Output23
题解:这是一个分块的问题;我们可以将其分成sqrt(n)块,如果有剩余,使num+=1;然后分别记录从当前块到下一个快所需的步数nxt[i]以及跳到下一个快的位置id[i],如果一步不能到达下一个块 nxt[i]=nxt[i+a[i]]+1,id[i]=id[i+a[i]];(注: a[i]为第i 个弹跳的幅度),若能,nxt[i]=1,id[i]=i+a[i]。然后如果改变摸个位置的幅度,只需维护这个位置所在的块即可(可以节省时间);
AC代码为:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200005;
int belong[N],block,num,l[N],r[N],x[N],y[N];
int a[N],n,m;
void build()
{
block=sqrt(n);
num=n/block;if(n%block) num++;
for(int i=1;i<=num;i++)
l[i]=(i-1)*block+1,r[i]=i*block;
r[num]=n;
for(int i=1;i<=n;i++)
belong[i]=(i-1)/block+1;
for(int i=n;i>=1;i--)
{
if(i+a[i]>r[belong[i]])
{
x[i]=1;
y[i]=i+a[i];
}
else
{
x[i]=x[i+a[i]]+1;
y[i]=y[i+a[i]];
}
}
}
void update(int s,int k)
{
a[s]=k;
for(int i=s;i>=r[belong[s]-1];i--)
{
if(i+a[i]>r[belong[i]])
{
x[i]=1;
y[i]=i+a[i];
}
else
{
x[i]=x[i+a[i]]+1;
y[i]=y[i+a[i]];
}
}
}
int query(int s)
{
int res=0;
while(s<=n)
{
res+=x[s];
s=y[s];
}
return res;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build();
scanf("%d",&m);
int s,p,q;
for(int i=1;i<=m;i++)
{
scanf("%d",&s);
if(s==1)
{
scanf("%d",&p);
printf("%d\n",query(p+1));
}
if(s==2)
{
scanf("%d%d",&p,&q);
update(p+1,q);
}
}
}
}
最新文章
- Kafka设计解析(五)- Kafka性能测试方法及Benchmark报告
- rockmongo用法
- 转:Java NIO系列教程(二) Channel
- pytest学习笔记(三)
- 首次发布App,In-App Purchase 无法submit for review 问题的解决方案
- Android与.Net交互模拟用户屏幕操作添加APN和网络4G/3G切换
- [Everyday Mathematics]20150115
- C# - 系统类 - DateTime类
- 如何在cmd中运行数据库
- SQL server 创建表,索引,主键,外键
- cocos2d-x Loading界面实现资源加载
- perl6的介绍与下载编译安装
- eclipse创建android项目,无法正常预览布局文件
- jquery模板下载网站
- ssi服务器端指令详解(shtml)
- java中关于&;、&;&;、|、||之间的区别和运算
- 自身使用的springboot项目中比较全的pom.xml
- Python 内置os模块的简单实用
- CI框架2.x的验证码中所遇问题解决
- Ubuntu 下 redmine 安装配置
热门文章
- Go组件学习——Web框架Gin
- Jetpack Compse 实战 —— 全新的开发体验
- Ubuntu18.04.3 LTS初体验
- PHP程序员-常用工具
- jenkins手把手教你从入门到放弃01-jenkins简介(详解)
- Rio手把手教学:如何打造容器化应用程序的一站式部署体验
- [Odoo12基础教程]之第一篇-创建Todo应用
- (四)OpenStack---M版---双节点搭建---Glance安装和配置
- C#笔记01——注释、进制、基本数据类型、量和输入输出函数
- Precision,Recall,F1的计算