P8252 [NOI Online 2022 提高组] 讨论 题解

· · 题解

文中 k_x 和 S_x 的定义与题目相同。

文中所有 x,y,z 都指人的编号，i 都指题目的编号。

首先考虑一个暴力：

对于每一个题目 i，找出会 i 这道题的所有人，将其按会的题目数 k_x 从小到大排序。

然后我们检查上述排序后相邻的两个人是否会讨论即可。

这个暴力的正确性证明：

因为每次被排序的人都至少会同一道题 i，所以只要考虑是否完全包含即可。

假设 x,y,z 三个人会同一题 i 并且 k_x \leq k_y \leq k_z，那么如果 x,y 和 y,z 间都不会讨论，那么必然有 S_x \subseteq S_y \subseteq S_z，那么 x,z 也必然不会讨论。

考虑优化上述暴力。

首先将所有人按 k_x 从小到大排序，依次插入。

如果我们对于每一道题 i 记录下会 i 这道题的上一个人 lst_i，那么每次插入一个人 x 的时候只需要检查 \forall i \in S_x，lst_i 与 x 会不会讨论。

但是这样由于每一个 S_x 会被多次检查，复杂度仍然不对。

随后我们发现，在遍历 S_x 的时候可以顺便求出 S_x 与所有 S_{lst_i} 的交集大小，于是我们可以直接通过交集大小是否为 k_{lst_i} 来判断两个集合是否完全包含，即会不会讨论。

这样每次插入一个人的时间复杂度变为 \Theta(|S_x|)。

总体复杂度 \Theta(n \log n +m)，使用桶排可以去掉 \log。

Code：

int n;
int k[1000006],a[1000006];
vector <int> p[1000006];
int cnt[1000006];
inline void clear(vector <int> X) {
    vector <int> e;
    e.swap(X);
}
inline bool cmp(int x,int y) {
    return k[x]<k[y];
}
int vis[1000006];
inline void work() {
    for(int i=1; i<=n; ++i) vis[i]=0;
    for(int i=1; i<=n; ++i) cnt[i]=0;
    n=read();
    for(int i=1; i<=n; ++i) {
        k[i]=read();
        clear(p[i]);
        p[i].resize(k[i]);
        for(int u=0; u<k[i]; ++u) p[i][u]=read();
        a[i]=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int t=1; t<=n; ++t) {
        int i=a[t];
        if(k[i]==0) continue;
        for(int u=0; u<k[i]; ++u) {
            ++cnt[vis[p[i][u]]];
        }
        for(int u=0; u<k[i]; ++u) {
            int g=vis[p[i][u]];
            if(g!=0&&cnt[g]<k[g]&&cnt[g]<k[i]) {
                puts("YES");
                write(i); putchar(' '); write(g); puts("");
                return ;
            }
        }
        for(int u=0; u<k[i]; ++u) {
            --cnt[vis[p[i][u]]];
            vis[p[i][u]]=i;
        }
    }
    puts("NO");
}