【题解】P7915 [CSP-S 2021] 回文
巴菲特
2021-10-26 20:29:49
# Palin 题解
## 连续
由于取出来的数字序列 ${b}$ 是回文的，所以当 $a[p] = x$ 被取出时，序列 ${a}$ 中的 $\rm a[q] = a[p] = x$ 在何时取出其实已经确定了。依照题意，任意时刻，序列 ${a}$ 一定是开头连续的一部分和结尾连续的一部分被取出，我们设当前序列 ${a}$ 中区间 $[1, l] \bigcup [r, 2 * n] $ 中的数字已经被取出。可以保证的是这两段区间内没有重复取出的数字。容易发现，当我们已经取出了 $n$ 个数字时，$[1, n]$ 的所有数字都被取了一遍，而最终的 ${b}$ 序列以及操作串也已经确定了。每当一个数字 $a[p] = x$ 在开头或是结尾被取出时，我们将 $a[q] = a[p] = x$ 也取出。一个重要的性质是：任意时刻，所有取出的 $a[q]$ 是连续的一段。
这个东西其实也很好理解。${b}$ 结尾的一段对应了序列 ${a}$ 中间的一部分。考虑序列 ${b}$ 的后 $\rm n$ 个数一定是随着前 $\rm n$ 个数被取出的，并且为了保证回文，这后 $\rm n$ 个数一定是从后往前生成的。也就是说序列 ${b}$ 前 $\rm n$ 个数生成的连续性决定了他后 $\rm n$ 个数生成的连续性，只不过是反序。
## DP
我们设当前状态 $(l,i,j,r)$ 表示 ${a}$ 中区间 $[1, l] \bigcup [i, j] \bigcup [r, 2*n]$ 被取出，考虑接下来我们能干什么。无外乎四种情况：
* 当 $a[l+1]==a[i-1]$ 的时候，可以从开头取出 $a[l+1]$ 这个元素，同时把 $a[i-1]$ 取出；
* 当 $a[l + 1] == a[j + 1]$ 的时候，可以从开头取出 $a[l + 1]$ 这个元素，同时把 $a[j + 1]$ 取出；
* 当 $a[r-1]==a[i-1]$ 的时候，可以从结尾取出 $a[r - 1]$ 这个元素，同时把 $a[i-1]$ 取出；
* 当 $a[r-1] == a[j + 1]$ 的时候，可以从结尾取出 $a[r - 1]$ 这个元素，同时把 $a[j + 1]$ 取出。
可以使用 BFS 进行转移。准备一个队列，在一开始找到 $pos1$ 和 $pos2$ 满足 $a[1]=a[pos1],a[pos2]=a[2*n]$，依照题意要么取开头要么取结尾。初始有两种状态，取开头的 $a[1]$ 就是 $(1,pos1,pos1,2*n+1)$ ，取结尾的 $a[2*n]$ 就是 $(0, pos2, pos2, 2*n)$。接下来按照上述方式进行转移，只要队列不为空，就弹出旧状态，插入新状态。终止状态满足 $l + 1 == i \And j + 1 == r$。
由于已经取出 $n$ 个数字的时候整个操作序列已经确定了，所以让操作序列的字典序最小等价于让取出前 $n$ 个数字的操作序列最小，也即取出 $[1,l] \bigcup [r, 2*n]$ 的操作序列而不用管 $[i,j]$ 是怎么取的。所以我们总是优先地考虑取出 $a[l + 1]$。 那么，一旦我们找到一个终止状态，便可以保证是字典序最小的，结束转移，直接输出即可。如果搜空了队列都没有到达终止状态，那么无解。
以上是考场上的我两个小时瞪眼的结果。
## ~~DP~~ 贪心
考虑上述 $4$ 中转移最多只有两种是可行的，因为不可能出现 $a[i-1]$ 同时和 $a[l+1]、a[r - 1]$ 相等，或是 $a[j + 1]$ 同时和 $a[l+1]、a[r - 1]$ 相等。故 DP 的时间复杂度上限是 $O(2^n)$，相当于我两个小时写了一个爆搜。当时我对这个程序的认识是：“时间复杂度一定很难跑满，并且策略是正确的，可以找到解” ，也就没往下想。但是事实上这个题是线性的贪心，接下来证明在上述 $4$ 种转移中只需要选择一种就能得到正确的操作序列。
当抉择分支出现时，也就是一种状态可以转移到两种新状态时，一共有如下两种情况：
* $a[l + 1] == a[i - 1] \And a[j + 1] == a[r - 1]$
* $a[l + 1] == a[j + 1] \And a[i - 1] == a[r - 1]$
这里我们以第一种情况为例进行讨论，第二种同理。我们只进行开头 $a[l + 1]$ 的转移，而暂且不管 $a[r - 1]$，那么状态变为 $(l + 1, i - 1, j, r)$。接下来假如出现 $a[l + 2] == a[i - 2]$ ，那么我们依旧进行开头的转移而不管，这样下去，直到开头不能取出，设此时的状态是 $(l+k,i-k,j,r)$。这个时候我们急不可耐地取出结尾，状态变为 $(l+k,i-k,j+1,r-1)$。考虑这个过程，我们的操作序列是 $L...LR$，是所有能得到状态 $(l+k,i-k,j+1,r-1)$ 里面字典序最小的一个。
也就是说如果在一开始我们就进行结尾的转移得到 $(l+1,i-1,j+1,r-1)$，然后再进行后续的操作，最终的操作序列是 $LRL...$，而现在我们已经找到了一个更优秀的替代品 $L...LR$ 同样也能够得到最终的状态，那么结尾的转移便是完全无用的了。贪心得证。当且仅当开头无法转移时，我们才进行结尾的转移。
这就是一个大贪心，时间复杂度 $O(n)$。（虽然但是，我考场上并没有想出来，而是拿剩下的 30min 写了一个 T2 的爆搜并最终取得了 0 分的好成绩。
实现起来也很简单，队列的部分不用变，一旦我们找到一个合法转移，continue 掉就好了，这样可以保证线性。
## 输出
接下来考虑如何输出操作序列。我是开了一个结构体：
```cpp
struct Op{
int l, r, i, j, tp1, tp2, pre;
}P[10000010];
```
$\rm P$ 相当于一个内存池。$\rm l, \rm r, \rm i, \rm j$ 无需多说，$\rm tp1$ 和 $\rm tp2$ 代表从上一个状态转移过来时的操作，$tp1 = 1/2$ 代表取出了 $a[l]$ 还是 $a[r]$，$tp2 = 1/2$ 代表取出了 $a[i]$ 还是 $a[j]$。$pre$ 记录上一个状态在内存池中的位置，用于最后的输出。注意是先输出 $\rm n$ 个 $tp1$，再输出 $\rm n$ 个 $tp2$，二者的输出顺序是相反的。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int rd(){
int res(0), fl(1);
char c=getchar();
while(!isdigit(c)){ if(c=='-') fl=-1; c=getchar();}
while(isdigit(c)){ res=(res<<3)+(res<<1)+c-'0'; c=getchar();}
return res*fl;
}
const int maxn = 1000010;
int t, n, a[maxn], b[maxn], pos1, pos2, Flg, top, N, ans1[maxn], ans2[maxn], cnt1, cnt2;
struct Op{
int l, r, i, j, tp1, tp2, pre;
}P[10000010];
int Q[10000010], hd, tl;
void prnt(int op){
ans1[++cnt1] = P[op].tp1; ans2[++cnt2] = P[op].tp2;
if(P[op].pre) prnt(P[op].pre);
return;
}
void Prnt(int op){
cnt1=0, cnt2=0, Flg=1;
prnt(op);
for(int i(cnt1); i >= 1; --i) if(ans1[i] == 1) printf("L"); else printf("R");
for(int i(1); i <= cnt2; ++i) if(ans2[i] == 1) printf("L"); else printf("R");
printf("\n");
return;
}
int main(){
t = rd();
for(;t--;){
top=0, Flg=0; memset(ans1, 0, sizeof(int)*n); memset(ans2, 0, sizeof(int)*n);
n = rd(); N = n * 2;
for(int i(1); i <= N; ++i) a[i]=rd();
for(int i(2); i <= N; ++i) if(a[i] == a[1]){ pos1 = i; break; }
for(int i(1); i < N; ++i) if(a[i] == a[N]){ pos2 = i; break; }
tl = 0, hd = 1;
P[++top] = Op{1, N+1, pos1, pos1, 1, 1, 0}; Q[++tl] = 1;
P[++top] = Op{0, N, pos2, pos2, 2, 1, 0}; Q[++tl] = 2;
while(hd <= tl){
int op = Q[hd++];
if(P[op].l + 1 == P[op].i && P[op].j + 1 == P[op].r){
Prnt(op); break;
}
if(P[op].l + 1 < P[op].i - 1 && a[P[op].l + 1] == a[P[op].i - 1]){
P[++top] = Op{P[op].l + 1, P[op].r, P[op].i - 1, P[op].j, 1, 1, op};
Q[++tl] = top; continue;
}
if(P[op].l + 1 < P[op].i && P[op].j + 1 < P[op].r && a[P[op].l + 1] == a[P[op].j + 1]){
P[++top] = Op{P[op].l + 1, P[op].r, P[op].i, P[op].j + 1, 1, 2, op};
Q[++tl] = top; continue;
}
if(P[op].i - 1 > P[op].l && P[op].r - 1 > P[op].j && a[P[op].i - 1] == a[P[op].r - 1]){
P[++top] = Op{P[op].l, P[op].r - 1, P[op].i - 1, P[op].j, 2, 1, op};
Q[++tl] = top; continue;
}
if(P[op].j + 1 < P[op].r - 1 && a[P[op].j + 1] == a[P[op].r - 1]){
P[++top] = Op{P[op].l, P[op].r - 1, P[op].i, P[op].j + 1, 2, 2, op};
Q[++tl] = top; continue;
}
}
if(!Flg) printf("-1\n");
}
return 0;
}
```