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

集训队互测投题——封印

《封印》解题报告

题目大意

你是一名大魔法师,现在遇到了 \(n\) 只怪物,第 \(i\) 只怪物的出现时间为 \([l_i,r_i)\),有经验值 \(w_i\)。对于怪物 \(i\),你可以选择一个实数 \(k_i\in[l_i,r_i]\),并在 \([l_i,k_i)\) 时间内施展封印术控制这只怪物。特别地,如果 \(k_i=l_i\),表示你没有对这种怪物施展封印术。由于人是有极限的,在同一时刻,你最多对 \(K\) 个怪物施展法术,\(K\) 为给定常数。

由于你已经很久没有使用过封印术了,在 \(0\) 时刻你的熟练度为 \(0\)。对于怪物 \(i\),如果 \(k_i=r_i\),那么你就成功封印了这只怪物,所以在 \(r_i\) 时刻你的熟练度就会增加 \(w_i\);如果 \(k_i<r_i\),那么怪物就会在 \(k_i\) 时刻攻击你,使得熟练度重置为 \(0\)

在任意时刻,设此时熟练度为 \(W\),你可以选择施展终极秘术,将时间线上的所有的 \(n\) 只怪物变成 \(W\) 枚金币,并带着它们离开。如果同一时刻发生多个事件(熟练度增加、熟练度重置、终极秘术),它们之间的生效顺序可以任意安排。

现在,请求出你最多能带着多少枚金币离开。

数据范围

对于所有数据,\(n,l_i,r_i,w_i,K\) 均为正整数,\(1\leq K\leq n\leq 3\times 10^5,1\leq w_i\leq10^9,1\leq l_i<r_i\leq 10^9\),且保证 \(l_1,l_2,\dots,l_n,r_1,r_2,\dots,r_n\)\(2n\) 个不同正整数。

各子任务特殊约束及分值如下:

  • 子任务 1(5 分):\(n\leq 20\)

  • 子任务 2(15 分):\(n\leq 1000,w_i=1\)

  • 子任务 3(15 分):\(n\leq 1000\)

  • 子任务 4(30 分):\(w_i=1\)

  • 子任务 5(35 分):无特殊性质。

解题过程

http://www.hskmm.com/?act=detail&tid=19172

相关文章:

  • 一天一款实用的AI工具,第4期,AI翻译成英语
  • Docker基础与工程部署
  • 安装MariaDB服务器流程介绍在Ubuntu 22.04系统
  • 三种神器让LLM输出结构化数据:LangChain、LlamaIndex与Function Calling实战指南
  • win11安装ensp
  • 自己湿热内蕴出汗痒和岳母生病2天不洗澡发痒的不同-完美解释小孩为啥没那么容易痒
  • vue: ubuntu安装vue环境
  • golang实现ai聊天窗口
  • 源码反码补码
  • 图的分类法:解耦数据和图表类型
  • IDEA 2024的零卡死配置
  • 数据结构
  • Python + MediaPipe 手势绘画高级应用:从基础到创意交互 - 实践
  • Crypto 2021 s Accepted papers
  • Github 12.3kstar, 3分钟起步做中后台?Go+Vue 脚手架,把权限、代码生成、RBAC 都封装好了
  • 250927
  • 完整教程:多线程——单例模式
  • A Twisty Movement
  • 完整教程:iOS 混淆与反调试反 Hook 实战,运行时防护、注入检测与安全加固流程
  • Attention进阶史(MHA, MQA, GQA, MLA)
  • 2025北京个性旅行自由行口碑推荐北京汇通清源国际旅游公司,满足独特需求,自由随心
  • 2025推拉门品牌推荐榜:聚焦玻璃推拉门,钛镁合金推拉门选择指南
  • 9-27
  • 图解KV Cache
  • [K230学习笔记 00] 前言
  • 博弈论
  • [CEOI 2025] theseus 做题记录
  • 2025 年钣金加工厂家最新推荐排行榜发布:江门,珠三角钣金加工厂选择指南
  • 全文 -- Vortex: Extending the RISC-V ISA for GPGPU and 3D-Graphics Research - 指南
  • 2025.9.26 - 9.30