题解：速战速决

进入博客食用更香！

一道贪心题。

无解

很明显的，当 $n=1$ 时，因为小I先手，小J可以直接收牌，所以小I无法获胜。

策略

Case 1 小 I 手上没有任何能配对的牌

也就是说对于每一对牌总有一张在小I的手上。

此时我们应该先打出对面出牌序列中最后一张牌，随后对面出什么牌我们就跟着出什么牌，确保小J出的牌能被我们立刻收掉。

最后对面出他的最后一张牌把我们出的第一张牌收掉，此时我们手上的牌全是成对的，对方只有一对牌。随便出一张手上的牌把对面的一张牌收掉，对面下次出牌就必输。

Case 2 小 I 贪心每一回合

此时我们手中必有一对牌。我们能用这对牌来干嘛呢？一开始我们埋下这张牌作为保险，如果后面对面想收牌（牌堆里的或是我手上的），我们就打出这对牌的另一张把整个牌堆清空。

我们可以像 $\text{Case 1}$ 一样，对面出牌我们紧跟着收牌 ，考虑以下几种情况（以下 $A_i$ 指我们出的编号为 $i$ 的牌，$B_i$ 指对面出的编号为 $i$ 的牌，$[\cdot\cdot\cdot]$ 表示当前时刻之后的假设情况）：

• $A_?…B_i[…A_i]$ 以及 $A_?…B_i[…B_i]$ 这两种情况都会对我们的策略造成威胁，因此在这个时候应该立即收掉所有牌。

• $A_i…A_iB_j[…]$ 这种情况会使我们误收场上所有牌，导致对方出的 $B_j$ 要么收不掉（这意味着我们要花额外的步数去收这张牌）或是对面会在后面某一时刻清场（这意味着我们要么输，要么步数更多）。

• 其余情况按正常的成对出牌。

基于以上几点对方就不能在任何时刻收牌，因为我们要么快人一步把前面的收了要么把他出的第一张牌直接收了，而此时也会达到步数最小值，不难发现这个步数最小值是 $n$ 。

* 蒟蒻个人理解，可能有些问题欢迎大家指出！

码

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

const int MAXN = 300010;

int n;
int s[2*MAXN], top, cnts[MAXN];
int mine[MAXN];
int a[MAXN];
queue<int> q;

void pop(int x) {  // 清理公共牌堆
    while (s[top] != x) {
        cnts[s[top]]--;
        mine[s[top]]++;
        q.push(s[top]);
        top--;
    }
    cnts[s[top]]--;
    mine[s[top]]++;
    q.push(s[top]);
    top--;
}

void push(int x) {  // 打牌
    s[++top] = x;
    cnts[x]++;
}

int main() {
    scanf("%d", &n);
    if (n == 1) return printf("-1")&0;  // 无解
    for (int i = 1; i <= n; i++) {
        mine[i] = 2;
    }
    int st = -1;
    for (int i = 1; i <= n; i++) {
        scanf("%d", a+i);
        mine[a[i]]--;
    }
    for (int i = 1; i <= n && st == -1; i++) if (mine[i] == 2) st = i;
    for (int i = 1; i <= n; i++) {
        for (int j = mine[i]-(i==st); j >= 1; j--) q.push(i);
    }

    if (st == -1) {  // 没有成对的牌
        printf("%d\n%d", n+2, a[n]);
        for (int i = 1; i < n; i++) printf(" %d", a[i]);
        printf(" %d %d", a[1], a[1]);
        return 0;
    }

    printf("%d\n%d", n, st);
    mine[st]--;
    push(st);
    push(a[1]);
    for (int i = 2; i <= n; i++) {
        int x = a[i];
        if (mine[x] || cnts[x]) {  // 有威胁。清空牌堆
            printf(" %d", s[1]);
            pop(s[1]);
        } else {
            if (q.front() == s[1]) {  // 会误收牌堆
                q.push(q.front());  // 将队首移到队尾
                q.pop();
            }
            int nxt = q.front();
            printf(" %d", nxt);
            if (cnts[nxt]) {
                pop(nxt);
            } else {
                push(nxt);
                mine[nxt]--;
                q.pop();
            }
        }
        push(x);
    }
}