题目描述
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
算法
用扩展域并查集
时间复杂度为
$O(n)$
实际上容易写错的地方就是图中红色字体写的部分
c++代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;
#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
const int maxn = 500 + 10;
const int maxm = 2000 + 10;
int pa[maxn * 3];
void initPa(int n) {
_rep(i, 0, n) pa[i] = i;
}
// usage: initPa(n * 3)
// self: x lower: x + n greater: x + n * 2
class Expr {
public:
int x;
char op;
int y;
};
Expr expr[maxm];
int n, m;
int line[maxm];
void init() {
Set(line, 0);
}
int find(int x) {
return x == pa[x] ? x : pa[x] = find(pa[x]);
}
bool conflict(const Expr& expr) {
int x = expr.x, y = expr.y;
char op = expr.op;
//debug(op);
if(op == '>') {
//puts("ok");
if((find(x) == find(y)) || (find(x) == find(y + n * 2))) return 1;
pa[find(x + n * 2)] = find(y);
pa[find(x)] = find(y + n);
pa[find(x + n)] = find(y + n * 2);
}
if(op == '<') {
//puts("ok");
if((find(x) == find(y)) || (find(x) == find(y + n))) return 1;
pa[find(x + n)] = find(y);
pa[find(x)] = find(y + n * 2);
pa[find(x + n * 2)] = find(y + n);
}
if(op == '=') {
//puts("ok");
if((find(x) == find(y + n)) || (find(x + n) == find(y))) return 1;
pa[find(x)] = find(y);
pa[find(x + n)] = find(y + n);
pa[find(x + n * 2)] = find(y + n * 2);
}
return 0;
}
void Rochambeau() {
//
_for(i, 0, m) scanf("%d%c%d", &expr[i].x, &expr[i].op, &expr[i].y);
//debug(expr[0].op);
init();
int cnt = 0, id = 0;
_for(i, 0, n) {
// i is judge
bool fail = 0;
_rep(k, 0, n * 3) pa[k] = k;
_for(j, 0, m) {
Expr cur = expr[j];
//debug(cur.x);
//debug(cur.y);
if(cur.x != i && cur.y != i && conflict(cur)) {
fail = 1;
if(j > line[i]) line[i] = j + 1;
break;
}
}
if(!fail) {
id = i;
cnt++;
}
}
//debug(cnt);
if(!cnt) puts("Impossible");
else if(cnt == 1) {
int ans = 0;
_for(i, 0, n) if(line[i] > ans) ans = line[i];
printf("Player %d can be determined to be the judge after %d lines\n", id, ans);
}
else puts("Can not determine");
}
int main() {
//freopen("input.txt", "r", stdin);
while (scanf("%d%d", &n, &m) != EOF) Rochambeau();
}
牛逼%
毕竟枚举了裁判
你这是$O(n^2)$的吧
嗯,写错了
$O(nm)$