题意分析

题目要求解密通过替换密码加密的消息。关键点包括：

1. 替换密码使用双射映射（每个字符唯一对应另一个字符）
2. 加密单词保持字典序
3. 需要判断是否能唯一确定解密映射

输入给出：

• 字母表大小$A$（前$A$个小写字母）
• $K$个按字典序排列的加密单词
• 加密消息

输出要求：

• 若能唯一解密则输出解密消息
• 否则提示无法解密

解题思路

1. 构建字符顺序关系图：

   • 通过比较相邻加密单词，建立字符的先后关系
   • 例如：若$word1 < word2$，则找到第一个不同字符$c1 < c2$

2. 拓扑排序确定唯一顺序：

   • 使用Kahn算法进行拓扑排序
   • 若排序过程中队列始终只有1个元素，则顺序唯一

3. 解密消息：

   • 根据拓扑顺序建立解密映射表
   • 对加密消息进行字符替换

实现步骤

1. 输入处理：

   • 读取测试用例数$N$
   • 对每个用例读取$A$、$K$和加密单词

2. 构建有向图：

   • 比较相邻单词建立边
   • 统计入度

3. 拓扑排序：

   • 使用队列处理零入度节点
   • 检查排序唯一性

4. 解密输出：

   • 建立解密映射
   • 处理加密消息

C++实现

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <set>
using namespace std;

void solve() {
    int N;
    cin >> N;
    while (N--) {
        int A, K;
        cin >> A >> K;
        vector<string> encrypted_words(K);
        for (int i = 0; i < K; ++i) {
            cin >> encrypted_words[i];
        }
        string message;
        cin.ignore(); // To ignore the newline after K
        getline(cin, message);

        map<char, set<char> > graph; // Fixed: space in nested template
        map<char, int> in_degree;
        for (int i = 0; i < A; ++i) {
            char c = 'a' + i;
            in_degree[c] = 0;
        }

        bool possible = true;
        for (int i = 0; i < K - 1; ++i) {
            const string &word1 = encrypted_words[i];
            const string &word2 = encrypted_words[i + 1];
            size_t min_len = min(word1.size(), word2.size());
            bool found = false;
            for (size_t j = 0; j < min_len; ++j) {
                char c1 = word1[j];
                char c2 = word2[j];
                if (c1 != c2) {
                    if (graph[c1].find(c2) == graph[c1].end()) {
                        graph[c1].insert(c2);
                        in_degree[c2]++;
                    }
                    found = true;
                    break;
                }
            }
            if (!found && word1.size() > word2.size()) {
                possible = false;
                break;
            }
        }

        if (!possible) {
            cout << "Message cannot be decrypted." << endl;
            continue;
        }

        queue<char> q;
        for (map<char, int>::iterator it = in_degree.begin(); it != in_degree.end(); ++it) {
            if (it->second == 0) {
                q.push(it->first);
            }
        }

        vector<char> topo_order;
        bool is_unique = true;
        while (!q.empty()) {
            if (q.size() > 1) {
                is_unique = false;
                break;
            }
            char current = q.front();
            q.pop();
            topo_order.push_back(current);
            set<char>& neighbors = graph[current];
            for (set<char>::iterator it = neighbors.begin(); it != neighbors.end(); ++it) {
                char neighbor = *it;
                if (--in_degree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        if (topo_order.size() != static_cast<size_t>(A) || !is_unique) {
            cout << "Message cannot be decrypted." << endl;
        } else {
            map<char, char> decrypt_table;
            for (int i = 0; i < A; ++i) {
                char original_char = 'a' + i;
                decrypt_table[topo_order[i]] = original_char;
            }
            string decrypted_message;
            for (size_t i = 0; i < message.size(); ++i) {
                char c = message[i];
                if (decrypt_table.find(c) != decrypt_table.end()) {
                    decrypted_message += decrypt_table[c];
                } else {
                    decrypted_message += c;
                }
            }
            cout << decrypted_message << endl;
        }
    }
}

int main() {
    solve();
    return 0;
}

代码说明

1. 数据结构：

   • graph：字符关系邻接表
   • in_degree：字符入度统计
   • topo_order：拓扑排序结果

2. 关键算法：

   • 通过单词比较构建有向图（$O(K*L)$，$L$为单词平均长度）
   • 拓扑排序检测唯一性（$O(A+E)$，$E$为边数）

3. 特殊处理：

   • 前导相同但长度不满足字典序时直接判不可解
   • 非字母字符原样输出

4. 复杂度分析：

   • 时间复杂度：$O(K*L + A^2)$
   • 空间复杂度：$O(A^2)$