#PQJ2879x16203. QOJ 2879_16203

    ID: 2881 传统题 3000ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:SCOI 2024枚举

QOJ 2879_16203

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 页