专栏文章

题解：P9137 [THUPC 2023 初赛] 速战速决

YYangXiaopei
P9137题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minaeiv3
此快照首次捕获于
2025/12/01 23:11
3 个月前
此快照最后确认于
2025/12/01 23:11
3 个月前
查看原文

题意：

有 2n2n 张牌，牌面有 nn 种，对于每种牌面 nn 均有两张牌。
操作者小 J 和小 I 轮流行动，每人将一张牌放在当前牌堆顶上，若此前牌堆里已有这张牌对应的另一个，则当前行动者将这两张牌和中间的所有牌收入自己的手中。
已知小 J 的手牌和每次会出什么牌，现在你是小 I，求在你先手时的一个出牌顺序使得在最小的次数内赢下小 J（即小 J 失去所有手牌）。

题解：

首先判断无解。
观察样例和打表可得，当且仅当只有一种牌两张牌时，你先出，然后没有手牌了，所以输掉，输出 −1-1 即可。
其他情况全部有解。
我们再来看，想要在最小次数内赢下，那只要保证小 J 无法获得新的牌，这样在 nn 次操作我们后必然获胜。
因此我们只要保证，牌堆顶部对应的那张牌，必须要在自己手中，这样每次小 J 即将获得牌的前一次操作，我们就能把当前牌堆的所有牌收入囊中。
具体的，假设当前排队顶的牌为 tptp，小 J 下一步要出的的牌为 xx。
  • 另一张 xx 在牌堆里，这是我们为了不让小 J 拿到牌，必须要在我们这一步把牌堆收完，打出 tptp，那么接下来的牌堆顶 tptp 就要变成 xx，而此时另一张 xx 已经被我们收下了，正好满足。
  • 另一张 xx 在我们手里，在这种情况下收还是不收都行。
  • 另一张 xx 在小 J 手里，这种情况下就一定不能收掉了，我们只需随意打出一个在我们手里不是 tptp 的牌即可。
最后我们还要处理一个小问题，那就是初始时我们根本没有能当牌堆顶的牌，也就是在初始时我们没有重复的牌。
那此时，我们和小 J 的牌都是一个 nn 的排列，那么设小 J 的牌依次为 a1,a2,...,ana_1, a_2, ..., a_n，我们秩序用一个类似田忌赛马的思路依次打出 an,a1,a2,...,an−1a_n, a_1, a_2, ..., a_{n - 1}，那么我们手里就有 a1a_1 到 an−1a_{n - 1} 的所有牌了，小 J 手里则是两张 ana_n，我们只需随意打出一张，再用另一张一样的收回来即可。
在我的维护里，一次最多往牌堆放 22 张牌，总共最多放 2n2n 张，因此总共最多弹出出 2n2n 张，时间复杂度 O(n)\mathcal{O}(n)。
细节见代码。

代码：

代码繁琐但可读性应该较高的代码CPP
#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int n, tp, a[300005], f[300005], pos[600005];//f表示每种牌我有几个，pos表示每张牌在谁那pos[i]=pos[i+n]=1/2/3，其中1表示在牌堆，2表示在我们手里，3表示在小J手里
queue<int> q;//我手里的牌
stack<int> st;//排堆里的牌，用栈维护
vector<int> ans;//答案序列
signed main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		f[a[i]]--, f[i] += 2;//记录每种牌我有几个
		if(pos[a[i]])//把a[i]号牌标记一张为小J的
			pos[a[i] + n] = 3;
		else
			pos[a[i]] = 3;
	}
	for(int i = 1; i <= n; i++){
		if(f[i] >= 2)//i号牌我有2个，记录为tp
			tp = i;
	}
	for(int i = 1; i <= n; i++){
		if(f[i] == 1 || i == tp)//把i号牌标记一张为我的，或者i号牌为tp，我最开始就要打出一张，先记录下来
			pos[i + n] = 2, q.push(i);
		else if(f[i] == 2)//把i号牌全标记为我的
			pos[i] = pos[i + n] = 2, q.push(i), q.push(i);
	}
	if(n == 1){//无解
		cout << -1;
		return 0;
	}
	else if(!tp){//没有重复的牌在一人手里
		cout << n + 2 << "\n" << a[n] << " ";
		for(int i = 2; i <= n; i++)
			cout << a[i - 1] << " ";
		cout << a[1] << " " << a[1];
		return 0;
	}
	else{
		ans.push_back(tp), st.push(tp);//我要先打出tp
		if(pos[tp] == 2)//更新牌在谁那的记录
			pos[tp] = 1;
		else
			pos[tp + n] = 1;
		st.push(a[1]);//牌堆里放入小J的第一张牌，因为tp号牌初始都在我的手里，所以第一张牌小J注定不会收掉
		if(pos[a[1]] == 3)
			pos[a[1]] = 1;
		else
			pos[a[1] + n] = 1;
		for(int i = 2; i <= n; i++){
			int x = a[i];//小J下一张要打的
			if(pos[x] == 1 || pos[x + n] == 1 || pos[x] == 2 || pos[x + n] == 2){//下一张牌的另一张在牌堆里或者在我手里
				ans.push_back(tp);//打出tp
				while(!st.empty()){//把牌堆里的所有牌全部收下。
					q.push(st.top());
					if(pos[st.top()] != 1)
						pos[st.top()] = 2;
					else
						pos[st.top() + n] = 2;
					st.pop();
				}
				tp = x, st.push(x);//更新tp，对方打出x
				if(pos[x] == 3)
					pos[x] = 1;
				else
					pos[x + n] = 1;
			}
			else{
				while(q.front() == tp)
					q.pop(), q.push(tp);
				int t = q.front();//找一张不是牌堆顶的牌，定然存在，因此上面的while最多循环一次跳掉一个tp
				q.pop();
				ans.push_back(t), st.push(t);
				if(pos[t] == 2)
					pos[t] = 1;
				else
					pos[t + n] = 1;
				st.push(x);
				if(pos[x] == 3)
					pos[x] = 1;
				else
					pos[x + n] = 1;
			}
		}
		cout << ans.size() << "\n";//输出
		for(auto i : ans){
			cout << i << " ";
		}
		return 0;
	}
	return 0;
}

评论

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

正在加载评论...