Tag: 带权并查集,枚举
题目链接 | Here
题意
author: shuri001
$n$个小伙伴进行猜拳游戏,除了一个比较聪明的家伙以外,其他人只会出单一的一种,给出$m$种猜拳的结果,要求找出那个比较聪明的小伙伴序号,并且输出在第几次猜拳可以确定?
输入
多组案例输入。
先输入$n$个人(编号从0开始),$m$种结果,然后输出一行字符串代表结果。$( 1 \leq N \leq 500 \quad 0 \leq M \leq 2000 )$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| 3 3 0<1 1<2 2<0 3 5 0<1 0>1 1<2 1>2 0<2 4 4 0<1 0>1 2<3 2>3 1 0
|
输出
如下所示。
1 2 3 4
| Can not determine Player 1 can be determined to be the judge after 4 lines Impossible Player 0 can be determined to be the judge after 0 lines
|
题解
观察发现直接判断裁判个数较为困难,并且数据规模较小(2e3*5e3),因此可以使用对枚举每个人并判断是否是裁判来求解。
假设要判断第$i$人是否为裁判,只要合并与不含此人的结果,如果没有冲突,则此人可能为裁判。
由于题目给定只能存在一个裁判因此不可能出现多裁判的情况,所以枚举出来个数为0为不可能情况,而当个数>0,则为无法分辨。
当个数为1的时候,我们显然知道这个就是裁判,但最小发现的行数如何寻找呢?起始只要仔细发现,我们在排除枚举时候,其他矛盾才能确定当前枚举的人不是裁判。
所以我们只要选择枚举中所有出现矛盾的行数的(位置)最靠后一行即可。
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| #include <algorithm> #include <iostream> using namespace std;
const int maxn = 1e5+100; int dsu[maxn],val[maxn]; int u[2200],v[2200]; char op[2200];
void init(int n) {for(int i=0; i<=n*3; i++) dsu[i]=i,val[i]=0;} int find(int u) { if(dsu[u]!=u) { int k=dsu[u]; dsu[u]=find(k); val[u]=(val[u]+val[k])%3; } return dsu[u]; }
int merge(int a,int b,int k) { int fa=find(a),fb=find(b); if(fa==fb) return ((val[fa]+val[a]-val[b])%3+3)%3!=k; dsu[fa]=fb; val[fa]=((val[b]+k-val[a])%3+3)%3; return 0; }
int main() { std::ios::sync_with_stdio(false); int k,pos,idx,n,m,cnt; bool flag; while(cin >> n >> m) { if(n==1) { cout << "Player 0 can be determined to be the judge after 0 lines\n"; continue; } pos=idx=cnt=0; for(int i=0; i<m; i++) cin >> u[i] >> op[i] >> v[i]; for(int i=0; i<n; i++) { init(n); flag=1; for(int j=0; j<m; j++) { if(u[j]==i || v[j]==i) continue; if(op[j]=='<') k=1; else if(op[j]=='>') k=2; else k=0; if(merge(u[j],v[j],k)) { pos=max(pos,j); flag=0; break; } } if(flag) { cnt++; idx=i; } } if(cnt==0) cout << "Impossible\n"; else if(cnt>1) cout << "Can not determine\n"; else cout << "Player " << idx << " can be determined to be the judge after " << (pos+1) << " lines\n"; } return 0; }
|