「KTSC 2023 R2」会议室 2 题解

问题深入分析

问题重述

我们有 $N$ 个会议，每个会议有开始时间 $S[i]$ 和结束时间 $E[i]$。需要找到所有移除序列的数量，使得在 $N-1$ 天的移除过程中，每天的成本总和最小。

关键概念理解

1. 会议相关性

• 直接相关：两会议时间重叠
• 间接相关：通过其他会议相连
• 这实际上定义了图的连通分量

2. 成本计算 对于某一天的会议集合，成本是所需的最少会议室数。

• 在区间图中，最少会议室数 = 最大重叠会议数
• 这等于区间图的色数，也等于最大团的规模

3. 移除序列的最优性 每天移除一个会议，要使得每天的成本总和最小。这意味着我们需要选择移除顺序，使得每天的最大团规模尽可能小。

算法详细解析

步骤1：预处理和排序

// 初始化组合数学工具
inv[0] = fac[0] = 1;
for (int i = 1; i <= n; ++i) {
    a[i] = {S[i-1], E[i-1]};
    inv[i] = (H - H/i) * inv[H%i] % H;  // 模逆元
    fac[i] = fac[i-1] * i % H;          // 阶乘
}

// 按开始时间排序，结束时间降序
sort(a + 1, a + n + 1, [&](seg A, seg B) {
    return A.l == B.l ? A.r > B.r : A.l < B.l;
});

排序目的：将会议按时间顺序排列，便于后续的连通分量划分。

步骤2：划分独立连通分量

for (int lst = 1, mx = 0, i = 1; i <= n; ++i) {
    mx = max(mx, a[i].r);
    if (i == n || a[i+1].l >= mx) {
        calc(lst, i);
        lst = i + 1;
    }
}

原理：如果下一个会议的开始时间 ≥ 当前所有会议的最大结束时间，说明它们属于不同的连通分量。

例子：

会议1: [1,3], 会议2: [2,4], 会议3: [5,7]

会议1和2重叠，会议3独立，形成两个连通分量。

步骤3：单个连通分量的DP计算（核心）

坐标压缩

int mn = N, m = 0;
for (int i = L; i <= R; ++i) {
    mn = min(mn, a[i].l - 1);
    m = max(m, a[i].r);
}
m -= mn;
// 将所有时间平移，使得最小时间为1

DP状态定义

f[l][r]：考虑时间区间 [l,r]，该区间内会议的合法移除序列方案数。

g[l][r]：时间区间 [l,r] 内包含的会议数量。

DP状态转移

基础转移（不包含端点会议）：

add(f[l][r], f[l+1][r] + f[l][r-1] - f[l+1][r-1] + H);

这利用了容斥原理：[l+1,r]的方案 + [l,r-1]的方案 - [l+1,r-1]的方案。

处理包含端点的会议：

for (int i : Gl[l]) {  // 所有以l开始的会议
    if (i < r) {
        add(f[l][r], f[l+1][r] - f[l+1][r-1] 
            - f[i+1][r] + f[i+1][r-1] + 2*H);
    }
}

这里计算了包含会议 [l,i] 对方案数的贡献。

关键归一化

f[l][r] = f[l][r] * inv[R - L + 1 - g[l][r]] % H;

这个步骤确保我们正确计算了概率或权重，是算法的核心之一。

步骤4：结果合并

for (int i = 1; i <= n; ++i)
    ans = ans * fac[cnt[i]] % H;

原理：不同连通分量的移除顺序相互独立。如果某个大小的连通分量出现了 cnt[i] 次，那么这些分量的内部顺序可以任意排列。

算法正确性证明

为什么这样划分连通分量？

在区间图中，两个会议属于同一连通分量当且仅当它们的时间区间在时间轴上连续重叠。我们的划分方法正好捕捉到了这一性质。

为什么DP状态这样设计？

f[l][r] 实际上在计算：在时间区间 [l,r] 内，所有会议的"最优移除序列"的数量。通过从小区间向大区间递推，我们能够累积所有可能的合法序列。

时间复杂度分析

• 排序：$O(n \log n)$
• 连通分量划分：$O(n)$
• 每个连通分量的DP：最坏 $O(n^2)$
• 总复杂度：$O(n^2)$，对于 $n \leq 2000$ 是可接受的

总结

本题的难点在于： $1.$ 理解会议相关性形成的图结构 $2.$ 将最优移除序列问题转化为组合计数问题 $3.$ 设计高效的DP状态和转移方程

该解法通过巧妙的区间划分和动态规划，成功地将一个复杂的最优化计数问题在多项式时间内解决。