「JSOI2014」歌剧表演

「JSOI2014」歌剧表演

传送门

没想到吧我半夜切的

这道题应该算是 \(\text{JSOI2014}\) 里面比较简单的吧。。。

考虑用集合关系来表示分辨关系，具体地说就是我们把所有演员分成若干个集合，满足同一个集合内的演员两两不能分辨。

初始时所有演员位于同一个集合内。

然后对于某次参加了演出的演员，他们可能分别来自不同的集合，那么这些集合就会有两类不同的组成元素：一种是参加了当前这次演出的，另外一种是没参加的。

那么我们就需要把这两种元素分开，也就是把这个集合拆成两个。

有解的情况就是一个演员单成一个集合。

具体操作可以用 \(\text{set}\) 来实现。

参考代码：

#include <algorithm>

#include <cstdio>

#include <set>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

template < class T > inline void read(T& s) {

    s = 0; int f = 0; char c = getchar();

    while ('0' > c || c > '9') f |= c == '-', c = getchar();

    while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

    s = f ? -s : s;

}

const int _ = 1e5 + 5;

int n, m, a[_], tot, id[_], ans[_];

set < int > S[_];

inline int cmp(const int& i, const int& j) { return id[i] < id[j]; }

int main() {

#ifndef ONLINE_JUDGE

    file("cpp");

#endif

    read(n), read(m), tot = 1;

    for (rg int i = 1; i <= n; ++i) S[id[i] = 1].insert(i);

    for (rg int x, i = 1; i <= m; ++i) {

        read(x);

        for (rg int o = 1; o <= x; ++o) read(a[o]);

        sort(a + 1, a + x + 1, cmp);

        for (rg int l = 1, r; l <= x; l = r + 1) {

            r = l;

            while (r < x && id[a[r + 1]] == id[a[l]]) ++r;

            if (S[id[a[l]]].size() == r - l + 1) continue ;

            int now = id[a[l]]; ++tot;

            for (rg int j = l; j <= r; ++j) S[now].erase(a[j]), S[id[a[j]] = tot].insert(a[j]);

            if (S[now].size() == 1 && !ans[*S[now].begin()]) ans[*S[now].begin()] = i;

            if (S[tot].size() == 1 && !ans[*S[tot].begin()]) ans[*S[tot].begin()] = i;

        }

    }

    for (rg int i = 1; i <= n; ++i) printf("%d%c", ans[i], " \n"[i == n]);

    return 0;

}