题目描述
N个小朋友(编号为0,1,2,…,N-1)一起玩石头剪子布游戏。
其中一人为裁判,其余的人被分为三个组(有可能有一些组是空的),第一个组的小朋友只能出石头,第二个组的小朋友只能出剪子,第三个组的小朋友只能出布,而裁判可以使用任意手势。
你不知道谁是裁判,也不知道小朋友们是怎么分组的。
然后,孩子们开始玩游戏,游戏一共进行M轮,每轮从N个小朋友中选出两个小朋友进行猜拳。
你将被告知两个小朋友猜拳的胜负结果,但是你不会被告知两个小朋友具体使用了哪种手势。
比赛结束后,你能根据这些结果推断出裁判是谁吗?
如果可以的话,你最早在第几轮可以找到裁判。
样例
输入
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
输出
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
算法1
对 n==1 和 m==0 进行特判
用 cnt 记录可能裁判数, tm 记录最晚冲突时刻, ans 记录裁判
枚举裁判
用边带权并查集维护已确定关系的同时,顺序遍历输入关系:如果关系涉及到裁判,不作判断;如果关系已经确定,判断其与输入关系是否一致;如果关系未确定,在并查集中新建关系
根据 cnt 输出答案
下面重点讨论对边权的构造
设 d [x] 为并查集中 x 节点与其父亲节点的关系:
d [x] == 0 表示 x 与其父亲节点 手势相同
d [x] == 1 表示 x 与其父亲节点对决 x 获胜
d [x] == 2 表示 x 与其父亲节点对决 其父亲节点获胜
这样的构造在3的剩余系下具有笔者认为非常优美的性质
-d [x] 能正确表示 将 x 节点与其父亲节点 交换位置后 其父亲节点的边权,或者说“把边反过来”
d [x] + d [y] 能正确表示 x 节点与 y 节点的父亲节点的关系
这也能解释 mrge 函数以及主函数中计算 x 与 y 的关系的正确性
C++ 代码
#include<bits/stdc++.h>
using namespace std;
inline bool read ( int &k ){
char c = getchar ();
bool neg = false;
while ( c != EOF && c != '-' && ( c < '0' || c > '9' ) )
c = getchar ();
if ( c == EOF ) return false;
if ( c == '-' ){
neg = true;
k = 0;
}else
k = c - '0';
c = getchar ();
while ( c >= '0' && c <= '9' ){
k = ( k << 1 ) + ( k << 3 ) + c - '0'; c = getchar ();
}
if ( neg ) k = -k;
}
const int N = 502;
const int M = 2002;
int fa [N], d [N], rk [N], in [M][2], rl [M];
inline void table ( int n ){
for ( int i = 1; i <= n; ++i ){
rk [i] = 1;
fa [i] = i;
d [i] = 0;
}
}
inline int get ( int x ){
if ( x == fa [x] ) return x;
int rt = get ( fa [x] );
d [x] = ( d [x] + d [ fa [x] ] ) % 3;
return fa [x] = rt;
}
inline void mrge ( int x, int y, int tx, int ty, int rl ){
if ( rk [tx] > rk [ty] ){
swap ( x, y ); swap ( tx, ty );
rl = ( 3 - rl ) % 3;
}
fa [tx] = ty;
d [tx] = ( d [y] + rl - d [x] + 3 ) % 3;
rk [ty] += rk [tx];
}
int main (){
int n, m;
while ( read ( n ) && read ( m ) ){
if ( n == 1 ){
puts ( "Player 0 can be determined to be the judge after 0 lines" );
continue;
}
if ( !m ){
puts ( "Can not determine" );
continue;
}
for ( int i = 1; i <= m; ++i ){
char s [10];
scanf ( "%s", s );
int a = 0, b = 0, t = 0, j = 0;
for ( ; s [j] >= '0' && s [j] <= '9'; ++j )
a = (a<<1)+(a<<3)+s[j]-'0';
if ( s [j] == '<' ) t = 2;
else if ( s [j] == '>' ) t = 1;
j += 1;
for ( ; j < strlen ( s ); ++j )
b = (b<<1)+(b<<3)+s[j]-'0';
in [i][0] = a+1; in [i][1] = b+1; rl [i] = t;
}
int cnt = 0, tm = 0, ans = 0;
for ( int h = 1; h <= n; ++h ){
table ( n );
for ( int i = 1; i <= m; ++i ){
int tx, ty;
int x = in [i][0]; if ( x != h ) tx = get ( x );
int y = in [i][1]; if ( y != h ) ty = get ( y );
int t = rl [i];
if ( x != h && y != h ){
if ( tx == ty ){
int now = ( d [x] - d [y] + 3 ) % 3;
if ( t != now ){
tm = max ( i, tm );
break;
}
}else{
mrge ( x, y, tx, ty, t );
}
}
if ( i == m ){
ans = h;
cnt ++;
}
}
}
if ( !cnt )
puts ( "Impossible" );
else if ( cnt > 1 )
puts ( "Can not determine" );
else
printf ( "Player %d can be determined to be the judge after %d lines\n", ans-1, tm );
}
return 0;
}