luogu7915 回文 题解
分析
首先明确,字典序最小是操作序列的字典序。
只剩下最后一个数的时候,操作 1 和 2 是等价的。由于要求字典序最小,所以操作序列最后一个必定是L
。
再考虑第一个操作。因为第一次只能操作序列 \(a\) 中的第一个数或最后一个数,且最后它必将留在序列 \(b\) 的第一个位置。而回文序列 \(b\) 中最后一个数必然和第一个数相同。那么就能知道一定是枚举 \(a_1\) 和 \(a_{2n}\) 两种操作选择,再通过满足 \(a_i = a_1\) 或 \(a_i = a_{2n}\) 的位置 \(i\) 作为一个操作的临界点。
一旦确定了 \(i\),那么 \(i\) 必定是最后一个操作。我们可以将顺序的操作与倒序的操作的数相对应,满足最终得到回文串。于是考虑搜索。
建议玩一下样例。 \[ [4, 1, 2, 4, 5, 3, 1 ,2, 3, 5 ] \]
\[ [ 4, 5, 3, 1, 2, 2, 1, 3, 5, 4 ] \]
不难发现每一次只能操作两个数,左边的位置单调增,右边的位置单调减。不妨设为 \(L\) 与 \(R\)。一开始 \(L=1\),\(R=2n\)。而倒序操作也只能操作两个数,左边的位置单调减,右边的位置单调增,且一开始始终是 \(i-1\) 与 \(i+1\)。记为 \(l\) 与 \(r\)。
这里默认一开始操作的是 4。
第一步用 1 操作把 4 放到第一位,那么 \(L+1\),\(R\) 不变,此时可以操作的数为靠左的 1 与靠右的 5。这个时候要选择能与 \(a_l\) 与 \(a_r\) 对应的数,否则绝对不是回文序列。那么显然就是 \(a_r\),靠左的 5。所以要使用操作 2 加入 5,\(R-1\),\(L\) 不变。 由于 \(r\) 在 \(i\) 右边,最后一定是用 2 操作将 \(a_r\) 归位的。此时 \(a_r\) 已经不可使用,\(r+1\),\(l\) 不变。当然,要记录每个操作。
接下来是将 \(a_r\) 与 \(a_R\) 配对,\(a_l\) 与 \(a_R\) 配对。
相信大家都看出来套路了。就是择优配对,先考虑可行性,然后贪心选择。L
必须尽可能靠前,因此优先度递减排序为 \(L\) 与 \(l\)、\(L\) 与 \(r\)、\(R\) 与 \(l\)、\(R\) 与 \(r\)。
当 \(l=L\) 并且 \(r=R\) 时操作结束。
但是还有一些小边界问题。这是由于边界的增减且不能越界造成的。
- 当 \(L \le l\) 时,必须满足 \(L < l\) 才能让 \(L\) 与 \(l\) 配对,满足 \(r \le R\) 时就能让 \(L\) 与 \(r\) 配对。
- 当 \(r \le R\) 时,满足 \(L \le l\) 就能让 \(R\) 与 \(l\) 配对,必须满足 \(r < R\) 时才能让 \(R\) 与 \(r\) 配对。
由于只有能够成为回文串才贪心操作,所以第一次到达 \(l = L\) 且 \(r = R\) 时一定是字典序最小的回文串。
复杂度 \(O(Tn)\)
CODE
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int t, flag, n, a[N];
char s[N];
void dfs(int p,int l,int r,int L,int R) {
// l与r,L与R同上文
// p表示序列b中有多少个数
if(l<L&&r>R) {
flag=1;
for(int i=1;i<=2*n;++i) printf("%c",s[i]); puts("");
return;
}
if(p>n) return;
if(L<=l&&(a[l]==a[L]&&L<l||a[r]==a[L]&&r<=R)) {
s[p]='L';
if(a[l]==a[L]&&L<l) s[2*n-p+1]='L', dfs(p+1,l-1,r,L+1,R);
else s[2*n-p+1]='R', dfs(p+1,l,r+1,L+1,R);
} else if(r<=R&&(a[l]==a[R]&&L<=l||a[r]==a[R]&&r<R)) {
s[p]='R';
if(a[l]==a[R]&&L<=l) s[2*n-p+1]='L', dfs(p+1,l-1,r,L,R-1);
else s[2*n-p+1]='R', dfs(p+1,l,r+1,L,R-1);
}
}
void sol() {
flag=0;
scanf("%d",&n);
for(int i=1;i<=2*n;++i) scanf("%d",&a[i]);
s[2*n]='L'; // 一定的
for(int i=2;i<=2*n;++i) if(a[i]==a[1]) {
s[1]='L';
// 一开始用1操作位置1,对应的最后一次操作位置是i
// 顺序操作区间[2,2n]
dfs(2,i-1,i+1,2,2*n);
break;
}
if(flag) return;
for(int i=1;i<=2*n-1;++i) if(a[i]==a[2*n]) {
s[1]='R';
// 一开始用2操作位置1,对应的最后一次操作位置是i
// 顺序操作区间[1,2n-1]
dfs(2,i-1,i+1,1,2*n-1);
break;
}
if(flag) return;
puts("-1");
}
int main() {
scanf("%d",&t);
while(t--) sol();
}