题意: n个人玩石头剪刀布,每个人每次出的手势都是一样的,除了裁判(裁判可以任意出)。现在给出他们之间的胜负关系,问哪一个是裁判,并输出最早是在哪一行确定的。
解法: 枚举裁判,然后对裁判外的其他人作类似于食物链的并查集操作,如果只存在一次一个人删除后其余人不出错的情况,那么那个人就是裁判。
最早确定是裁判的那行一定是最迟出错的那一行。笔者表示想不出证明。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int INF = ~0u>>1; #define REP(i,a,b) for(int i=(a); i<(b); i++) #define FOR(i,a,b) for(int i=(a); i<=(b); i++) #define FORP(i,a,b) for(int i=(a); i>=(b); i--) #define clr(a,b) memset(a,b,sizeof(a)) #define PB push_back const int MAXN = 510; int fa[MAXN]; int rel[MAXN]; int err[MAXN]; struct edge { int u,v,op; }g[MAXN*4]; int n,m; int Find(int x) { if(fa[x] == x) return x; int ff = fa[x]; fa[x] = Find(fa[x]); rel[x] = (rel[x] + rel[ff]) % 3; return fa[x]; } int merge(int a, int b, int op) { int aa = Find(a); int bb = Find(b); if(aa == bb) return 0; fa[aa] = bb; rel[aa] = (rel[b] - rel[a] + op + 3) % 3; return 1; } int main() { while(~scanf("%d%d", &n, &m)) { char c; REP(i,0,m) { scanf("%d%c%d", &g[i].u, &c, &g[i].v); if(c == '=') g[i].op = 0; else if(c == '>') g[i].op = 1; else g[i].op = 2; } clr(err,-1); REP(i,0,n) { REP(j,0,n) { fa[j] = j; rel[j] = 0; } REP(j,0,m) { if(g[j].u==i || g[j].v==i) continue; if(!merge(g[j].u,g[j].v,g[j].op)) { // printf("merging error\n"); if(rel[g[j].u] != (rel[g[j].v]+g[j].op)%3) { err[i] = j + 1; break; } } } } int a1 = 0,a2 = 0,cnt = 0; REP(i,0,n) { if(err[i] == -1) { cnt ++; a1 = i; } a2 = max(a2,err[i]); } // printf("cnt = %d , a1 = %d, a2 = %d\n", cnt,a1,a2); if(cnt > 1) printf("Can not determine\n"); else if(cnt == 0) printf("Impossible\n"); else { printf("Player %d can be determined to be the judge after %d lines\n",a1,a2); } } return 0; }