2021 回文 · 方案一环形配对逆向

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 4229 字
环形配对逐对逆向构造，O(n^2) 直白版
2021
贪心
正文

// CSP-S 2021 复赛 T3 · 回文（方案一：环形配对逆向构造，O(n^2) 直白版）
// 原题：https://oj.yecheng.tv/p/CSPS2021C
// 题意：双端队列里 2n 个数（1..n 各两个），每次从头/尾取一个接到新
//       串尾，使新串为回文；输出字典序最小的操作串（L 取头 / R 取尾）。
// 思路（逆向逐对构造）：
//   取出序列 t_1..t_{2n} 是回文 ⟺ t_i = t_{2n+1-i}。于是"第 i 次"
//   与"第 2n+1-i 次"取的是同一个值的两副本。从外向内构造：
//   1. 枚举首步 L / R：取出的 x 的另一副本 o 必须最后被取出；
//   2. 把队列看成"环形区间"：首副本一侧已消耗，剩余数字分成两段
//      （副本 o 的左侧段与右侧段）。第 i 对取数时，两个副本必须
//      分别是这两段中某段的当前端点；
//   3. 每次扫描各段端点找"端点值配对"（两个端点同值），同值则两端
//      同时收缩并记录方向（L 优先保证字典序）；找不到则失败。
//   直白版每步线性扫端点（最多 4 个端点 × 配对查找），总 O(n^2)；
//   方案二用位置表做到 O(n)。
// 复杂度：O(n^2)。
// 易错点：
//   1. 首步 L 优先，失败再试 R；
//   2. 首值副本 o 所在位置决定两段的初始边界；
//   3. 每对操作的方向：第 i 个取自哪段哪端，对称位方向由配对端决定；
//   4. T 组独立。
#include <cstdio>
#include <cstring>
using namespace std;

int T, n, len;
int a[500005];
char ans[500005];

int main() {
    freopen("palin.in", "r", stdin);
    freopen("palin.out", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        len = 2 * n;
        for (int i = 1; i <= len; i++) scanf("%d", &a[i]);
        bool solved = false;
        for (int firstDir = 0; firstDir < 2 && !solved; firstDir++) {
            int v = (firstDir == 0) ? a[1] : a[len];
            // 找 v 的两副本位置 p < q
            int p = 0, qq = 0;
            for (int i = 1; i <= len; i++)
                if (a[i] == v) { if (p == 0) p = i; else qq = i; }
            // 两段：(p+1, qq-1) 与 (qq+1, len) ∪ (1, p-1) 环形
            // 首步取的是 p 侧（若首步 L 则 p 必须为 1；R 则 q 必须为 len）
            if (firstDir == 0 && p != 1) continue;
            if (firstDir == 1 && qq != len) continue;
            // 双段端点：段 A = [p+1, qq-1]，段 B = [qq+1, len] 与 [1, p-1]
            int a1 = p + 1, a2 = qq - 1;         // 段 A
            int b1 = qq + 1, b2 = len;           // 段 B 右半
            int c1 = 1, c2 = p - 1;              // 段 B 左半（环形）
            int live1 = (a1 <= a2), live2 = (b1 <= b2 || c1 <= c2);
            (void)live1;
            (void)live2;
            char ops[500005];
            ops[1] = (firstDir == 0) ? 'L' : 'R';
            ops[len] = (firstDir == 0) ? 'R' : 'L';
            bool ok = true;
            // 成对处理第 2..n 对
            for (int i = 2; i <= n && ok; i++) {
                // 收集当前可用端点（值, 段, 是否左端）
                int found = 0;
                int vL = 0, dirL = 0;
                // 依次检查 A 左、B 右、B 左、A 右 —— L 优先
                struct Cand { int pos; char dir; int seg; };
                Cand cand[4];
                int cn = 0;
                if (a1 <= a2) cand[cn++] = {a1, 'L', 0};
                if (c2 >= c1) cand[cn++] = {c1, 'L', 1};
                if (b2 >= b1) cand[cn++] = {b2, 'R', 1};
                if (a2 >= a1) cand[cn++] = {a2, 'R', 0};
                for (int ci = 0; ci < cn && !found; ci++) {
                    int pv = a[cand[ci].pos];
                    // 找 pv 的另一副本是否也在某端点
                    for (int cj = 0; cj < cn && !found; cj++) {
                        if (cj == ci) continue;
                        if (a[cand[cj].pos] == pv) {
                            // 配对成功：消耗两端
                            found = 1;
                            ops[i] = cand[ci].dir;
                            ops[len + 1 - i] = cand[cj].dir;
                            // 收缩对应端点
                            if (cand[ci].seg == 0 && cand[ci].dir == 'L') a1++;
                            if (cand[ci].seg == 0 && cand[ci].dir == 'R') a2--;
                            if (cand[ci].seg == 1 && cand[ci].dir == 'L') c1++;
                            if (cand[ci].seg == 1 && cand[ci].dir == 'R') b2--;
                            if (cand[cj].seg == 0 && cand[cj].dir == 'L') a1++;
                            if (cand[cj].seg == 0 && cand[cj].dir == 'R') a2--;
                            if (cand[cj].seg == 1 && cand[cj].dir == 'L') c1++;
                            if (cand[cj].seg == 1 && cand[cj].dir == 'R') b2--;
                        }
                    }
                }
                if (!found) ok = false;
            }
            if (ok) {
                solved = true;
                for (int i = 1; i <= len; i++) ans[i] = ops[i];
            }
        }
        if (solved) printf("%s\n", ans + 1);
        else printf("-1\n");
    }
    return 0;
}
2021 回文 · 方案一 环形配对逆向

正文

CSP-S 标程 · 复赛真题的其它内容

2021 回文 · 方案一环形配对逆向
