题解：P11604 [PA 2016] 卡牌 / Gra w karty

· · 题解

[PA 2016] 卡牌 / Gra w karty

大受震撼，感觉不止黄吧。

分别考虑 \rm Bob 和 \rm Alice 能不能赢，如果都不能赢那就是平局。

若 a > b ，则令 a 向 b 连一条边。这样原图会形成一个两边都是 n 个点的二分有向图。我们令 \rm Alice 的点为左部， \rm Bob 的点为右部。

对于 \rm Bob 来说，如果说他有某个点没有出边，那么 \rm Alice 只要一直保留这个点不删， \rm Bob 就一定赢不了。否则， \rm Bob 一定可以一直保持每个点都有出边的情况直到最后，也就赢了。考虑归纳证明：假设当前 \rm Alice 和 \rm Bob 都有 n 个点，且 \rm Bob 的每个点都有出边，那么不论 \rm Alice 删了哪个点， \rm Bob 都会剩下 n-1 个有出边的点。这时候 \rm Alice 任然剩下 n 个点，显然 \rm Bob 一定能删掉一个点，使得他的 n-1 个点任然都有出边，因为最坏情况下是每个点的出度都恰好为 1 且出集互不相同，这样任然存在一个能删的点。

而对于 \rm Alice ，由于他是先手删的，因此会很不利。观察样例发现，如果 \rm Bob 有一个入度为 n 的点，那么她只需要一直留着这个点，无论 \rm Bob 怎么删她都能赢。其他情况下 \rm Alice 一定赢不了，同样考虑归纳证明：假设两人都有 n 个点，无论 \rm Alice 删了哪个点，此时 \rm Bob 会剩下 n-1 个点，且每个点的入度最多为 n-1 。我们不妨只考虑入度为 n-1 的点（因为对于其他点，无论 \rm Bob 怎么删，都不会成为满入度的点），如果存在某个入度为 n-1 的点 i ，而唯一一个没有连向 i 的点为 j ，那么 \rm Bob 一定不能删除 j ，否则 i 就会成为满入度的点。由于 \rm Bob 只有 n-1 个点，因此这样的 i 最多只有 n-1 个，因此 j 也最多只有 n-1 个。那么只要删掉不是某个 j 的点就行了。

#include<bits/stdc++.h>
#define ll long long
#define pn putchar('\n')
#define mset(a,x) memset(a,x,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof a)
#define all(a) a.begin(),a.end()
#define fls() fflush(stdout)
using namespace std;
int re()
{
    int x=0;
    bool t=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
        t=ch=='-'?0:t,ch=getchar();
    while(ch>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return t?x:-x;
}
const int maxn=2e5+5;
int n,m;
int cd[maxn],rd[maxn];
void solve()
{
    n=re(),m=re();
    mset(cd,0);
    mset(rd,0);
    while(m--)
    {
        int u=re();
        char ch=getchar();
        int v=re();
        if(ch=='>')
            rd[v]++;
        else
            cd[v]++;
    }
    bool ans=1;
    for(int i=1;i<=n;i++)
    {
        if(rd[i]==n)
        {
            puts("WYGRANA");
            return;
        }
        if(!cd[i])
            ans=0;
    }
    puts(ans?"PRZEGRANA":"REMIS");
}
signed main()
{
    int T=re();
    while(T--)
        solve();
    return 0;
}