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;
}
|
