2021 CSP 题解
T3 回文
本题的数据偏大,只能用 $O(n)$ 或 $O(nlogn)$ 的算法。
同时,本题要求最小字典序,这提醒了我们往贪心这一方面想。
因为答案要的是 回文串,可见对于任意一个字符,若它 第一个 取出,则另一个值相等的字符要 最后取。
根据要 最后取 的字符做 分割线,将这一串数字被分成了两部分($A$ 和 $B$),靠左的只能往左取、靠右的往右。
最后就是顺序问题了,因为最终要形成 回文串,这启发我们定义两个指针,从两端往中间搜。
贪心
若 $A$ 队头 等于 $A$ 队尾,因为 $A$ 队队尾后没有 $A$ 队元素,不会产生影响,所以 可以取出。
若 $B$ 队头 等于 $B$ 队尾,因为 $B$ 队队尾后没有 $B$ 队元素,不会产生影响,所以 可以取出。
若 $A$ 队头 等于 $A$ 队中的元素,因为 $A$ 队中此元素为 局部最晚弹出,其后元素只能往右弹,但右边有分割线,无法也最好不这么弹,所以 不能取出。
若 $B$ 队头 等于 $B$ 队中的元素,因为 $B$ 队中此元素为 局部最晚弹出,其后元素只能往左弹,但左边有分割线,无法弹出,所以 不能取出。
若 $A$ 队头 等于 $B$ 队尾,因为 $B$ 队队尾后没有 $B$ 队元素,不会产生影响,所以 可以取出。
若 $B$ 队头 等于 $A$ 队尾,因为 $A$ 队队尾后没有 $A$ 队元素,不会产生影响,所以 可以取出。
若 $A$ 队头 等于 $B$ 队中的元素,因为 $B$ 队中此元素为 局部最晚弹出,其后元素只能往左弹,但左边有分割线,无法弹出,所以 不能取出。
若 $B$ 队头 等于 $A$ 队中的元素,因为 $A$ 队中此元素为 局部最晚弹出,其后元素只能往右弹,但右边有分割线,无法也最好不这么弹,所以 不能取出。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int T, n;
int a[N], b[N];
int Al, Ar, Bl, Br;
char ans[N];
bool F1, F2;
deque<int> A, B;
void print()
{
for (int i = 1; i <= 2 * n; i ++ ) printf("%c", ans[i]);
puts("");
}
int find(int x)
{
for (int i = 2; i <= 2 * n; i ++ )
if (a[i] == x)
{
return i;
}
}
void build(bool op, int S, int E)
{
A.clear(), B.clear();
if(!op) Al = 1, Ar = E, Bl = E + 1, Br = 2 * n;
if (op) Al = 1, Ar = S, Bl = S + 1, Br = 2 * n;
for (int i = Al; i <= Ar; i ++ ) A.push_back(a[i]);
for (int i = Bl; i <= Br; i ++ ) B.push_back(a[i]);
}
bool work()
{
int L = 1, R = n * 2;
while (A.size() || B.size())
{
// 两个元素都在 A 栈里, 其中一个在队首, 出栈操作为 'L'
// 另一个元素会是此栈中最晚出栈的, 因为A栈原队尾是全局最晚出栈的
// 所以最好也只能选 'L'
if (A.size() >= 2 && A.front() == A.back())
{
A.pop_front(), A.pop_back();
ans[L] = 'L', ans[R] = 'L';
L ++, R --;
}
else if (A.size() && B.size() && A.front() == B.front())
{
A.pop_front(), B.pop_front();
ans[L] = 'L', ans[R] = 'R';
L ++, R --;
}
// 两个元素都在 B 栈里, 其中一个在 B 栈队尾, 出栈操作为 'R'
// 另一个元素会是当前栈中最晚出栈的, 因为A栈原队尾是全局最晚出栈的
// 所以只能选 'R'
else if (B.size() >= 2 && B.front() == B.back())
{
B.pop_front(), B.pop_back();
ans[L] = 'R', ans[R] = 'R';
L ++, R --;
}
else if (A.size() && B.size() && A.back() == B.back())
{
A.pop_back(), B.pop_back();
ans[L] = 'R', ans[R] = 'L';
L ++, R --;
}
else return false;
}
print();
return true;
}
int main()
{
scanf("%d", &T);
while (T -- )
{
scanf("%d", &n);
for (int i = 1; i <= 2 * n; i ++ ) scanf("%d", &a[i]);
F1 = false, F2 = false;
int Ls = 1;
int Le = find(a[Ls]);
strcpy(ans, "");
build(0, Ls, Le);
if (work()) continue;
int Re = 2 * n;
int Rs = find(a[Re]);
strcpy(ans, "");
build(1, Rs, Re);
if (work()) continue;
puts("-1");
}
return 0;
}