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