2021 回文 · 方案二位置表逆向构造

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 3267 字
位置表直接定位数字，从中间逆向构造操作序列
2021
贪心
正文

// CSP-S 2021 复赛 T3 · 回文（方案二：位置表 + O(n) 逆向构造，满分）
// 原题：https://oj.yecheng.tv/p/CSPS2021C
// 题意：同方案一（Σn ≤ 5e5，需满分）。
// 思路（与方案一同构，两处提速）：
//   1. pos[v][2] 直接存每个值两副本的位置，配对查找 O(1)；
//   2. 每对的字典序贪心固定顺序：候选方向 L < R，且"当前对"的四个
//      端点组合里，先试 (L, ?) 再试 (R, ?)。
//   逆向构造推导（对照方案一）：
//   - 首步取 x（L 或 R），x 的另一副本 o 必须是"最后一个被取出"的，
//     即操作串的对称位；初始两段 = o 的两侧；
//   - 第 i 对：两副本必须分别处于两段的当前端点（否则它们无法在
//     对称时刻被取出）——因为两段各自只能从端点消化，非端点元素
//     的副本若已配对必然也非端点，矛盾；
//   - 每对成功的充要：存在两段端点同值。取 L 优先的可行组合。
//   全程每元素进出一次，O(n)。
// 易错点：
//   1. 首步 R 时副本 o 必须在 len（队尾）；L 时必须在 1；
//   2. 两段是"环形"概念：o 的左段与右段都可能是首步消耗过的方向；
//   3. 无解输出 -1；多组重置 pos。
#include <cstdio>
#include <cstring>
using namespace std;

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

// 取 v 的"另一副本"位置（相对 given）
inline int other(int v, int given) {
    return pos0[v] == given ? pos1_[v] : pos0[v];
}

bool run(int firstDir) {
    int x = (firstDir == 0) ? a[1] : a[len];
    int o = other(x, firstDir == 0 ? 1 : len);
    if (firstDir == 0 && o != len) return false;    // 对称端必须是队尾
    if (firstDir == 1 && o != 1) return false;      // 对称端必须是队头
    // 两段：[1+? , o-1] 与 [o+1, len-1 / 1]（环形拆半）
    int A1, A2, B1, B2;
    if (firstDir == 0) {
        A1 = 2; A2 = o - 1;      // 左段（去掉首元素 1）
        B1 = o + 1; B2 = len - 1;
    } else {
        A1 = 2; A2 = o - 1;
        B1 = o + 1; B2 = len - 1;
        // 首步取尾：消耗 len，右段右界 len-1；左段同
    }
    ans[1] = (firstDir == 0) ? 'L' : 'R';
    ans[len] = (firstDir == 0) ? 'R' : 'L';
    for (int i = 2; i <= n; i++) {
        // 端点候选：(pos, dir, seg)；L 优先
        int cs[4][3];
        int cn = 0;
        if (A1 <= A2) { cs[cn][0]=A1; cs[cn][1]=0; cs[cn][2]=0; cn++; }   // L
        if (B1 <= B2) { cs[cn][0]=B1; cs[cn][1]=0; cs[cn][2]=1; cn++; }   // L
        if (A1 <= A2) { cs[cn][0]=A2; cs[cn][1]=1; cs[cn][2]=0; cn++; }   // R
        if (B1 <= B2) { cs[cn][0]=B2; cs[cn][1]=1; cs[cn][2]=1; cn++; }   // R
        bool found = false;
        for (int ci = 0; ci < cn && !found; ci++)
            for (int cj = 0; cj < cn && !found; cj++) {
                if (cj == ci) continue;
                if (a[cs[ci][0]] != a[cs[cj][0]]) continue;
                // 消耗
                for (int t = 0; t < 2; t++) {
                    int which = (t == 0) ? ci : cj;
                    int p = cs[which][0], isR = cs[which][1], seg = cs[which][2];
                    if (seg == 0) { if (!isR) A1++; else A2--; }
                    else { if (!isR) B1++; else B2--; }
                }
                ans[i] = cs[ci][1] ? 'R' : 'L';
                ans[len + 1 - i] = cs[cj][1] ? 'R' : 'L';
                found = true;
            }
        if (!found) return false;
    }
    return true;
}

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]);
            if (pos0[a[i]] == 0) pos0[a[i]] = i;
            else pos1_[a[i]] = i;
        }
        bool ok = run(0) || run(1);
        if (ok) printf("%s\n", ans + 1);
        else printf("-1\n");
        for (int i = 1; i <= len; i++) { pos0[a[i]] = 0; pos1_[a[i]] = 0; }
    }
    return 0;
}
2021 回文 · 方案二 位置表逆向构造

正文

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

2021 回文 · 方案二位置表逆向构造
