P8252 [NOI Online 2022 提高组] 讨论

题目传送门

题意

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

题解

我挺喜欢的一类题。

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

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

事实上， 我们的想法是随意check两个子集， 不合法的话就用一个代替另一个， 这样使复杂度降至 \(O(n)\)，那么我们是否可以选择两个最小的子集check呢？

考虑按子集大小排序，每次取出最小的那个子集 \(y\)， 然后找到和它有交的最小子集 \(x\)(不包括他自己)，check它们，如果不合法的话：我们用 \(x\) 代替 \(y\)， 也就是直接把 \(y\) 删掉。

为什么呢？如果存在一组答案 \((y, z)\)， 那么 \(z\) 和 \(y\) 有交， 也一定和 \(x\) 有交， 假如 \(x\) 包含 \(z\)，那么和 \(y\) 有交且最小的子集就不可能是 \(x\) 了， 不成立。 所以 \(x,z\) 互不包含且 \(z\) 和 \(x\) 有交，所以 \((x, z)\) 也一定能构成一组答案， 把 \(y\) 删掉显然可以。

实现

预处理出每个点匹配的子集(比它大且和它有交的最小子集)后， 每次暴力check最小子集和它的匹配子集， 复杂度乍一看是对的(我考场人傻了也是这么写的)， 其实是错的， 因为每次暴力check的复杂度是 \(O(|x| + |y|)\) 的， 假如有一个很大的子集， 被前面的子集匹配了很多次，复杂度就退化到 \(O(nm)\) 了。

你可以看成一棵树巴拉巴拉做，但是没必要，我们还是考虑暴力：优化check复杂度。

我们考虑一种 $O(|y| \log m) $ 复杂度的做法， 就是每次check的复杂度是小的那个子集大小的：考虑把对于每个集合开一个map， 记录这个集合有哪些元素，check时枚举小的那个集合中的元素，判断时否在大的集合出现过， 就可以求出它们的交集。 如果交大于 \(0\) 且小于小子集大小，就是合法的。 这样做是 \(O(m \log m+n)\) 的， 因为每个点只会作为小的子集出现一次，然后就被删除了。

我还是喜欢用线性做法，桶排一手，我们换一个想法，复杂度爆炸的原因是因为有些子集被匹配了多次， 求交的时候重复计算了这个集合。 这是冗余，是重复计算，我们要考虑复用！！！我们倒过来做： 我们开一个标记数组，从最大的子集开始，每次把这个集合中所有元素都打上标记， 然后处理前面所有匹配了这个子集的集合， 对于每个集合， 我们只要求出有多少被标记的元素即可求出交集，线性！

如果你不知道如何预处理出 比它大且和它有交的最小子集， 直接从大的子集开始往小：对于每个子集， 给它包含的所有元素打上这个集合的编号标记， 然后对于每个子集， 它包含的所有元素中，标记的集合中大小最小的既是，你也可以直接看代码。

有一本书叫 《设计模式：可复用的面向对象软件设计》 ， 我觉得这本书实在是太炫酷了，推荐大家看看。

桶排有点丑， 就不写了。

#include 
#include 
#include 
#include 
using namespace std;

int read(){
    int num=0, flag=1; char c=getchar();
    while(!isdigit(c) && c!='-') c=getchar();
    if(c == '-') flag=-1, c=getchar();
    while(isdigit(c)) num=num*10+c-'0', c=getchar();
    return num*flag; 
}

const int N = 2e6+1000;
int T, n, q[N], vis[N], fla[N];
vector s[N], deal[N];

bool cmp(int a, int b){return s[a].size() < s[b].size();}

void solve(){
    for(int i=n; i; i--){
        int x = q[i];
        for(auto j : s[x]) fla[j] = x;
        for(auto y : deal[x]){
            int res = 0;
            for(auto j : s[y]) if(fla[j] == x) res++;
            if(res && res < s[y].size()) {
                printf("YES\n%d %d\n", x, y);
                return ;
            }		
        }
    }
    printf("NO\n");
}

int main(){
    T = read();
    while(T--){
        n = read();
        for(int i=1; i<=n; i++) {
            int k = read(); s[i].clear(); deal[i].clear();
            while(k--) s[i].push_back(read());
            q[i] = i, fla[i] = vis[i] = 0;
        }
        sort(q+1, q+1+n, cmp);
        for(int i=n; i; i--){
            int res = 0;
            for(auto x : s[q[i]]) {
                if(!res) res=vis[x]; 
                else if(vis[x] && s[vis[x]].size() < s[res].size()) res = vis[x];
            }
            deal[res].push_back(q[i]);
            for(auto x : s[q[i]]) vis[x] = q[i];
        }
        solve();
    }
    return 0;
}

快省选了，加油啊各位！！