luogu#P11346. 「KTSC 2023 R2」会议室 2
「KTSC 2023 R2」会议室 2
题目背景
请勿用 C++14 (GCC 9) 提交。
请在代码开头加入如下代码:
#include<vector>
int count_removals(std::vector<int> S, std::vector<int> E);
题目描述
题目译自 2023년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T2 「회의실 2」
KDH 公司每天会举行 场会议。每场会议都有一个编号,从 到 。对于每个 ,第 场会议在时间 开始,在时间 结束。
KDH 公司安排会议的方式很特别。如果某一天进行的两场不同会议 和 满足以下条件之一,则称这两场会议在该天是相关的:
- 两场会议有重叠的时间段。
- 存在第三场会议 ,使得 和 都与 相关。
如果两场会议 和 在该天不是相关的,则称它们在该天是无关的。KDH 公司在安排会议时,会将每场会议分配到特定的会议室。要求在同一天内,无关的会议不能分配到同一个会议室。KDH 公司会选择满足这些条件的分配方案中所需会议室数量最少的方案。所需的最少会议室数量称为会议的成本。
KDH 公司认为目前的会议安排浪费了太多资源,决定将会议数量减少到只剩一场。为此,KDH 公司将在 天内每天进行以下操作:
- 选择一个尚未取消的会议。
- 从当天起永久取消该会议。
- 进行所有未取消的会议。
当这个过程结束时,除了最后一场会议外,所有会议都被取消。最后剩下的会议是哪一场并不重要。
为了进一步节省成本,KDH 公司希望找到一种方法,使得在 天内每天的总成本最小。你需要计算出有多少种方法可以实现这一目标。两种方法相同的定义是:在 天内每天选择取消的会议完全相同。即使剩下的会议分配方式不同,只要每天取消的会议相同,就认为是相同的方法。由于方法数量可能非常大,结果需要对 取模。
你需要实现以下函数:
int count_removals(vector<int> S, vector<int> E);
S, E
:大小为 的整数数组。对于每个 ,第 场会议在时间 开始,在时间 结束。- 该函数返回在 天内每天的总成本最小的情况下,选择取消会议的方法数量,对 取模。
注意,提交的代码中不应包含任何输入输出操作。
输入格式
示例评测程序按以下格式读取输入:
- 第 行:
- 第 行:
输出格式
示例评测程序按以下格式输出:
- 第 行:函数
count_removals
返回的值
4
1 2
3 4
5 6
7 8
24
10
1 5
2 3
4 7
6 11
8 9
10 15
12 13
14 20
16 17
18 19
13280
10
1 20
2 9
3 4
5 8
6 7
10 17
11 16
12 13
14 15
18 19
845040
10
1 5
2 9
3 10
4 12
6 14
7 16
8 17
11 18
13 19
15 20
1797408
10
12 16
5 7
10 19
2 3
4 6
17 20
8 11
1 15
14 18
9 13
647760
提示
样例 1 解释
考虑 的情况。
评测程序将调用如下函数:
count_removals([1,3,5,7], [2,4,6,8]);
无论选择哪种方式取消会议,每天所需的会议室数量(即成本)依次为 、、,总成本为 。因此,所有方法都是可行的。
函数应返回 24
。
数据范围
对于所有输入数据,满足:
- 对于每个 ,
- 对于每个 ,$S[i] \neq S[j], S[i] \neq E[j], E[i] \neq S[j], E[i] \neq E[j]$
详细子任务附加限制及分值如下表所示。
子任务 | 分值 | 附加限制 |
---|---|---|
; | ||
任意时刻进行的会议最多为 场 | ||
对于每个 ,不存在 的 对 | ||
对于每个 ,不存在 的 对 | ||
无附加限制 |