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

naughty-naught / 2024-10-15 / 原文

Problem Link

[THUPC 2023 初赛] 速战速决

题目描述

题意清晰，不再过多赘述。

Solution

每张不同的卡是等效的。

小 $J$ 手上的卡牌只有 $2$ 种情况：手上没有相同的牌和有相同的牌。

情况 $1$：

小 $J$ 手上的牌等价于 $1 \sim n$（但其实没用），令其手上的牌为 $b_1, b_2,\ldots,b_n$。

由于要“速战速决”，所以尽量让 $J$ 少拿牌（这个在情况 $2$ 中也适用），那么如何让 $J$ 少拿牌呢？

因为手牌为排列，所以 $I$ 手上每张牌 $J$ 都有一张复制，同理 $J$ 上每张牌 $I$ 中也有一张复制。

前者的说法是因为 $I$ 先手，垫下去的第一张牌一定会被 $J$ 回收；后者是因为，只要第一张牌不被 $J$ 回收，我们可以视为少 $1$ 张牌+$J$ 先手，如此除了放的第一张牌其他所有牌都能回收。

那么我们放的第一张牌就很显然了，即 $b_n$，之后 $J$ 每打一张牌，我们跟同一张，即可在 $n$ 次后使得 $J$ 手牌中是两张 $b_n$，其他所有牌在 $I$ 手上，此时轮到 $I$ 先手，随便放一张牌 $x$，待 $J$ 打出 $b_n$ 后再打出一张 $x$，$J$ 出完一张 $b_n$ 后就会因无牌而败了。

综上，操作次数为 $n+2$，操作序列为 $b_n, b_1, b_2,\ldots, b_{n-1}, b_1, b_1$。

情况 $2$：

假设 $J$ 将打出第 $i$ 张牌和第 $i+1$ 牌：

$b_i$ 是一张单牌（即另一张牌 $x = b_i$ 在 $I$ 手上）：打出 $x$ 将其收回即可。
$b_i$ 不是一张单牌但另一张牌 $x = b_i$ 不是下一张被打出的牌：学习情况 $1$ 中的策略，只要保证 $b_i$ 的收回只能收 $2$ 张即可。
$b_i$ 不是一张单牌且 $b_{i+1} = b_i$：在 $J$ 下次打出 $b_i$ 前提前垫一张不是单牌 $x$，在其打出 $b_i$ 后打出另一张 $x$ 将 $b_i$ 回收即可。

操作 $1$ 等价于操作 $1$ 次得 $1$ 张牌，操作 $2$ 等价于操作 $2$ 次得 $2$ 张牌，操作 $3$ 等价于操作 $2$ 次得 $2$ 张牌，总共要从 $J$ 处获得 $n-1$ 张牌，所以要操作 $n-1$ 次，算上第一次先手垫的 $1$ 张牌，总操作数为 $n$ 次。

代码实现就显然了。

代码

//written by Naught
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define Maxn 300005
#define fo(i, l, r) for (int i = l; i <= r; ++i)
#define fr(i, r, l) for (int i = l; i >= r; --i)
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read(int x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}

int n, b[Maxn], cnt[Maxn], lst, ind[Maxn], s[Maxn], top, ans[Maxn];
queue<int> q;

void push(int x) {ind[s[++top] = x] = 1;}

void pop(int x)
{
    while(s[top] != x) ++cnt[s[top]], ind[s[top]] = 0, q.push(s[top--]);
    ++cnt[x], ind[x] = 0, q.push(x), --top;
}

int main()
{
    n = read();
    if(n == 1) return puts("-1"), 0;
    fo(i, 1, n) cnt[i] = 2;
    fo(i, 1, n) b[i] = read(), --cnt[b[i]];
    fr(i, 1, n) if(cnt[i] == 2) {lst = i; break;}
    fr(i, 1, n) fr(j, 1, cnt[i]-(lst == i)) q.push(i);

    if(lst == 0)
    {
        printf("%d\n%d ", n+2, b[n]);
        fo(i, 1, n-1) printf("%d ", b[i]);
        printf("%d %d", b[1], b[1]);
        return 0;
    }

    push(ans[0] = lst), --cnt[ans[0]];
    fo(i, 1, n-1)
    {
        push(b[i]);
        if(cnt[b[i+1]] || ind[b[i+1]]) pop(ans[i] = s[1]);
        else
        {
            if(q.front() == s[1]) q.push(s[1]), q.pop();
            if(ind[ans[i] = q.front()]) pop(ans[i]);
            else push(ans[i]), --cnt[ans[i]], q.pop();
        }
    }

    printf("%d\n", n);
    fo(i, 0, n-1) printf("%d ", ans[i]);

    return 0;
}