8.12总结

T1 Asya and Kittens

题意

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

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

思路

核心观察

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

数据结构

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

合并操作

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

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

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

输出

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

复杂度

时间： $O(n · α(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）：

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

正确性

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

复杂度

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

样例验证

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

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

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

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

| 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]：

若 pre[c] 已确定，直接输出。
否则从 '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 · 26^2)$ 最坏，实际链很短， $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：

从根节点 pos = 0 出发。
取当前位 w = (x >> i) & 1。
若分支 tree[pos][w] 不存在，创建新节点（tot 自增）。
移动到子节点，cnt[pos]++ 表示该节点又有一个数经过。

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

root

/ \

0 1

/ \ /

0 1 0

| | |

... 5 5

查询 query(x)

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

从根节点出发，结果 ret = 0。
从高位到低位逐位处理：

- 取 x 的当前位 w。

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

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

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

复杂度

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

关键点

高位优先贪心：异或的高位对结果影响最大，所以从 bit 29 到 bit 0 逐位贪心选相同位。
cnt 处理重复：cnt[pos] 记录经过节点的数字数，查询时递减，确保每个 b 元素只匹配一次。
异或为 0 最优：走相同分支时 ret 不变（该位异或 0），走相反分支时 ret |= (1<<i) 累加异或贡献。
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)。

三步法

栈预处理配对：扫描括号序列，遇 ( 入栈，遇 ) 弹栈，记录 match[i]。O(n)。
双向链表：pre[i]、nxt[i] 连接未删除括号，0 号作哨兵（nxt[0] 是链表头）。初始 pre[i]=i-1, nxt[i]=i+1。
操作处理： - 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 的最长回文前缀和最长回文后缀中较长的一个。

算法步骤

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

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;
}

8.12总结

8.12总结

T1 Asya and Kittens

题意

思路

核心观察

数据结构

合并操作

输出

复杂度

关键点

代码

T2 String Transformation 1

题意

思路

无解判定

建图

贪心策略

正确性

复杂度

样例验证

关键点

代码

T3 Phase Shift

转化

贪心构造

小环检测

闭合大环

正确性

代码

T4 Perfect Security

题意

核心思想

Trie 结构

插入 insert(x)

查询 query(x)

复杂度

关键点

代码

T5 Correct Bracket Sequence Editor

题意

思路

关键：O(1) 的 D 操作

三步法

为什么正确

输出

复杂度

关键点

代码

T6 Prefix-Suffix Palindrome (Hard Version)

题意

思路

答案结构

算法步骤

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

复杂度

样例验证

关键点

代码

0 条评论

目前还没有评论...

还没有账户？

登录