#2312. 重整山河

    ID: 2312 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>PROV赛事:contest2879来源:qoj.ac数据:公开样例枚举贪心

重整山河

重整山河

题目描述

CCF NOI 2024 四川省代表队评测活动 第一试 重整山河(rebuild) 重整山河(rebuild) 【题目描述】 世界被怪兽入侵了!小 W 要重建世界,他要先解决所有的怪兽。 一共有 𝑛 只怪兽,第 𝑖 只怪兽有 𝑎𝑖 的血量和 𝑏𝑖 的爆炸伤害,怪兽的血量互不相同。当 一只怪兽的血量小于等于 0 时称为死亡,否则称其存活。第 𝑖 只怪兽死亡时会对其余所有存活 的怪兽造成 𝑏𝑖 的爆炸伤害。 小 W 是被世界选中的勇者,他有一把圣剑,一次可以对任意一只怪造成 +∞ 的伤害。但 圣剑不能使用无数次,所以小 W 希望最小化使用圣剑的次数。 遗憾的是,探测装置收到了干扰,小 W 只能知道 𝑏𝑖 是一个在很小的区间 [𝑙𝑖, 𝑟𝑖] 里的整 数。 现在,小 W 想知道,对于所有可能的序列 {𝑏},他使用的圣剑的最小次数的和。小 W 有 特殊能力,他只需要知道这个和对 𝑀 取模的结果。 【输入格式】 从文件 rebuild.in 中读入数据。 输入的第一行包含三个整数 𝑛, 𝑚, 𝑀,其中 𝑚 是 𝑏𝑖 所属区间的限制。 接下来 𝑛 行,每行三个整数 𝑎𝑖, 𝑙𝑖, 𝑟𝑖,表示第 𝑖 只怪兽的血量,以及 𝑏𝑖 所处的区间 [𝑙𝑖, 𝑟𝑖],保证 𝑟𝑖≤𝑚。 【输出格式】 输出到文件 rebuild.out 中。 输出一行一个整数,表示答案。 【样例1 输入】 1 4 2 308641732 2 8 1 1 3 5 1 2 4 2 1 1 5 3 1 2 【样例1 输出】 1 8 第8 页 共9 页

CCF NOI 2024 四川省代表队评测活动 第一试 重整山河(rebuild) 【样例1 解释】 总共有四种 {𝑏},这里以 {1, 1, 1, 1} 为例。 怪兽的血量和爆炸伤害用二元组表示为 {(8, 1), (5, 1), (2, 1), (3, 1)},最优策略为对 (8, 1), (5, 1) 使用圣剑,此时产生 2 的爆炸伤害,(2, 1) 死亡,再产生 1 的爆炸伤害,总共为 3 的爆炸伤害进而导致 (3, 1) 死亡,使用次数为 2。 与上同理可得所有情况使用圣剑的次数都是 2,答案为 2 × 4 = 8。 【样例2】 见选手目录下的 rebuild/rebuild2.in 与 rebuild/rebuild2.ans。 这个样例满足测试点 1 ∼2 的条件限制。 【样例3】 见选手目录下的 rebuild/rebuild3.in 与 rebuild/rebuild3.ans。 这个样例满足测试点 7 ∼12 的条件限制。 【样例4】 见选手目录下的 rebuild/rebuild4.in 与 rebuild/rebuild4.ans。 这个样例满足测试点 13 ∼20 的条件限制。 【样例5】 见选手目录下的 rebuild/rebuild5.in 与 rebuild/rebuild5.ans。 这个样例满足测试点 13 ∼20 的条件限制。 【数据范围】 对于所有测试数据保证:1 ≤𝑛≤20,1 ≤𝑙𝑖≤𝑟𝑖≤𝑚≤15,1 ≤𝑎𝑖≤300, 2 ≤𝑀≤109 + 7。 测试点编号 𝑛≤ 𝑚≤ 特殊性质 1 ∼2 20 15 𝑙𝑖= 𝑟𝑖 3 ∼6 𝑟𝑖−𝑙𝑖≤1 7 ∼12 10 7 1 ≤𝑎𝑖≤70 13 ∼20 20 15 无 【注意事项】 相信一下常数。 第9 页 共9 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 2 308641732
8 1 1
5 1 2
2 1 1
3 1 2
8

样例 2

20 15 715511970
130 9 9
74 14 14
41 7 7
72 7 7
268 4 4
134 10 10
39 8 8
141 7 7
218 4 4
19 13 13
162 5 5
49 5 5
184 5 5
278 12 12
135 12 12
75 5 5
122 12 12
157 13 13
153 10 10
292 9 9
8