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

· · 题解

题意：

有 2n 张牌，牌面有 n 种，对于每种牌面 n 均有两张牌。

操作者小 J 和小 I 轮流行动，每人将一张牌放在当前牌堆顶上，若此前牌堆里已有这张牌对应的另一个，则当前行动者将这两张牌和中间的所有牌收入自己的手中。

已知小 J 的手牌和每次会出什么牌，现在你是小 I，求在你先手时的一个出牌顺序使得在最小的次数内赢下小 J（即小 J 失去所有手牌）。

题解：

首先判断无解。

观察样例和打表可得，当且仅当只有一种牌两张牌时，你先出，然后没有手牌了，所以输掉，输出 -1 即可。

其他情况全部有解。

我们再来看，想要在最小次数内赢下，那只要保证小 J 无法获得新的牌，这样在 n 次操作我们后必然获胜。

因此我们只要保证，牌堆顶部对应的那张牌，必须要在自己手中，这样每次小 J 即将获得牌的前一次操作，我们就能把当前牌堆的所有牌收入囊中。

具体的，假设当前排队顶的牌为 tp，小 J 下一步要出的的牌为 x。

最后我们还要处理一个小问题，那就是初始时我们根本没有能当牌堆顶的牌，也就是在初始时我们没有重复的牌。

那此时，我们和小 J 的牌都是一个 n 的排列，那么设小 J 的牌依次为 a_1, a_2, ..., a_n，我们秩序用一个类似田忌赛马的思路依次打出 a_n, a_1, a_2, ..., a_{n - 1}，那么我们手里就有 a_1 到 a_{n - 1} 的所有牌了，小 J 手里则是两张 a_n，我们只需随意打出一张，再用另一张一样的收回来即可。

在我的维护里，一次最多往牌堆放 2 张牌，总共最多放 2n 张，因此总共最多弹出出 2n 张，时间复杂度 \mathcal{O}(n)。

细节见代码。

代码：

::::info[代码繁琐但可读性应该较高的代码]{open}

#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;
}

::::