自动搬运

查看原文

来自洛谷，原作者为

	Coffee_zzz 沉覆z

搬运于2025-08-24 23:08:46，当前版本为作者最后更新于2025-01-27 18:02:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题真的好难好难啊！

首先考虑 A 什么时候赢。

如果存在一个不大于 $n$ 的正整数 $i$，满足 B 的 $i$ 会输给 A 的 $1\sim n$ 的所有数，那么显然 A 把 B 的 $i$ 留下即可做到胜利。

否则，对于任意不大于 $n$ 的正整数 $i$，都满足存在至少一个不大于 $n$ 的正整数 $j$，使得 B 的 $i$ 不输 A 的 $j$。
这时，我们考虑一个极端情况：现存在一个长度为 $n$ 的序列 $v$，B 的每个 $i$ 都只不输 $v_i$，即会输给 $1\sim v_i-1$ 和 $v_i+1 \sim n$。
我们考虑一个可重集合 $S$，维护当前剩余的 $v_i$。在 A 把 B 的 $i$ 弃掉后，B 只需要把 $v_i$ 从 $S$ 中删掉，并选择一个不在 $S$ 中且还未被弃掉的 $j$，把 A 的 $j$ 弃掉即可。这样，在操作结束后，A 剩下的牌一定在 $S$ 中，即 B 剩下的牌不输给 A 剩下的牌。
由于在 B 操作时，不在 $S$ 中的数的数量一定不小于当前轮数，所以一定可以找到满足条件的 $j$，这样的构造是合法的。

既然极端情况 B 都可以做到不输，而其他情况显然严格弱于极端情况，所以只要不满足「存在一个不大于 $n$ 的正整数 $i$，满足 B 的 $i$ 会输给 A 的 $1\sim n$ 的所有数」，那么 B 一定不输，即「存在一个不大于 $n$ 的正整数 $i$，满足 B 的 $i$ 会输给 A 的 $1\sim n$ 的所有数」是 A 赢的条件。

接下来考虑 B 什么时候赢。

如果存在一个不大于 $n$ 的正整数 $i$，满足 B 的 $i$ 不赢 A 的 $1\sim n$ 的所有数，那么显然 A 把 B 的 $i$ 留下即可做到不输。

否则，对于任意不大于 $n$ 的正整数 $i$，都满足存在至少一个不大于 $n$ 的正整数 $j$，使得 B 的 $i$ 赢 A 的 $j$，那么我们还是可以考虑一个序列 $v$，满足 B 的每个 $i$ 赢 A 的 $v_i$，并考虑一个可重集合 $S$，维护当前剩余的 $v_i$。
在 A 把 B 的 $i$ 弃掉后，B 只需要把 $v_i$ 从 $S$ 中删掉，并选择一个不在 $S$ 中且还未被弃掉的 $j$，把 A 的 $j$ 弃掉即可。这样，在操作结束后，A 剩下的牌一定在 $S$ 中，即 B 剩下的牌会赢 A 剩下的牌。
由于在 B 操作时，不在 $S$ 中的数的数量一定不小于当前轮数，所以一定可以找到满足条件的 $j$，这样的构造是合法的。

于是，我们可以得到，只要不满足「对于任意不大于 $n$ 的正整数 $i$，都满足存在至少一个不大于 $n$ 的正整数 $j$，使得 B 的 $i$ 赢 A 的 $j$」，那么 A 一定不输，即「对于任意不大于 $n$ 的正整数 $i$，都满足存在至少一个不大于 $n$ 的正整数 $j$，使得 B 的 $i$ 赢 A 的 $j$」是 B 赢的条件。

最后，如果 A 和 B 都无法获胜，那么他们只能做到不输，即平局。

代码还挺好写的。

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define i128 __int128
#define endl '\n'
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define vei vector<int>
#define pq priority_queue
#define yes puts("yes")
#define no puts("no")
#define Yes puts("Yes")
#define No puts("No")
#define YES puts("YES")
#define NO puts("NO")
#define In(x) freopen(x".in","r",stdin)
#define Out(x) freopen(x".out","w",stdout)
#define File(x) (In(x),Out(x))
using namespace std;
const int N=1e5+5;
int a[N],b[N];
void solve(){
	int n,m;
	cin>>n>>m;
	memset(a,0,sizeof a);
	memset(b,0,sizeof b);
	for(int i=1;i<=m;i++){
		int x,y;
		char w;
		cin>>x>>w>>y;
		if(w=='>') a[y]++;
		if(w=='<') b[y]++;
	}
	int cnt=0;
	bool win=0;
	for(int i=1;i<=n;i++){
		if(a[i]==n) win=1;
		if(b[i]) cnt++;
	}
	if(win) puts("WYGRANA");
	else if(cnt==n) puts("PRZEGRANA");
	else puts("REMIS");
}
signed main(){
	ios::sync_with_stdio(0);
	signed T=1;
	cin>>T;
	while(T--) solve();
	return 0;
}