P8252 [NOI Online 2022 提高组] 话题讨论有哪些观点？

本文共计1513个文字，预计阅读时间需要7分钟。

撰写题目解析，不拘泥于传统，不超过100字，直接输出结果：“优秀！题目解析清晰，不仅喜欢这种题型，更是子集题目的典范。题目传送门意义明确，给你（n）个子集，求出两个有交集但互不包含的子集，或判断无解。

好好写个题解， 不过还是挺喜欢这种题的， 尤其是子集题。 题目传送门 题意

给你 \(n\) 个子集，求出两个有交但互不包含的子集， 或判断无解。

题解

我挺喜欢的一类题。

我们先考虑任意两个子集（如果两个子集无交显然无解， 所以我们假定这两个子集有交）， 我们check它们， 如果合法的话直接就输出答案了， 如果不合法的话显然是一个子集包含另一个，假定是 \(x\) 包含 \(y\)。

很自然的，我们考虑是否可以用 \(x\) 代替 \(y\)， 假如有一个子集和 \(y\) 可以构成一组答案， 但是被 \(x\) 包含， 就不行了。
那可以用 \(y\) 代替 \(x\) 吗？ 也不行， 因为如果一个子集和 \(y\) 能构成答案， 但是和 \(x\) 没有交集， 就寄了。