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

LJN1117 · 2025-10-20 08:53:32 · 题解

考虑对于 Alice 的必胜策略，由于 Alice 是先手删除 Bob 的牌，变相的是 Bob 具有决定权，所以显然 Alice 需要有 n 张牌同时指向 Bob 的一张牌。

对于 Bob 的必胜策略，由于后手选择，他都可以选出最优策略，那么也就说明只要他的每一张牌都指向了 Alice 的至少一张牌，那么他就必胜。

若两者均不符合，则平局。

code:

#include<bits/stdc++.h>
#define int long long
#define maxn 100100

using namespace std;

int t,n,m;
int a[maxn],b[maxn];

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) a[i]=b[i]=0;
    for(int i=1;i<=m;i++){
        int x,y;
        char w;
        cin>>x>>w>>y;
        if(w=='<') a[y]++;
        else b[y]++;
    }
    for(int i=1;i<=n;i++) if(b[i]==n){
        cout<<"WYGRANA\n";
        return ;
    }
    for(int i=1;i<=n;i++) if(!a[i]){
        cout<<"REMIS\n";
        return ;
    }
    cout<<"PRZEGRANA\n";
    return ;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}