#PQJ3342x17201. QOJ 3342_17201
QOJ 3342_17201
第一试猫和老鼠(game) IOI2026 中国国家队选拔 猫和老鼠(game) 【题目描述】 《猫和老鼠》是一部家喻户晓的动画片。小G 根据这部动画片设计了一个游戏。在 这个游戏中,玩家需要帮助Tom 使用机器猫抓住Jerry。 Jerry 的活动范围是数轴上的区间[0, m]。初始时刻(即第0 秒时),Jerry 可能位于 该区间内的任意位置。之后,它可以在该区间内自由移动,但任意时刻的速度不会超过 每秒1 单位长度。 Tom 有n 个可供部署的机器猫,其中部署第i (1 ≤i ≤n) 个机器猫的成本为wi。 若部署了第i (1 ≤i ≤n) 个机器猫,则其会在第ti 秒从位置ai 出现,然后以每秒1 单 位长度的速度向位置bi 匀速移动,并在抵达后消失。 Jerry 初始拥有k 点生命值。每当它与一个机器猫完全重合时(即存在某个时刻,两 者位置完全相同),其生命值将减少1,该机器猫也会随之失效。当Jerry 的生命值.小.于 .或.等.于0 时,Tom 即成功抓住Jerry。 小G 设定Tom 必须在初始时刻就部署好机器猫。因此,玩家需要在游戏开始前选 定若干个机器猫进行部署。玩家获胜当且仅当部署好机器猫后,对于Jerry 所有可能的 移动路径,Tom 均能成功抓住Jerry。 小G 为这个游戏设计了很多关卡,并邀请你进行测试。为了控制游戏难度,小G 计划为部署机器猫的成本总和设置一个合理的上限。你需要帮助小G 求出,玩家获胜 所需部署的机器猫的成本总和的最小值。 【实现细节】 .选.手.不.需.要,.也.不.应.该.实.现main .函.数。 选手需要确保提交的程序包含头文件game.h,即在程序开头加入以下代码: #include "game.h" 1 选手需要在提交的程序源文件中实现以下函数: long long game(int n, int m, int k, std::vector a, 1 std::vector b, std::vector t, std::vector w); • n, m, k 分别表示机器猫的个数、Jerry 的活动范围与Jerry 的初始生命值。 • 对于0 ≤i < n,ai, bi, ti, wi 分别表示第i + 1 个机器猫的出现位置、最终位置、 出现时间与部署成本。 • 该函数需要返回成本总和的最小值。特别地,如果部署所有机器猫也无法获胜, 则返回−1。 • 对于每个测试点,该函数会被交互库调用.不.超.过20 .次。 第2 页 共14 页 第一试猫和老鼠(game) IOI2026 中国国家队选拔 .注.意:.在.任.何.情.况.下,.交.互.库.运.行.所.需.时.间.均.不.会.超.过0.1 .秒,.所.用.内.存.为.固.定.大 .小,.且.均.不.超.过64 MiB。 【测试程序方式】 .试.题.目.录.下.的grader.cpp .是.交.互.库.参.考.实.现,.最.终.测.试.时.所.用.的.交.互.库.实.现.与.该 .参.考.实.现.有.所.不.同,.因.此.选.手.的.解.法.不.应.该.依.赖.交.互.库.实.现。 选手可以在本题目录下使用如下命令编译得到可执行程序: g++ grader.cpp game.cpp ‐o game ‐O2 ‐std=c++14 ‐static 1 对于编译得到的可执行程序: • 可执行文件将从.标.准.输.入读入以下格式的数据: – 输入的第一行包含一个正整数t,表示测试数据组数。 – 接下来依次为每组测试数据,对于每组测试数据: ∗第一行包含三个正整数n, m, k,分别表示机器猫的个数、Jerry 的活动 范围与Jerry 的初始生命值。 ∗第i + 1 (1 ≤i ≤n) 行包含四个非负整数ai, bi, ti, wi,分别表示第i 个 机器猫的出现位置、最终位置、出现时间与部署成本。 • 可执行文件将输出以下格式的数据至.标.准.输.出: – 对于每组测试数据,输出一行一个整数,表示成本总和的最小值。特别地, 如果部署所有机器猫也无法获胜,则输出−1。 【样例1 输入】 3 1 4 10 1 2 0 6 0 1 3 4 8 6 2 4 10 2 7 3 5 0 8 4 4 6 3 6 2 7 2 6 0 0 8 4 0 1 0 9 5 0 2 0 10 7 9 2 11 3 0 1 7 12 3 6 1 8 13 第3 页 共14 页 第一试猫和老鼠(game) IOI2026 中国国家队选拔 6 9 4 9 14 3 0 7 3 15 3 6 7 3 16 3 6 7 5 17 6 9 10 5 18 【样例1 输出】 6 1 ‐1 2 35 3 【样例1 解释】 该样例共包含三组测试数据。 对于第一组测试数据,玩家可以选择部署第1, 2, 3 个机器猫,成本总和为1+2+3 = 6。若玩家选择部署第1, 3 个机器猫,则当Jerry 初始时刻位于位置7,且从第6 秒开始 以每秒1 单位长度的速度匀速移动至位置1 时,Tom 无法成功抓住Jerry。 对于第二组测试数据,当Jerry 初始时刻位于位置5.5 且不移动时,它只会与第1 个机器猫在第3.5 秒时完全重合,因此部署所有机器猫也无法获胜。 对于第三组测试数据,玩家可以选择部署第1, 2, 3, 4, 5, 7 个机器猫,成本总和为 7 + 8 + 9 + 3 + 3 + 5 = 35。 【附加文件说明】 在附加文件中:
- grader.cpp 是提供的交互库参考实现。
- game.h 是头文件,选手不用关心具体内容。
- template_game.cpp 是提供的示例代码,选手可参考并实现自己的代码。 【子任务】 设N, S 分别为单个测试点内所有测试数据的n, nk 的和。对于所有测试数据,均 有: • 1 ≤n ≤5 × 104,N ≤3 × 105; • 1 ≤m ≤109,1 ≤k ≤10,S ≤106; • 对于所有1 ≤i ≤n,均有0 ≤ai, bi ≤m,0 ≤ti, wi ≤109。 第4 页 共14 页 第一试猫和老鼠(game) IOI2026 中国国家队选拔 子任务编号 分值 特殊性质 n ≤ k ≤ 103 AC 1 3 1 5 × 104 BC 2 7 103 3 5 C 10 5 × 104 4 15 103 5 22 1 5 × 104 6 8 无 7 27 300 10 5 × 104 8 13 特殊性质A:m ≤103,且对于所有1 ≤i ≤n,均有ti ≤106。 特殊性质B:对于所有1 ≤i ≤n,均有ai ≤bi。 特殊性质C:对于所有1 ≤i ≤n,均有wi = 0。 【评分方式】 .注.意: • 选手不应当通过非法方式获取交互库的内部信息,如直接与标准输入、输出流进 行交互。此类行为将被视为作弊; .最.终.的.评.测.交.互.库.与.样.例.交.互.库.的.实.现.不.同。 • .本.题.首.先.会.受.到.和.传.统.题.相.同.的.限.制,例如编译错误会导致整道题目得0 分,运行 时错误、超过时间限制、超过空间限制等会导致相应测试点得0 分等。选手只能在程序 中访问自己定义的变量以及交互库给出的变量,尝试访问其他地址空间将可能导致编译 错误或运行错误。 在上述条件基础上: • 对于每个测试点,程序得到满分当且仅当每次调用game 函数时返回的答案均正 确。 第5 页 共14 页