P11347 「KTSC 2023 R2」学生

naoliaok_lovely · 2024-12-23 15:22:23 · 题解

一道有趣的思维题，不过好像比较板。

先考虑题目的朴素版：已知若干集合（相较于原题目少了区间补集的限制），求最早有一个人发现自己不在某集合内的时间。
设 f(S) 表示包含所有 S 中的人的集合构成的总集合。讨论在每个时间结束的条件：

• 第一轮结束，显然条件为 \exist i,f(\{i\})=\varnothing。
• 第二轮结束，此时意味着所有的人都至少被一个集合包含。考虑 \exist i,j,f(\{i,j\})=\varnothing，此时在 i 的眼中，如果包含 i 的集合是所有集合，就没有集合能够包含 j，那么 j 会在第一轮报告。这说明包含 i 的集合并不是所有集合，于是 i 会在第二轮报告，同理 j 也会在第二轮报告。
• 第三轮结束，不难证明充要条件是 \exist i,j,k,f(\{i,j,k\})=\varnothing。
• ……

于是我们得到结论：第 i 轮结束的充要条件是 \exist f(\{x_1,x_2\dots,x_i\})=\varnothing，且报告的人的集合为满足上述条件的并。

回到原问题，即求出最少的人数，使得每一个区间的补集都不能完全包含之。这又等价于每一个区间都至少包含一个人。这是一个十分基础的问题，贪心扫一遍即可求出最小人数。还要求所有合法构造的人集合的并，这个就左右分别扫一遍，记录下两次贪心的方案，判断在强制选 i 号点之后能取到最小人数是不是刚刚的答案即可。

时间复杂度 O(n\log n)。