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

Yikuwa · 2023-03-07 23:30:37 · 题解

我们将小 I 的初始手牌分为两种情况：手中有两张相同的牌或没有。

容易发现后者等价于小 I 手中的牌为一个 1 到 n 的排列，这种情况下由于小 I 打出的第一张牌的另一半一定在小 J 手上，所以小 J 至少能够收回一次牌。

我们猜测小 I 存在一种方法能够使得小 J 只收回一次牌且收回牌数为 2，构造简单：

题目给出小 J 的出牌顺序 :a_1,a_2,a_3,...a_n,a_n,a_n

小 I 的出牌方法 :a_n,a_1,a_2,a_3,...,a_{n-1},a_1,a_1

解释：先打 a_n，之后 n-1 轮打小 J 上一轮打出的牌，这样 n 轮之后小 J 手上只剩两张 a_n，小 I 连着打两张相同的牌即可。

这样我们就做完了初始手牌为排列的情况。

接下来处理小 I 手中存在两张相同的牌的情况，设小 I 初始手中有两张编号为 k 的牌。

我们考虑先打其中一张 k，接下来时刻保持小 I 手中存在一张牌与牌堆底部的牌编号相同，这样的好处就是我们可以在每一次小 J 可能收牌前把牌堆抽完，保证小 J 收不到牌，从而在 n 轮交换后结束游戏。

考虑如何维护，不妨设当前牌堆底部牌为 x，小 I 手中有另一张 x，小 J 下一张要打的牌为 y。

分情况讨论：

另一张 y 在牌堆中，此时如果不及时将牌堆中的 y 收回，下一轮小 J 打出的 y 就能形成收牌操作，所以此时小 I 打出 x 清空牌堆，将牌堆中的 y 收在手上，同时保证了下一回合小 J 打出 y 后新牌堆顶 y 的另一张在小 I 手中。
另一张 y 在小 I 手上，这种情况其实可收可不收，但是为了方便，我们同第一种情况打出 x 收回整个牌堆，同样保证新牌堆顶 y 的另一张在小 I 手中。
另一张 y 在小 J 手上，此时小 I 随便打一张牌就可以了，但是注意不能把手中与牌堆顶相同的那张牌打出去。

至此，我们已经做完了这道题，具体在代码中，我们需要维护牌堆和记录每个牌的位置（是否在小 I 手中和是否在牌堆中），为了方便处理可以维护小 I 的手牌。写起来有些细节。

#include<bits/stdc++.h>
#define reg register
#define IL inline
using namespace std;
//#define getchar() (_S==_T&&(_T=(_S=_B)+fread(_B,1,1<<15,stdin),_S==_T)?EOF:*_S++)
char _C,_B[1<<15],*_S=_B,*_T=_B;
IL int read(){
    reg int x=0,y=1;
    for(_C=getchar();!isdigit(_C);_C=getchar())if(_C=='-')y=-1;
    for(;isdigit(_C);_C=getchar())x=(x<<1)+(x<<3)+(_C^48);
    return x*y;
}
const int N=3e5+7;
int n,cnt[N],a[N],in[N],s[N],top,Ans[N];
queue<int>q;
IL void Push(reg int x){in[s[++top]=x]=1;}
IL void Pop(reg int x){
    while(s[top]!=x)++cnt[s[top]],in[s[top]]=0,q.push(s[top--]);
    ++cnt[x],in[x]=0,q.push(x),--top;
}

IL int work(){
    printf("%d\n%d ",n+2,a[n]);
    for(reg int i=1;i<n;++i)printf("%d ",a[i]);
    printf("%d %d",a[1],a[1]);
    return 0;
}

signed main(){
    for(reg int i=n=read();i;--i)cnt[i]=2;
    if(n==1)return !puts("-1");
    for(reg int i=1;i<=n;++i)--cnt[a[i]=read()];
    reg int Start=0;
    for(reg int i=n;i&&!Start;--i)if(cnt[i]==2)Start=i;
    for(reg int i=n;i;--i)for(reg int j=cnt[i]-(Start==i);j;--j)q.push(i);

    if(!Start)return work();

    Push(Ans[0]=Start),--cnt[Ans[0]];
    for(reg int i=1;i<n;++i){
        Push(a[i]);
        if(cnt[a[i+1]]||in[a[i+1]]){
            Pop(Ans[i]=s[1]);
        }
        else{
            q.front()==s[1]?q.push(s[1]),q.pop():void();
            if(in[Ans[i]=q.front()]){
                Pop(Ans[i]);
            }
            else{
                Push(Ans[i]),--cnt[Ans[i]];
                q.pop();
            }
        }
    }
    printf("%d\n",n);
    for(reg int i=0;i<n;++i)printf("%d ",Ans[i]);
    return 0;
}

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

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