题解：P7234 [JSOI2014] 歌剧表演

· · 题解

题目传送门

大致思路

我们可以考虑维护一个集合。初始情况下，所有人都在编号为 0 的集合中。

对于每一场表演，如果有两个表演者在同一个集合中，那么我们就可以区分这两个人和其他人，所以我们可以将这场演出中在同一个集合中的表演者（可以排序一下，方便查找）分裂出去，组成一个新的集合。

接下来 check 一下，如果有集合的长度为 1，则说明这个人可以被认出，此时标记当前的演出编号，最后输出。（具体步骤请看代码注解）。

具体代码

#include<bits/stdc++.h>
#define F(i,a,b) for(register int i=a;i<=b;i=-~i)
#define D(i,a,b) for(register int i=a;i>=b;i=~-i)
using namespace std;const int N=1e5+2;
int n,m,xr[N],len[N],st[N],ans[N],num[2*N],sum,cnum;//异或和 集合长度 所在集合 答案
pair<int,int> p[N];//集合-人的编号
signed main(){
    cin>>n>>m;
    p[0]=make_pair(-1,-1);//记得初始化，不然会爆零 
    len[0]=n;//第一个的集合长度为人的数量 
    F(i,1,n)xr[0]^=i;
    F(K,1,m){
        int k=0,cnt=0;cin>>k;cnum=0;
        F(i,1,k){
            int x;cin>>x;
            if(ans[x]==0)p[++cnt]=make_pair(st[x],x);//将x丢进集合 
        }sort(p+1,p+cnt+1); 
        F(i,1,cnt){
            if(p[i].first!=p[i-1].first){//两个人所在集合不同 
                st[p[i].second]=++sum;
                num[++cnum]=p[i].first;
                num[++cnum]=sum;
            }else st[p[i].second]=sum;//相同 
            len[p[i].first]--;xr[p[i].first]^=p[i].second;
            len[sum]++;xr[sum]^=p[i].second;
        }F(i,1,cnum)if(len[num[i]]==1)ans[xr[num[i]]]=K;//记录当前演出编号 
    }F(i,1,n)cout<<ans[i]<<" ";
    return 0;
}