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

· · 题解

这题真的好难好难啊！

首先考虑 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;
}