当前位置: 首页 > news >正文

炮弹【USACO】

题目背景

时/空限制: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 上有一个跳板则 qi=0 ,位置 i 上有一个炮击目标则 qi=1 ,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;
}

相关文章:

炮弹【USACO】

题目背景 时/空限制&#xff1a;1s / 64MB 题目描述 贝茜已经精通了变成炮弹并沿着长度为 N 的数轴弹跳的艺术&#xff0c;数轴上的位置从左到右编号为 1,2,…,N 。 她从某个整数位置 S 开始&#xff0c;以 1 的起始能量向右弹跳。 如果贝茜的能量为 k &#xff0c;则她将…...

python如何读取excel文件内的数据

目录 前言一、安装openpyxl二、读取Excel数据总结前言 在Python中读取Excel数据,最常用的库之一是openpyxl(用于.xlsx格式)和xlrd(尽管xlrd从版本2.0开始不再支持.xlsx,仅支持旧的.xls格式)。然而,对于大多数现代应用来说,openpyxl是一个更好的选择,因为它支持.xlsx格…...

Java项目: 基于SpringBoot+mybatis+maven+mysql教师工作量管理系统(含源码+数据库+毕业论文)

一、项目简介 本项目是一套基于SpringBootmybatismavenmysql教师工作量管理系统 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 该系统功能完善、界面美观…...

项目开发--数据库--postgresql数据库操作

背景 1、安装postgresql的基础方法 2、基本操作命令 解决方案 安装命令 在ubuntu环境当中进行安装。 sudo apt install postgresql安装完毕之后直接进行测试&#xff0c;如果看到如下内容则安装成功。 sudo systemctl status postgresql使用DBeaver进行连接报错&#xff…...

c语言——用一维数组输出杨辉三角形

一.代码 #include <stdio.h> int Num[100]; int Hang; int Lie; int a; int Flag; int main() {Lie 1;Hang 1;a 0;while (1) {//列1为1if (Lie 1) {Num[1] 1;Lie;}//数据存到数组里面while (Hang > Lie && Hang ! 2) { if (Hang!Lie) {Flag Num[Lie] …...

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单&#xff0c;不做解释 C 对于 x y 两个方向&#xff0c;每一个方向至少需要 x / k 向上取整的步数&#xff0c;取最大值。 由于 x 方向先移动&#xff0c;假如 x 方向需要的步数多于 y 方向的步数&#xff0c;那么最后 y 方向的那一步就不需要了&#xff0c;答案…...

为什么构造函数不能为虚函数?为什么析构函数可以为虚函数,如果不设为虚函数可能会存在什么问题?

目录 一、为什么构造函数不能为虚函数&#xff1f; 二、为什么析构函数可以是虚函数&#xff1f;如果不设为虚函数可能会存在什么问题&#xff1f; 构造函数不能为虚函数&#xff0c;因为在构造过程中&#xff0c;虚函数机制尚未生效&#xff0c;对象还未完成构造&#xff0c…...

【数据结构】单链表功能的实现

目录 1.链表的概念及结构 2.单链表功能的实现 2.1打印单链表 2.2创建节点 2.3单链表尾插 2.3单链表头插 2.5单链表尾删 2.6单链表头删 2.7单链表的查找 2.8在指定位置之前插入数据 2.9在指定位置之后插入数据 2.10删除pos节点 2.11删除pos之后的节点 2.12销毁链表…...

最新车型库大全|阿里云实现调用API接口

整体请求流程&#xff1a; 介绍&#xff1a; 本次解析通过阿里云云市场的云服务来实现查询车型库大全查询&#xff0c;首先需要选择一家可以提供查询的商品。 [探数API]车型库查询_API专区_云市场-阿里云 步骤1: 选择商品 如图点击免费试用&#xff0c;即可免费申请该接口数…...

70. 爬楼梯

70. 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f; 示例 1&#xff1a; 输入&#xff1a;n 2 输出&#xff1a;2 解释&#xff1a;有两种方法可以爬到楼顶。 1.1 阶 1 阶 2.2 阶 示例…...

pytorch正向传播没问题,loss.backward()使定义的神经网络中权重参数变为nan

记录一个非常坑爹的bug:loss回传导致神经网络中一个linear层的权重参数变为nan 1.首先loss值是正常数值&#xff1b; 2.查了好多网上的解决办法&#xff1a;检查原始输入神经网络数据有没有nan值&#xff0c;初始化权重参数&#xff0c;使用relu激活函数&#xff0c;梯度裁剪&a…...

❤《实战纪录片 1 》原生开发小程序中遇到的问题和解决方案

《实战纪录片 1 》原生开发小程序中遇到的问题和解决方案 文章目录 《实战纪录片 1 》原生开发小程序中遇到的问题和解决方案1、问题一&#xff1a;原生开发中 request请求中返回 的数据无法 使用this传递给 data{}中怎么办&#xff1f;2、刚登录后如何将token信息保存&#xf…...

2024.9.6 作业

手写unique_ptr指针指针 代码&#xff1a; #include <iostream> #include <stdexcept>template <typename T> class unique_ptr { public:// 构造函数explicit unique_ptr(T* ptr nullptr) : m_ptr(ptr) {}// 析构函数~unique_ptr() {delete m_ptr;}// 禁…...

2024年架构设计师论文-“模型驱动架构设计方法及其应用”

论模型驱动架构设计方法及其应用 模型驱动架构设计是一种用于应用系统开发的软件设计方法&#xff0c;以模型构造、模型转换和精化为核心&#xff0c;提供了一套软件设计的指导规范。在模型驱动架构环境下&#xff0c;通过创建出机器可读和高度抽象的模型实现对不同问题域的描述…...

Tapd敏捷开发平台的使用心得

Tapd敏捷开发平台的使用心得 一、Tapd 简介 TAPD(Tencent Agile Product Development),腾讯敏捷产品研发平台行业领先的敏捷协作方案,贯穿敏捷产品研发生命周期的一站式服务,了解敏捷如下图 二、几个核心模块概念 需求迭代缺陷故事墙前期项目需求的管理,可以按类别建…...

远程桌面 Rust Desk 自建服务器

因为某些原因(诈骗)&#xff0c;Rush Desk 服务已暂停国内访问&#xff0c;今天我们介绍如何利用自己的服务器搭建 Rust Desk 远程桌面&#xff0c;低延迟电脑远程手机&#xff0c;手机远程电脑等 一、准备工作 准备一台服务器&#xff0c;我用的腾讯云服务器&#xff0c;一年…...

开源网安引领AIGC+开发安全,智能防护铸就软件安全新高度

近日&#xff0c;国内网络安全领域知名媒体数说安全正式发布了《2024年中国网络安全市场100强》和《2024年中国网络安全十大创新方向》。开源网安凭借在市场表现力、资源支持力以及产品在AI方向的创新力上的优秀表现成功入选百强榜单&#xff0c;并被评为“AIGC开发安全”典型厂…...

树和二叉树

树 节点&#xff08;Node&#xff1a;&#xff09; 树由一系列的节点组成&#xff0c;每个节点可以包含数据和指向其他节点的链接。 节点通常包含一个数据元素和若干指向其他节点的指针 根节点&#xff08;Root&#xff09;&#xff1a; 树的顶部节点称为根节点&#xff0c…...

一篇带你速通差分算法(C/C++)

个人主页&#xff1a;摆烂小白敲代码 创作领域&#xff1a;算法、C/C 持续更新算法领域的文章&#xff0c;让博主在您的算法之路上祝您一臂之力 欢迎各位大佬莅临我的博客&#xff0c;您的关注、点赞、收藏、评论是我持续创作最大的动力 差分算法是一种在计算机科学中常用的算法…...

贷款利率高低跟什么有关?仅凭身份证就能贷到款?额度是多少?

在金融的广阔舞台上&#xff0c;借款人的“信用基石”——即其综合资质&#xff0c;是决定贷款利率高低的决定性因素。这并非偶然&#xff0c;而是银行基于详尽的风险评估与收益预期所做出的精准判断。 需明确的是&#xff0c;贷款的易得性并不意味着无门槛的放任。它更像是设置…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

鸿蒙(HarmonyOS5)实现跳一跳小游戏

下面我将介绍如何使用鸿蒙的ArkUI框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...