题解：AT_awtf2025_b Movies

dark_moon · 2025-09-10 21:18:40 · 题解

首先如果集合确定，有一个简单的贪心做法，把所有集合按照右端点升序排序，右端点相同按照左端点升序排序，对于当前考虑的区间 [L, R] 和当前每天看电影 / 没看电影的局面，从 [L, R] 中找到最小的一天，满足这天没看电影，然后让这天看电影。如果不存在这样一天，无影响。

然后就是这种题的常规想法，拆贡献，但由于各种区间、天之间互相纠缠、互相影响，不好算有多少种集合使得某一天一定看电影。但是观察贪心过程可以注意到，“极长区间”很有意义，也就是说枚举极长的看电影连续段 [l, r]，使得 l - 1 和 r + 1 没看，且 l \sim r 都看了。

但是直接考虑极长连续段，也不好算，继续寻找性质。如果我们枚举的极长区间是 [l, r]，同时集合中存在一个区间 [L_i, R_i] 使得 L_i \not \in [l, r]，如果 L_i > r，那么这个区间显然对 [l, r] 无影响，如果 L_i < l，这个区间可能对 [l, r] 产生影响，但产生影响的必要条件是 l - 1 看电影了，所以不符合我们的钦定。

于是乎，设 t_{l, r} 表示所有 L_i \in [l, r] 的区间组成的集合，求 f_{l, r} 表示，有多少个 t_{l, r} 的子集，使得 [l, r] 是极长连续段。如果求出了 f_{l, r}，由于当 [l_1, r_1] \cap [l_2, r_2] = \varnothing 的时候，t_{l_1, r_1} 和 t_{l_2, r_2} 不交，两者的 f 值可以直接相乘，所以后面的东西就简单了，直接用一个 n^2 个状态的二维 dp。dp 转移的时候要注意，我们钦定的这些极长连续段不仅不能相交，还不能相邻。

考虑怎么求 f_{l, r}。注意最开始我们的贪心，这个贪心给了我们一个考虑区间的顺序，所以把输入的区间排好序，设 f_{i, l, r} 表示考虑了前 i 个区间，当前的 f_{l, r} 的值。

当加入区间 [L, R] 的时候：

• 不选择。这时候直接 f_{i, l, r} \gets f_{i - 1, l, r}。
• 选择。
  • 当 [L, R] 被 [l, r] 包含的时候，选择这个区间对于 [l, r] 没有影响，所以 f_{i, l, r} \gets f_{i - 1, l, r}。
  • 我们可以让 [L, R] 单开一个极长区间，也就是 < i 的区间都不选，只选 i，所以 f_{i, L, L} \gets 1。
  • 如果 L = l，那么把 [L, R] 这个区间选在 [L + 1, r] 上的时候，可以让极长区间向左拓展，所以 f_{i, l, r} \gets f_{i - 1, l + 1, r}。
  • 如果 L \in [l, r] 且 R \ge r，那么根据贪心过程，可以让极长区间向右拓展，所以 f_{i, l, r} \gets f_{i - 1, l, r - 1}。
  • 还有一种情况，加入了 [L, R] 之后让两个极长区间合并了。枚举 k \in [L, R] 表示 [L, R] 使得位置 k 看电影了，那么区间分裂成了 [l, k - 1] 和 [k + 1, r]，直接 f_{i, l, r} \gets f_{i - 1, l, k - 1} \times f_{i - 1, k + 1, r}。这个转移还需要满足条件 l \le L。

算出 f 后直接用前面说的 dp 就行了。复杂度 O(n^5)，但是常数非常小。