QYcode QYcode
博客广场/ zhuyqi
比赛总结

8.12总结

8.12总结 T1 Asya and Kittens 题意 有 n 只小猫，编号 1 到 n，分别放在一排 n 个格子中（每个格子一只）。相邻格子之间有隔板，共 n-1 块。每天 Asya 观察到相邻格子里的两只小猫 x_i 和 y_i 想一起玩，于是拆掉它们之间的隔板，把两个格子合并成一个。 给出 n-1 天里每天的 (x_i, y_i)，求一个合法的初始

zhuyqi发布于 2026-8-12 15:29:03
综合/比赛总结

8.12总结

T1 Asya and Kittens

题意

有 n 只小猫，编号 1 到 n，分别放在一排 n 个格子中（每个格子一只）。相邻格子之间有隔板，共 n-1 块。每天 Asya 观察到相邻格子里的两只小猫 xix_i 和 yiy_i 想一起玩，于是拆掉它们之间的隔板，把两个格子合并成一个。

给出 n-1 天里每天的 (xi,yi)(x_i, y_i)，求一个合法的初始排列（保证有解）。

思路

核心观察

每次合并的两个连通块在合并前必定相邻，所以可以把每个连通块看成一条链，合并就是把两条链首尾相接。

数据结构

  • 并查集：维护每个元素属于哪个连通块。
  • 链表：对每个连通块维护 head（链首）和 tail（链尾），用 nxt 数组串联。

合并操作

对于一次操作 (x, y)：

  1. fx = find(x), fy = find(y) 找到各自所在连通块的代表。
  2. 把 x 所在链的尾接到 y 所在链的首：nxt[tail[fx]] = head[fy]。
  3. 更新合并后链的尾：tail[fx] = tail[fy]。
  4. 并查集合并：fa[fy] = fx（fy 的信息此后不再使用）。

由于 x 和 y 在合并当天相邻，这种首尾相接的连接方式天然满足"相邻"约束。

输出

所有合并完成后只剩一个连通块。从其链首 head[find(1)] 出发，沿 nxt 一路输出到链尾即可。

复杂度

  • 时间：O(n⋅α(n))O(n · α(n))，并查集路径压缩后近似线性。
  • 空间：O(n)O(n)。

关键点

  • 每个连通块是一条链，合并时连接"左链尾 → 右链首"，保证相邻关系。
  • 用并查集定位代表元素，合并后只保留左连通块的信息（右块作废）。
  • 题目保证有解，所以直接按输入顺序合并即可得到一组合法排列。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int fa[150010];
int find (int x) {
    if (fa[x] == x) return x;
    return fa[x] = find (fa[x]);
}
int head[150010], tail[150010], nxt[150010];
int n;
int main () {
	scanf ("%d", &n);
    for (int i = 1; i <= n; i++) {
        fa[i] = head[i] = tail[i] = i;
        nxt[i] = 0;
    }
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf ("%d%d", &x, &y);
        int fx = find (x), fy = find (y);
        nxt[tail[fx]] = head[fy];
        tail[fx] = tail[fy];
        fa[fy] = fx;
    }
    int root = find (1);
    int cur = head[root];
    while (cur != 0) {
        printf ("%d ", cur);
        cur = nxt[cur];
    }
	return 0;
}

T2 String Transformation 1

题意

两个长度为 n 的字符串 A 和 B，仅含前 20 个小写字母（a-t）。每次操作：

  • 选 A 中若干个相同字母 x 的位置（子集）。
  • 选一个字母 y > x（严格大于）。
  • 把这些位置全改成 y。

求最少操作数使 A = B，无解输出 -1。

思路

无解判定

只能把字母变大（y > x），所以若任一位置 A[i] > B[i]，则无解，输出 -1。

建图

字母只有 20 种，用 20×20 邻接矩阵 edge[x][y] 记录所有需要的转换：对每个 A[i] < B[i] 的位置，标记 edge[A[i]][B[i]] = true（去重，相同转换只需一次）。

贪心策略

从小到大处理每个字母 x（0 到 19）：

  1. 在 x 的所有出边中找最小目标 m。
  2. 花 1 次操作：把 x 变成 m（满足 y = m > x）。
  3. 目标为 m 的位置已完成，删除边 x→m。
  4. 其余更大目标 y > m 的位置：现在它们位于 m，仍需到达 y，所以把边 x→y 重定向为 m→y。

正确性

  • 选最小目标 m 是最优的：先把 x 变成 m，再由 m 继续处理更大的目标，避免对 x 重复操作。
  • 重定向后的边 m→y 满足 m < y（因为 m 是最小目标，其余 y > m），合法。
  • 由于从小到大处理，重定向到的 m 会在后续被处理。

复杂度

  • 时间：O(n+202)O(n + 20^2) 每组数据，非常高效。
  • 空间：O(n+202)O(n + 20^2)。

样例验证

| 输入 | 边 | 过程 | 输出 |

|------------------------|------------------------|------------------------|------|

| aab → bcc | a→b, b→c | a→b(1), b→c(2) | 2 |

| cabc → abcb | c>a 无解 | - | -1|

| abc → tsr | a→t, b→s, c→r | 各 1 次 | 3 |

| aabd → cccd | a→c, b→c | a→c(1), b→c(2) | 2 |

| abcbd → bcdda | d>a 无解 | - | -1 |

关键点

  • 字母只有 20 种，用邻接矩阵去重转换需求。
  • 贪心：每个字母选最小目标先变，其余目标重定向，保证每个字母最多花 1 次操作。
  • A[i] > B[i] 直接无解。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T, n;
char A[100010], B[100010];
bool edge[21][21];
int main () {
	scanf ("%d", &T);
    while (T--) {
        scanf ("%d%s%s", &n, A, B);
        for (int i = 0; i < 20; i++) {
            for (int j = 0; j < 20; j++) edge[i][j] = false;
        }
        bool ok = true;
        for (int i = 0; i < n; i++) {
            int a = A[i] - 'a';
            int b = B[i] - 'a';
            if (a > b) {
                ok = false;
                break;
            }
            if (a < b) edge[a][b] = true;
        }
        if (!ok) {
            puts ("-1");
            continue;
        }
        int ans = 0;
        for (int x = 0; x < 20; x++) {
            int m = -1;
            for (int y = x + 1; y < 20; y++) {
                if (edge[x][y]) {
                    m = y;
                    break;
                }
            }
            if (m == -1) continue;
            ans ++;
            edge[x][m] = false;
            for (int y = m + 1; y < 20; y++) {
                if (edge[x][y]) {
                    edge[x][y] = false;
                    edge[m][y] = true;
                }
            }
        }
        printf ("%d\n", ans);
    }
	return 0;
}

T3 Phase Shift

题意

26 个小写字母按某种顺序排成一个环。加密：字符串 s 中每个字母替换为环中顺时针下一个字母，得到 t。给 t，求字典序最小的原串 s。思路

转化

环中每个字母 c 有唯一"前驱" d（d 的顺时针下一个是 c），即 nxt[d] = c，pre[c] = d。于是 s[i] = pre[t[i]]。

题目等价于：构造一个 26 个字母的置换（单一大环），对每个 t[i] 输出 pre[t[i]]，使 s 字典序最小。

贪心构造

从左到右扫描 t，对每个字符 c = t[i]：

  1. 若 pre[c] 已确定，直接输出。

  2. 否则从 'a' 到 'z' 找最小的可用 d：

    • d ≠ c（不能自环，否则环长度为 1）。
    • used[d] = false（d 还没分配后继，保证每个字母后继唯一）。
    • 不能形成长度 < 26 的小环。

小环检测

分配 nxt[d] = c 会形成环 ⟺ d 与 c 已在同一条链上（c 是链头，d 是链尾）。

由于 used[d]=false 说明 d 是某条链的尾（nxt[d] 未设），c 有 pre[c]=-1 说明 c 是链头。若沿 nxt 从 c 出发能到达 d，则它们同属一条链，分配会闭合小环 → 跳过。

闭合大环

当已分配 25 条边（cnt=25）时，26 个字母恰组成一条长度 26 的链。此时仅剩链尾 d 和链头 c，分配 nxt[d]=c 闭合为完整大环——这是合法的，必须允许。所以 cnt=25 时跳过小环检测。

正确性

  • 贪心选最小 d 保证字典序最小。
  • 小环检测保证最终能形成包含全部 26 字母的单一大环。
  • 每个字母前驱/后继唯一，符合环结构。

复杂度

  • 时间：O(n⋅262)O(n · 26^2) 最坏，实际链很短，O(n⋅26)O(n · 26)。
  • 空间：O(n+26)O(n + 26)。

样例验证

t s 说明
a b a 的前驱选最小可用 b
ba ac b→a, a 的前驱不能是 a 或 b（b 已指向 a 会成小环），选 c
codeforces abcdebfadg 依次分配 c→a, o→b, d→c, e→d, f→e, r→f, s→g
abc...xyz bcdef...xyza 每个字母前驱为下一字母，最后 z 的前驱为 a 闭合
abc...wxyza (末两位交换) bcdef...xyaz 同上，顺序不同导致闭合点不同

关键点

  • 逆向思考：求 pre[c]（c 的前驱）而非直接求映射。
  • 贪心 + 小环检测：每个 d 选最小可用，避免提前闭合小环。
  • cnt=25 时允许闭合，形成完整 26 环。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T, n;
char s[100010];
int pre[27], nxt[27];
bool used[27];
int main () {
	int T;
    scanf ("%d", &T);
    while (T--) {
        scanf ("%d%s", &n, s);
        for (int i = 0; i < 26; i++) {
            pre[i] = nxt[i] = -1;
            used[i] = false;
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'a';
            if (pre[c] != -1) {
                putchar (pre[c] + 'a');
                continue;
            }
            for (int d = 0; d < 26; d++) {
                if (d == c) continue;
                if (used[d]) continue;
                bool flag = false;
                if (cnt < 25) {
                    int x = nxt[c];
                    while (x != -1) {
                        if (x == d) {
                            flag = true;
                            break;
                        }
                        x = nxt[x];
                    }
                }
                if (flag) continue;
                pre[c] = d, nxt[d] = c, used[d] = true;
                cnt ++;
                putchar (d + 'a');
                break;
            }
        }
        printf ("\n");
    }
	return 0;
}

T4 Perfect Security

题意

给定两个长度为 n 的数组 a 和 b，对每个 a[i]，从 b 中选一个元素（每个元素只能用一次），使得 a[i] XOR b[j] 最小。输出每对的最小异或值。

核心思想

要让两个数的异或最小，应让高位尽量相同（相同则异或为 0）。Trie 可以按位存储二进制数，从高位到低位贪心匹配相同的位，就能实现异或最小化。

Trie 结构

每个整数用 30 位二进制表示（从 bit 29 到 bit 0）。Trie 每个节点有两个分支：

  • tree[pos][0]：当前位为 0 的子节点
  • tree[pos][1]：当前位为 1 的子节点

cnt[pos] 记录经过该节点的数字个数，用于处理重复元素。

插入 insert(x)

将数字 x 的 30 位二进制从高到低逐位插入 Trie：

  1. 从根节点 pos = 0 出发。

  2. 取当前位 w = (x >> i) & 1。

  3. 若分支 tree[pos][w] 不存在，创建新节点（tot 自增）。

  4. 移动到子节点，cnt[pos]++ 表示该节点又有一个数经过。

    示例：插入 5 (二进制 101)

          root

         /   \

        0     1

       / \   /

      0   1  0

      |   |  |

      ... 5  5

查询 query(x)

对 a[i]，在 Trie 中贪心找异或最小的 b[j]：

  1. 从根节点出发，结果 ret = 0。

  2. 从高位到低位逐位处理：

    • 取 x 的当前位 w。

     - 优先走相同的分支 tree[pos][w]（如果存在且 cnt > 0），此时该位异或为 0，不产生贡献。

     - 若相同分支不可用，走相反分支 tree[pos][w ^ 1]，此时该位异或为 1，ret |= (1 << i) 累加贡献。

  3. 每走一步 cnt[pos]--，表示该节点被一个 b 元素"消耗"，处理重复元素（每个 b 只能用一次）。

复杂度

  • 时间：O(n × 30)，每个 a[i] 查询 30 层 Trie。
  • 空间：O(n × 30)，Trie 节点数不超过 n × 30。

关键点

  1. 高位优先贪心：异或的高位对结果影响最大，所以从 bit 29 到 bit 0 逐位贪心选相同位。
  2. cnt 处理重复：cnt[pos] 记录经过节点的数字数，查询时递减，确保每个 b 元素只匹配一次。
  3. 异或为 0 最优：走相同分支时 ret 不变（该位异或 0），走相反分支时 ret |= (1<<i) 累加异或贡献。
  4. 30 位表示：int 最多 31 位符号位，取 30 位（bit 29~0）足够表示非负整数。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 300000 * 31 + 10;
int n;
int a[300010];
int tot;
int tree[N][2];
int cnt[N];
void insert (int x) {
    int pos = 0;
    for (int i = 29; i >= 0; i--) {
        int w = (x >> i) & 1;
        if (tree[pos][w] == 0) tot ++, tree[pos][w] = tot, tree[tot][0] = tree[tot][1] = 0, cnt[tot] = 0;
        pos = tree[pos][w];
        cnt[pos] ++;
    }
}
int query (int x) {
    int pos = 0, ret = 0;
    for (int i = 29; i >= 0; i--) {
        int w = (x >> i) & 1;
        if (tree[pos][w] != 0 && cnt[tree[pos][w]] > 0) pos = tree[pos][w];
        else w ^= 1, pos = tree[pos][w], ret |= (1 << i);
        cnt[pos] --;
    }
    return ret;
}
int main () {
	scanf ("%d", &n);
    for (int i = 0; i < n; i++) scanf ("%d", &a[i]);
    tot = 0, tree[0][0] = tree[0][1] = 0, cnt[0] = 0;
    for (int i = 0; i < n; i++) {
        int x;
        scanf ("%d", &x);
        insert (x);
    }
    for (int i = 0; i < n; i++) printf ("%d ", query (a[i]));
	return 0;
}

T5 Correct Bracket Sequence Editor

题意

一个长度 n 的合法括号序列，光标初始在位置 p。m 次操作：

  • L：光标左移一位
  • R：光标右移一位
  • D：删除光标所在括号、其配对括号及它们之间的所有括号。删除后光标移到右侧最近的未删除括号；若无则移到左侧最近的。

输出最终括号序列。n, m ≤ 5×10⁵。

思路

关键：O(1) 的 D 操作

D 删除的是一个完整区间 [l, r]，其中 l、r 是配对括号。用双向链表维护未删除括号，删除整段只需更新两个边界指针，O(1)。

三步法

  1. 栈预处理配对：扫描括号序列，遇 ( 入栈，遇 ) 弹栈，记录 match[i]。O(n)。
  2. 双向链表：pre[i]、nxt[i] 连接未删除括号，0 号作哨兵（nxt[0] 是链表头）。初始 pre[i]=i-1, nxt[i]=i+1。
  3. 操作处理：   - L：p = pre[p]   - R：p = nxt[p]   - D：     - l = min(p, match[p]), r = max(p, match[p])     - nl = pre[l], nr = nxt[r]     - 光标：nr != 0 则 p = nr，否则 p = nl     - 摘除整段：nxt[nl] = nr; pre[nr] = nl

为什么正确

  • match[] 基于原始位置，删除不影响配对关系。
  • 链表只含未删除括号，从光标（始终未删除）经 pre/nxt 移动自然跳过已删除。
  • D 删整段：边界一接，中间括号从链表脱离，不再可达，等价于删除。
  • 光标规则：删除 [l,r] 后，右侧最近未删除即 nxt[r]（删除前的链表后继），若无（删到末尾）取 pre[l]。

输出

从 nxt[0]（链表头）沿 nxt 遍历输出。

复杂度

  • 时间：O(n + m)，每个操作 O(1)。
  • 空间：O(n)。

关键点

  • D 删的是配对括号夹住的整段，用链表边界更新 O(1) 实现，无需逐个删除。
  • match 预处理基于原始位置，固定不变。
  • 哨兵 0 简化边界：nxt[0] 是头，pre[0]/nxt[0] 的更新让首尾删除也统一处理。
  • **必须初始化 **nxt[0] = 1：否则链表头不指向位置 1，若全程没删到位置 1（l 从不为 1），nxt[0] 恒为 0，输出为空。删到位置 1 时 nl=pre[1]=0 会间接更新 nxt[0]，但不能依赖这点。
  • 光标删除后优先取右侧 nxt[r]，无则取左侧 pre[l]。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, p;
char s[500010], ops[500010];
int match[500010], stk[500010], top; // macth[i]:i的配对位置，stk[]:预处理用的栈，top:栈顶
int pre[500010], nxt[500010];
int cur; // 当前光标位置
int main () {
	scanf ("%d%d%d", &n, &m, &p);
    scanf ("%s", s + 1);
    for (int i = 1; i <= n; i++) {
        if (s[i] == '(') stk[top++] = i; // 左括号入栈
        else {
            int j = stk[--top]; // 弹出最近的左括号位置
            match[i] = j, match[j] = i; // 左右括号i,j分别配对
        }
    }
    for (int i = 1; i <= n; i++) {
        pre[i] = i - 1;
        nxt[i] = i + 1;
    }
    pre[1] = 0;
    nxt[n] = 0, nxt[0] = 1;
    cur = p;
    scanf ("%s", ops);
    for (int i = 0; i < m; i++) {
        if (ops[i] == 'L') cur = pre[cur];
        else if (ops[i] == 'R') cur = nxt[cur];
        else {
            int l, r;
            if (s[cur] == '(') {
                l = cur;
                r = match[cur];
            }
            else {
                l = match[cur];
                r = cur;
            }
            int nl = pre[l], nr = nxt[r];
            if (nr != 0) cur = nr;
            else cur = nl;
            nxt[nl] = nr;
            pre[nr] = nl;
        }
    }
    int t = nxt[0];
    while (t != 0) {
        putchar (s[t]);
        t = nxt[t];
    }
	return 0;
}

T6 Prefix-Suffix Palindrome (Hard Version)

题意

给定字符串 s，求最长的"前缀-后缀回文"：即一个回文串 t，它由 s 的一个前缀和一个后缀拼接而成（前缀是 s[0..i-1]，后缀是 s[n-j..n-1]）。输出任意一个最长的。

D2 数据范围：n ≤ 10⁶，Σn ≤ 10⁶。

思路

答案结构

答案 = s[0..k-1] + 中间的回文 P + s[n-k..n-1]，其中 s[0..k-1] 与 s[n-k..n-1] 互为反串（前后对称部分），P 是中间剩余串 mid = s[k..n-k-1] 的一个回文子串，且 P 必须是 mid 的前缀或后缀。

为了让总长最大：

  • k 取最大（前后对称部分尽量长）。
  • P 取 mid 的最长回文前缀和最长回文后缀中较长的一个。

算法步骤

  1. 去对称：双指针求最大 k，使得 s[0..k-1] == reverse(s[n-k..n-1])。
  2. 取中间：mid = s[k..n-k-1]，长度 m = n - 2k。
  3. 找最长回文前缀：从长到短枚举 len，判断 mid[0..len-1] 是否回文，取第一个满足的。
  4. 找最长回文后缀：同理判断 mid[m-len..m-1]。
  5. 拼接：前缀 + 较长回文 + 后缀。

D2 关键优化：O(1) 回文判断

D1 用 check 逐字符比较 + substr 拷贝，单次 O(m)，总 O(n²)。

D2 用字符串哈希：

  • h1[i]：mid 正向前缀哈希。
  • h2[i]：mid 反向前缀哈希（即 mid 反转后的前缀哈希）。
  • pw[i]：BASE 的幂次。

mid[l..r] 是回文 ⟺ 正向哈希 == 反向哈希：

正向 = h1[r+1] - h1[l] * pw[r-l+1]

反向 = h2[m-l] - h2[m-r-1] * pw[r-l+1]

每次判断 O(1)，找最长回文前缀/后缀各 O(m)，总计 O(n)。

复杂度

  • 时间：O(n) 每组（预处理哈希 O(m) + 两次线性扫描 O(m)）。
  • 空间：O(n)。

样例验证

| s | k | mid | 最长回文前缀 | 最长回文后缀 | 答案 |

|---|---|-----|-------------|-------------|------|

| abacaba | 2 | aca | aca(3) | aca(3) | ab+aca+ba=abacaba |

| codeforces | 0 | codeforces | c(1) | s(1) | c |

| acbba | 1 | cbb | c(1) | bb(2) | a+bb+a=abba |

| abbabba | 3 | a | a(1) | a(1) | abb+a+bba=abbabba |

关键点

  • 答案结构：去对称前后缀 + 中间最长回文前缀/后缀。
  • 哈希 O(1) 判回文是 D2 的核心优化，把 O(n²) 降到 O(n)。
  • 从长到短枚举，第一个满足即为最长，可直接 break。
  • 取前缀和后缀中较长者；等长时任取（这里取前缀）。

代码

#include <bits/stdc++.h>
using namespace std;
bool check (string s) {
	int n = s.size ();
	for (int i = 0; i < n / 2; i++) {
		if (s[i] != s[n - i - 1]) return false;
	} 
	return true;
}
string ppre (string s) {
	for (int len = s.size (); len >= 1; len--) {
		if (check (s.substr (0, len))) return s.substr (0, len);
	}
	return "";
}
string ssuf (string s) {
	for (int len = s.size (); len >= 1; len--) {
		if (check (s.substr (s.size () - len, len))) return s.substr (s.size () - len, len);
	}
	return "";
}
int main () {
	int T;
	scanf ("%d", &T);
	while (T--) {
		string s;
		cin >> s;
		int n = s.size ();
		int k = 0;
		while (k < n / 2 && s[k] == s[n - k - 1]) k ++;
		string mid = s.substr (k, n - 2 * k);
		string pre = ppre (mid);
		string suf = ssuf (mid);
		string ans = s.substr (0, k);
		if (pre.size () >= suf.size ()) ans += pre;
		else ans += suf;
		ans += s.substr (n - k, k);
		cout << ans << endl;
	}
	return 0;
}
14 次阅读

评论

0