NekoNowcoder

Appearance

subsequence 2 - 题解 ​

标签与难度 ​

标签: 图论, 拓扑排序, 构造, 字符串, 哈希 难度: 1900

题目大意喵~ ​

你好呀，未来的算法大师！本喵今天带来一个有趣的谜题哦~ ฅ(●'◡'●)ฅ

题目是这样的：有一个长度为 n 的神秘字符串，它只由前 m 个小写英文字母组成。我们虽然看不到这个字符串，但出题人非常慷慨地为我们提供了线索！对于任意两种不同的字母（比如 'a' 和 'b'），他都会告诉我们一个子序列。这个子序列是通过从神秘字符串中删除所有不是这两个字母的字符得到的。

举个栗子，如果神秘字符串是 "apple"，我们选择的字母是 'e' 和 'p'，那么得到的子序列就是 "ppe"。

我们的任务，就是根据所有这些成对的子序列线索，把原来的神秘字符串给找出来！如果找不到，就说明线索有矛盾，输出 -1。如果有很多种可能的答案，随便输出一个就可以啦，喵~

解题思路分析 ​

这道题给了我们好多好多关于字符之间相对顺序的信息，一看到“顺序”、“依赖关系”这类词，本喵的直觉雷达就“叮”地一下响了——这很可能和拓扑排序有关哦！

为什么是拓扑排序？ ​

拓扑排序是用来解决有向无环图（DAG）中节点线性排序问题的。如果图中有一条从 u 到 v 的边，那么在排序结果中，u 一定在 v 的前面。这不就和我们题目中的情况很像嘛？一个字符在另一个字符前面，这就是一种顺序限制。

确定图的节点 (Nodes) ​

首先，图得有节点呀！我们能直接用 'a', 'b', 'c' ... 当作节点吗？ 不行哦！因为同一个字母可能在字符串里出现好几次，比如 "banana"。第一个 'a' 和第二个 'a' 是不同的，它们在字符串里的位置也不同。所以，我们的节点必须能唯一地表示字符串中每一个字符的每一次出现。

我们可以用一个二元组 (character, k) 来表示一个节点，意思是“字符 character 的第 k 次出现”。例如，('b', 1) 代表第一个 'b'，('a', 2) 代表第二个 'a'。这样，原字符串中的 n 个字符就对应了我们图中的 n 个节点。

确定图的边 (Edges) ​

节点有了，边从哪里来呢？当然是从题目给的子序列线索里来啦！

假设我们拿到了一对字母 c1 和 c2 的子序列，比如说 s = "c1c2c1"。 这个子序列告诉我们：

  1. 第一个 c1 出现在第一个 c2 之前。
  2. 第一个 c2 出现在第二个 c1 之前。

这就可以转化为图中的有向边了！

  • 从代表“第一个 c1”的节点，画一条指向“第一个 c2”的节点的边。
  • 从代表“第一个 c2”的节点，画一条指向“第二个 c1”的节点的边。

对于子序列中每一个相邻的字符 s[i] 和 s[i+1]，我们都从 s[i] 对应的节点向 s[i+1] 对应的节点连一条边。这样，我们就把所有的顺序限制都建成了一张大大的有向图！

如何唯一表示节点？ ​

('a', 1) 这种表示方法对我们我来说很直观，但电脑程序更喜欢用数字ID来表示节点。我们需要一个聪明的办法，把 (char, k) 映射成一个独一无二的整数ID。

这里有一个很酷的哈希技巧，喵~ 我们可以定义一个足够大的常数 C（比如比 n 大一点，n+1 就很安全），然后这样计算ID： node_id = (character - 'a') * C + (k - 1) 这里 k 是第几次出现（从1开始），所以 k-1 是从0开始的索引。

  • character - 'a' 的范围是 0 到 25。
  • k-1 的范围是 0 到 n-1。 因为 k-1 < n < C，所以不同的 (character, k) 组合绝对不会撞车，完美地生成了唯一的ID！

整合起来：算法流程 ​

好啦，思路已经清晰了，让我们把步骤串起来，喵~

  1. 建图：

    • 我们需要一个邻接表 adj 来存图，还需要一个数组 in_degree 来记录每个节点的入度（有多少条边指向它）。
    • 遍历题目给的 m*(m-1)/2 个子序列。
    • 对于每个关于 c1, c2 的子序列 s：
      • 维护 c1 和 c2 的出现次数计数器 k1, k2（从0开始）。
      • 遍历子序列 s，对于相邻的两个字符 s[i] 和 s[i+1]:
        • 计算出它们分别对应的节点ID u_id 和 v_id。
        • 在图中添加一条边 u_id -> v_id，并把 in_degree[v_id] 加一。

  2. 拓扑排序 (Kahn's Algorithm)：

    • 创建一个队列 q，用来存放所有入度为0的节点。这些是排在最前面的字符，没有任何其他字符必须在它们之前。
    • 遍历所有我们创建过的节点，如果某个节点的 in_degree 是0，就把它加入队列 q。
    • 当队列不为空时，循环执行：
      • 从队列中取出一个节点 u。
      • 将 u 对应的字符追加到我们的答案字符串 ans 的末尾。
      • 遍历 u 的所有邻居 v（即所有 u 指向的节点）：
        • 将 v 的入度 in_degree[v] 减一。
        • 如果 in_degree[v] 变成了0，说明 v 的所有前置条件都已满足，可以把它加入队列 q 了！

  3. 检查结果：

    • 拓扑排序结束后，检查我们构造出的答案字符串 ans 的长度。
    • 如果 ans.length() == n，太棒了！我们成功找到了一个合法的原始字符串，输出 ans 就好。
    • 如果 ans.length() != n，这说明图里存在环（即线索互相矛盾，比如 A 在 B 前，B 在 C 前，C 又在 A 前），或者图不连通导致没能包含所有 n 个字符。这时就无解，输出 -1。

这个方法把一个看似复杂的字符串谜题，变成了一个经典的图论问题，是不是很优雅呢？喵~

代码实现 ​

这是本喵根据上面的思路，精心为你准备的代码哦！注释写得很详细，希望能帮到你，呐~

cpp
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <numeric>

// 定义一个足够大的常量作为哈希乘子
// n 最大为 100000，所以 100001 是一个安全的选择
const int NODE_MULTIPLIER = 100001; 
// 节点ID的最大可能值，m <= 26
const int MAX_NODE_ID = 26 * NODE_MULTIPLIER; 

// 使用 vector 代替原生数组，更安全喵~
std::vector<std::vector<int>> adj;
std::vector<int> in_degree;
// 用来记录所有出现过的节点ID，方便初始化队列
std::vector<bool> node_exists;

int main() {
    // 加速输入输出，让程序跑得像小猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    // 初始化邻接表和入度数组
    adj.resize(MAX_NODE_ID);
    in_degree.assign(MAX_NODE_ID, 0);
    node_exists.assign(MAX_NODE_ID, false);

    int num_pairs = m * (m - 1) / 2;
    for (int i = 0; i < num_pairs; ++i) {
        char c1, c2;
        int len;
        std::cin >> c1 >> c2 >> len;
        
        if (len == 0) {
            std::string dummy; // 即使长度为0，也可能有一个空字符串需要读取
            if (std::cin.peek() != '\n' && std::cin.peek() != EOF && std::cin.peek() != '\r') {
                 // 根据题目格式，长度为0时后面没有字符串，但为了健壮性检查一下
            }
            continue;
        }

        std::string s;
        std::cin >> s;

        // c1 和 c2 的0-indexed出现次数计数器
        int k1 = 0, k2 = 0;
        std::vector<int> node_sequence;
        node_sequence.reserve(len);

        // 第一步：将子序列中的字符转换为节点ID序列
        for (char ch : s) {
            int node_id;
            if (ch == c1) {
                node_id = (c1 - 'a') * NODE_MULTIPLIER + k1;
                k1++;
            } else { // ch == c2
                node_id = (c2 - 'a') * NODE_MULTIPLIER + k2;
                k2++;
            }
            node_sequence.push_back(node_id);
            node_exists[node_id] = true;
        }

        // 第二步：根据节点ID序列建立边
        for (size_t j = 0; j < node_sequence.size() - 1; ++j) {
            int u = node_sequence[j];
            int v = node_sequence[j + 1];
            adj[u].push_back(v);
            in_degree[v]++;
        }
    }

    // --- 拓扑排序开始 ---
    std::queue<int> q;
    // 找到所有入度为0的起始节点
    for (int i = 0; i < MAX_NODE_ID; ++i) {
        if (node_exists[i] && in_degree[i] == 0) {
            q.push(i);
        }
    }

    std::string result_str = "";
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // 从节点ID反向解析出字符
        char ch = 'a' + (u / NODE_MULTIPLIER);
        result_str += ch;

        for (int v : adj[u]) {
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

    // --- 检查结果 ---
    if (result_str.length() == n) {
        std::cout << result_str << '\n';
    } else {
        std::cout << "-1\n";
    }

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(m2+m⋅n)O(m^2 + m \cdot n)

    • 设 m 是字符集大小，n 是隐藏字符串的长度。
    • 总共有 O(m2)O(m^2) 对字符，我们需要读取所有输入。
    • 所有子序列的总长度之和是多少呢？对于一个字符 c，它会出现在 m-1 个子序列中（与其它 m-1 个字符的配对）。所以，所有子序列的长度加起来是 ∑c(m−1)⋅count(c)=(m−1)∑ccount(c)=(m−1)⋅n\sum_{c} (m-1) \cdot \text{count}(c) = (m-1) \sum_{c} \text{count}(c) = (m-1) \cdot n。
    • 建图的过程需要遍历所有子序列的所有字符，所以时间复杂度是 O(m⋅n)O(m \cdot n)。
    • 拓扑排序的时间复杂度是 O(V+E)O(V+E)，其中 V 是节点数（n），E 是边数。边的总数也和子序列总长度成正比，是 O(m⋅n)O(m \cdot n)。
    • 所以，总的时间复杂度是 O(m2+m⋅n)O(m^2 + m \cdot n)。考虑到 m 最大是 26，这个复杂度是完全可以接受的！

  • 空间复杂度: O(m⋅n)O(m \cdot n)

    • 我们使用了邻接表 adj 和入度数组 in_degree 等。
    • 节点ID的最大值可以达到 m * (n+1) 级别，所以数组大小需要开到 O(m⋅n)O(m \cdot n)。
    • 邻接表中存储的边的总数也是 O(m⋅n)O(m \cdot n)。
    • 因此，主要的空间开销来自于图的存储，为 O(m⋅n)O(m \cdot n)。

知识点总结 ​

这道题真是一次很棒的练习呢，喵！我们从中可以学到：

  1. 问题建模: 如何将一个看似与图无关的问题（字符串恢复）抽象成一个图论问题。识别出问题中的“实体”作为节点，“关系”作为边，是解决这类问题的关键一步。
  2. 拓扑排序: 它是解决依赖和顺序问题的强大工具。Kahn算法（基于队列和入度）是实现拓扑排序的经典方法。
  3. 哈希思想: 当需要为复杂结构（如本题的 (char, k)）创建唯一ID时，使用一个简单的数学公式进行哈希映射是一种非常高效和简洁的技巧。
  4. 细节处理: 别忘了处理边界情况，比如长度为0的子序列，以及最后检查结果的合法性（长度是否为 n）。

希望这篇题解能让你有所收获！继续加油，你超棒的！喵~ (ฅ'ω'ฅ)