CF797E. Array Queries
a is an array of n positive integers, all of which are not greater than n.
You have to process q queries to this array. Each query is represented by two numbers p and k. Several operations are performed in each query; each operation changes p to p + ap + k. There operations are applied until p becomes greater than n. The answer to the query is the number of performed operations.
Input
The first line contains one integer n (1 ≤ n ≤ 100000).
The second line contains n integers — elements of a (1 ≤ ai ≤ n for each i from 1 to n).
The third line containts one integer q (1 ≤ q ≤ 100000).
Then q lines follow. Each line contains the values of p and k for corresponding query (1 ≤ p, k ≤ n).
Output
Print q integers, ith integer must be equal to the answer to ith query.
Example
3
1 1 1
3
1 1
2 1
3 1
2
1
1
Consider first example:
In first query after first operation p = 3, after second operation p = 5.
In next two queries p is greater than n after the first operation.
题意:
给你q次查询,每次会有两个数字p,k,问每次使p=p+a[p]+k,总共需要多少次会使p>n
题解:
存粹暴力必然超时,因此需要打个表,
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const int INF=-0x3f3f3f3f;
int a[MAXN];
int dp[MAXN][510];
int main()
{
int n;
scanf("%d",&n);
for (int i = 1; i <=n ; ++i) {
scanf("%d",&a[i]);
}
for(int i=n;i>=1;i--) {//表示为p,由大->小,我们需要变化的次数增加
for (int j = 1; j <=500; ++j) {//表示为k的大小
if(i+a[i]+j>n) dp[i][j]=1;
else
dp[i][j]=dp[i+a[i]+j][j]+1;
}
}
int ans=0;
int m;
scanf("%d",&m);
int p,k;
while(m--)
{
ans=0;
scanf("%d%d",&p,&k);
if(k>400)
{
while(p<=n)
{
p=p+a[p]+k;
ans++;
}
printf("%d\n",ans);
}
else
printf("%d\n",dp[p][k]);
}
return 0;
}
最新文章
- Docker实践--部署Nodejs应用
- hbase
- coursera机器学习笔记-建议,系统设计
- python-数据类型补充及文件处理操作
- gulp学习笔记1-定义
- Centos镜像使用帮助
- HTML5自学笔记[ 19 ]canvas绘图实例之炫彩时钟
- String性能优化
- Sprint第二个冲刺(第二天)
- hdu2955 Robberies 01背包+概率
- awk笔记
- CSS设置DIV背景色渐变显示
- PL/pgSQL学习笔记之十一
- Qt仿Android带特效的数字时钟源码分析(滑动,翻页,旋转效果)
- WPF笔记(1.2 Navigation导航)——Hello,WPF!
- robotframework常见问题解决汇总
- python 元组用法
- 提交变更(git commit)
- SQL优化总结之一
- Promise.all和Promise.race区别,和使用场景
热门文章
- [转]C#利用委托跨线程更新UI数据
- C#面向对象几组关键字的详解(this,base,dynamic,var,const,readonly,is,as)
- SharePoint 计时器作业
- javascript:json对象和json字符串的相互转换
- OpenCV视觉库
- 一款带有CSS的单选框以及选中事件
- 【BZOJ4025】二分图(LCT动态维护图连通性)
- 使用 NetBackup 命令创建 Hyper-V 策略(命令创建其他策略也是如此)
- 百度Ueditor 图片上传无反应,显示上传0张,不能点确定
- 【转】使用webmagic搭建一个简单的爬虫