专栏文章

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

__abcd_
P11604题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqdrdat
此快照首次捕获于
2025/12/04 03:08
3 个月前
此快照最后确认于
2025/12/04 03:08
3 个月前
查看原文

[PA 2016] 卡牌 / Gra w karty

大受震撼，感觉不止黄吧。
分别考虑 Bob\rm Bob 和 Alice\rm Alice 能不能赢，如果都不能赢那就是平局。
若 a>ba > b，则令 aa 向 bb 连一条边。这样原图会形成一个两边都是 nn 个点的二分有向图。我们令 Alice\rm Alice 的点为左部，Bob\rm Bob 的点为右部。
对于 Bob\rm Bob 来说，如果说他有某个点没有出边，那么 Alice\rm Alice 只要一直保留这个点不删，Bob\rm Bob 就一定赢不了。否则，Bob\rm Bob 一定可以一直保持每个点都有出边的情况直到最后，也就赢了。考虑归纳证明：假设当前 Alice\rm Alice 和 Bob\rm Bob 都有 nn 个点，且 Bob\rm Bob 的每个点都有出边，那么不论 Alice\rm Alice 删了哪个点，Bob\rm Bob 都会剩下 n−1n-1 个有出边的点。这时候 Alice\rm Alice 任然剩下 nn 个点，显然 Bob\rm Bob 一定能删掉一个点，使得他的 n−1n-1 个点任然都有出边，因为最坏情况下是每个点的出度都恰好为 11 且出集互不相同，这样任然存在一个能删的点。
而对于 Alice\rm Alice，由于他是先手删的，因此会很不利。观察样例发现，如果 Bob\rm Bob 有一个入度为 nn 的点，那么她只需要一直留着这个点，无论 Bob\rm Bob 怎么删她都能赢。其他情况下 Alice\rm Alice 一定赢不了，同样考虑归纳证明：假设两人都有 nn 个点，无论 Alice\rm Alice 删了哪个点，此时 Bob\rm Bob 会剩下 n−1n-1 个点，且每个点的入度最多为 n−1n-1。我们不妨只考虑入度为 n−1n-1 的点（因为对于其他点，无论 Bob\rm Bob 怎么删，都不会成为满入度的点），如果存在某个入度为 n−1n-1 的点 ii，而唯一一个没有连向 ii 的点为 jj，那么 Bob\rm Bob 一定不能删除 jj，否则 ii 就会成为满入度的点。由于 Bob\rm Bob 只有 n−1n-1 个点，因此这样的 ii 最多只有 n−1n-1 个，因此 jj 也最多只有 n−1n-1 个。那么只要删掉不是某个 jj 的点就行了。
CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...