[CSP-S 2021] 回文 题解

郑朝曦zzx · 2022-06-05 12:03:51 · 题解

一 关于今年的这道 T3

• 比想象中的简单（可我不看题解依然不会，我太弱了）
• 和 T2 差不多吧，甚至更难一些（T2就是个套路区间动规）
• 涉及的算法只有普及难度，但思维含量还是有的。

二 解题思路

part1 暴力

没啥好说的暴力枚举每次是 L 还是 R 再判一下是否回文。

时间复杂度：O(2^n\times n)

期望得分：28pts

part2 区间动态规划

也是套路，小区间被大区间包含。

时间复杂度：O(n^2)

期望得分：60pts

part3 正解：双向队列

您看到了正解所需的算法时可能和我当初看题解时的心情一样，怎么这么简单！

我们来分析一下这道题目是如何被转化为双向队列的：

由于第一个取左边和取右边的思路相似，此处只分析取左边的情况：

1. 第一步：找到唯一的位置 x，使得 a_1 = a_x。

• 举例：再样例一中，x = 4。

2. 第二步：我们可以把这个数列分成两个部分：2\sim x-1 和 x + 1 \sim 2n。

为了方便说明，我们设第一个队列为 P，第二个为 Q。

• 举例：样例一就被分成两截：

  P:1 2
  Q:5 3 1 2 3 5

  3. 第三步重复以下操作纸质两个队列均为空：

分类讨论（重点）第 i 次取有一下几种情况：

注： 此处解释一下：ans_{2(n - 1) - i + 1} 是指倒数第 i 次操作。

你需要输出所有方案对应的字符串中字典序最小的一个。

情况 1 和情况 4 是有可能同时出现的，情况 2 和情况 3 可能同时出现，故需要按照一定的顺序枚举四种情况，即 1 在 4 前，2 在 3 前。

说着有点绕，强烈建议大家画图理解，而不仅仅是复制代码，毕竟真题挺珍贵的。

三 代码

说了这么多，上代码吧：

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 500010;
int t, n, l, r;
int a[maxn << 1];
char ans[maxn << 1];
bool solve(int l1, int r1, int l2, int r2)
{
    for (int i = 1; i < n; ++i)
    {
        if (l1 < r1 && a[l1] == a[r1])
        {
            ans[i] = 'L'; l1++;
            ans[2 * (n - 1) - i + 1] = 'L'; --r1;
        }
        else if (l1 <= r1 &&l2 <= r2 && a[l1] == a[l2])
        {
            ans[i] = 'L'; ++l1;
            ans[2 * (n - 1) - i + 1] = 'R'; ++l2;
        }
        else if (l2 <= r2 && l1 <= r1 && a[r2] == a[r1])
        {
            ans[i] = 'R'; --r2;
            ans[2 * (n - 1) - i + 1] = 'L'; --r1;
        }
        else if (l2 < r2 && a[l2] == a[r2])
        {
            ans[i] = 'R'; ++l2;
            ans[2 * (n - 1) - i + 1] = 'R'; --r2;
        }
        else return 0;
    }
    return 1;
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        int x1, x2;
        scanf("%d", &n);
        for (int i = 1; i <= 2 * n; ++i)
            scanf("%d", &a[i]);
        memset(ans, '\0', sizeof(ans));
        for (int i = 2; i <= 2 * n; ++i)
            if (a[1] == a[i]) {x1 = i; break;}
        for (int i = 2; i < 2 * n; ++i)
            if (a[2 * n] == a[i]) { x2 = i; break;}
        if (solve(2, x1 - 1, x1 + 1, 2 * n))
            printf("L%sL\n", ans + 1);
        else if(solve(1, x2 - 1, x2 + 1, 2 * n - 1))
            printf("R%sL\n", ans + 1);
        else printf("-1\n");
    }   
    return 0;
}