专栏文章

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

CCoffee_zzz/xin
P11604题解参与者 4已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@miqdr4me
此快照首次捕获于
2025/12/04 03:08
3 个月前
此快照最后确认于
2025/12/04 03:08
3 个月前
查看原文
这题真的好难好难啊！
首先考虑 A 什么时候赢。
如果存在一个不大于 nn 的正整数 ii，满足 B 的 ii 会输给 A 的 1∼n1\sim n 的所有数，那么显然 A 把 B 的 ii 留下即可做到胜利。
否则，对于任意不大于 nn 的正整数 ii，都满足存在至少一个不大于 nn 的正整数 jj，使得 B 的 ii 不输 A 的 jj。
这时，我们考虑一个极端情况：现存在一个长度为 nn 的序列 vv，B 的每个 ii 都只不输 viv_i，即会输给 1∼vi−11\sim v_i-1 和 vi+1∼nv_i+1 \sim n。
我们考虑一个可重集合 SS，维护当前剩余的 viv_i。在 A 把 B 的 ii 弃掉后，B 只需要把 viv_i 从 SS 中删掉，并选择一个不在 SS 中且还未被弃掉的 jj，把 A 的 jj 弃掉即可。这样，在操作结束后，A 剩下的牌一定在 SS 中，即 B 剩下的牌不输给 A 剩下的牌。
由于在 B 操作时，不在 SS 中的数的数量一定不小于当前轮数，所以一定可以找到满足条件的 jj，这样的构造是合法的。
既然极端情况 B 都可以做到不输，而其他情况显然严格弱于极端情况，所以只要不满足「存在一个不大于 nn 的正整数 ii，满足 B 的 ii 会输给 A 的 1∼n1\sim n 的所有数」，那么 B 一定不输，即「存在一个不大于 nn 的正整数 ii，满足 B 的 ii 会输给 A 的 1∼n1\sim n 的所有数」是 A 赢的条件。
接下来考虑 B 什么时候赢。
如果存在一个不大于 nn 的正整数 ii，满足 B 的 ii 不赢 A 的 1∼n1\sim n 的所有数，那么显然 A 把 B 的 ii 留下即可做到不输。
否则，对于任意不大于 nn 的正整数 ii，都满足存在至少一个不大于 nn 的正整数 jj，使得 B 的 ii 赢 A 的 jj，那么我们还是可以考虑一个序列 vv，满足 B 的每个 ii 赢 A 的 viv_i，并考虑一个可重集合 SS，维护当前剩余的 viv_i。
在 A 把 B 的 ii 弃掉后，B 只需要把 viv_i 从 SS 中删掉，并选择一个不在 SS 中且还未被弃掉的 jj，把 A 的 jj 弃掉即可。这样，在操作结束后，A 剩下的牌一定在 SS 中，即 B 剩下的牌会赢 A 剩下的牌。
由于在 B 操作时，不在 SS 中的数的数量一定不小于当前轮数，所以一定可以找到满足条件的 jj，这样的构造是合法的。
于是，我们可以得到，只要不满足「对于任意不大于 nn 的正整数 ii，都满足存在至少一个不大于 nn 的正整数 jj，使得 B 的 ii 赢 A 的 jj」，那么 A 一定不输，即「对于任意不大于 nn 的正整数 ii，都满足存在至少一个不大于 nn 的正整数 jj，使得 B 的 ii 赢 A 的 jj」是 B 赢的条件。
最后，如果 A 和 B 都无法获胜，那么他们只能做到不输，即平局。
代码还挺好写的。
CPP
#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;
}

评论

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

正在加载评论...