社保官方网站登录入口,汤阴县seo快速排名有哪家好,企业网站源码免费带数据库,企业做什么需要有网站题目背景
时/空限制#xff1a;1s / 64MB
题目描述
贝茜已经精通了变成炮弹并沿着长度为 N 的数轴弹跳的艺术#xff0c;数轴上的位置从左到右编号为 1,2,…,N 。
她从某个整数位置 S 开始#xff0c;以 1 的起始能量向右弹跳。
如果贝茜的能量为 k #xff0c;则她将…题目背景
时/空限制1s / 64MB
题目描述
贝茜已经精通了变成炮弹并沿着长度为 N 的数轴弹跳的艺术数轴上的位置从左到右编号为 1,2,…,N 。
她从某个整数位置 S 开始以 1 的起始能量向右弹跳。
如果贝茜的能量为 k 则她将弹跳至距当前位置向前距离 k 处进行下一次弹跳。
从 1 到 N 的每个整数位置上均有炮击目标或跳板。
每个炮击目标和跳板都有一个在 0 到 N 范围内的整数值。
一个数值为 v 的跳板会使贝茜的能量增加 v 并反转她的方向。
一个数值为 v 的炮击目标会当着陆时能量不小于 v 时被击破。
着陆在炮击目标上不会改变贝茜的能量和方向。
被击破的炮击目标将保持击破状态贝茜依然可以该炮击目标上弹跳同样不会改变能量和方向。
如果贝茜弹跳无限长的时间直到她离开数轴她会击破多少个炮击目标
如果贝茜开始时位于一个她可以击破的炮击目标她会立刻将其击破。
类似地如果贝茜开始时位于一个跳板跳板的效果将在她第一次跳跃之前生效。
输入格式
输入的第一行包含 N 和 S 其中 N 为数轴的长度S 为贝茜的起始位置。
以下 N 行描述了每一个位置。其中第 i 行包含整数 qi 和 vi 如果位置 i 上有一个跳板则 qi0 位置 i 上有一个炮击目标则 qi1 vi 是位置 i 上的跳板或炮击目标的数值。
输出格式
输出一个整数为将被击破的炮击目标数量。
输入输出样例
输入 #1复制
5 2
0 1
1 1
1 2
0 1
1 1
输出 #1复制
1
输入 #2复制
6 4
0 3
1 1
1 2
1 1
0 1
1 1
输出 #2复制
3
说明/提示
数据范围 1≤N≤10^5 , 1≤S≤N , 0≤qi≤1 , 0≤vi≤N 样例1解释 贝茜从坐标 2 开始这是一个数值为 1 的炮击目标所以她立刻击破了它。
然后她弹跳至坐标 3 这是一个数值为 2 的炮击目标所以她无法击破它。
她继续弹跳至坐标 4 这改变了她的方向并将她的能量增加了 1 达到 2 。
她跳回至坐标 2 这是一个已经被击破的炮击目标所以她继续弹跳。
此时她弹跳至了坐标 0 因此她停了下来。
她击破了恰好一个炮击目标位于坐标 2 。 样例2解释 贝茜经过的路径为 4→5→3→1→6 下一次弹跳将会使她离开数轴11 。
她依次击破了炮击目标 4,3,6 。
AC代码
#include bits/stdc.h
using namespace std;
const int N 1e5 10;
int n, s, q[N], v[N], ans 0;
bool vis[N];
int main() {cin n s;for (int i 1; i n; i) {cin q[i] v[i];}int energy 1, dir 1; for (int i 1; i 1000 * N; i) {if (q[s] 0) { energy v[s];dir * -1;} else { if (!vis[s] energy v[s]) {vis[s] 1;ans;}}s dir * energy;if (s 1 || s n) break;}cout ans endl;return 0;
}
