Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 6063 --5、 数列 (shulie)
6063: 5、 数列 (shulie)
警告!
题目
状态
题解
题目描述
小Q被一个数列迷住了。他发现这个数列可以分为连续的N段,其中第i段是连续ai个pi。小Q在想有没有快速求数列第K项的方法呢?于是他开始不断尝试计算数列第ki项的值,但计算量太大,小Q想用程序来实现自动计算,你来帮帮他吧。
输入
第一行有一个整数N, 表示数列分为N个重复段。 接下来有N行,每行有两个整数ai, pi,表示第i段重复了ai个pi。 第N+2行有一个整数M, 表示小Q有M个查询。 接下来有M个整数ki,表示小Q需要计算数列中第ki项的值。
输出
输出数据有M个,每个数依次对应了小Q一次查询的结果。
样例输入输出
输入#1
复制
2 5 1 3 2 3 1 4 8
输出#1
复制
1 1 2
提示
[样例解释] 数列有2个重复段如下: 1 1 1 1 1 2 2 2 小Q有3个查询,分别查询第1项、第4项和第8项。 查询结果为:数列中第1项的值为1,第4项的值为1,第8项的值为2。 [数据范围] 60%的数据1 <= N <=1000,1<=ai<=1000 ,1<=pi<=1000 , 1<=M<=1000 , 1<=ki<=10^6。 100%的数据1 <=N <=100000,1<=ai<=10^6,1<=pi<=10^6 , 1<=M<=10000, 1<=ki<=10^9。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
普及-
标签
前缀和
点击显示
if ($pr_flag) { ?>
递交数
17
已通过
8
} ;?>
通过率
48%
时间限制
1 秒
内存限制
128 MB
来源
2019桂城小学B
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和