题意分析

Tom 需要设计一个菜单系统，要求为每个菜单项分配唯一热键。热键必须是菜单项名称中某个单词的首字母，且满足以下规则：

1. 同级唯一性：同一父菜单下的子菜单项热键不能重复。
2. 父子限制：父菜单项与直接子菜单项的热键不能重复（但非直接父子允许重复）。

输入通过 < 和 > 表示层级关系，需验证是否存在合法的热键分配方案。

解题思路

1. 树形结构解析

• 输入处理：使用栈结构解析输入的层级关系，构建树形结构。每个节点包含名称、子节点列表和热键。
• 示例：输入示例中，File 的子菜单包括 Open、Save、Send 等，其中 Send 又包含子菜单 Mail 和 Fax。

2. 热键分配规则

• 候选字母生成：从菜单项名称中提取各单词首字母作为候选（如 Save As 的候选为 S 和 A）。
• 冲突检查：
  • 父子冲突：直接子菜单项的热键不能与父菜单项相同。
  • 兄弟冲突：同一父菜单下的子菜单项热键唯一。

3. 回溯算法

• 递归分配：从根节点开始，为每个节点尝试所有可能的候选字母。
• 剪枝优化：若当前候选导致冲突（与父或兄弟节点重复），立即回溯尝试下一个候选。
• 示例分析：在输入示例中，File 的热键为 F，其子菜单 Save 已占用 S，导致 Send 无法再选 S，最终无解。

C++代码实现

#include <iostream>
#include <vector>
#include <stack>
#include <sstream>
#include <algorithm>
using namespace std;

struct Node {
    string name;
    vector<Node*> children;
    char hotkey = '\0';
    Node* parent;
    Node(const string& n, Node* p) : name(n), parent(p) {}
};

// 获取候选热键（去重后的首字母）
vector<char> getCandidates(const string& name) {
    vector<char> candidates;
    istringstream iss(name);
    string word;
    while (iss >> word) {
        if (!word.empty()) candidates.push_back(toupper(word[0]));
    }
    sort(candidates.begin(), candidates.end());
    auto last = unique(candidates.begin(), candidates.end());
    candidates.erase(last, candidates.end());
    return candidates;
}

// 递归分配热键，返回是否成功
bool assignHotkeys(Node* node) {
    vector<char> usedSiblingKeys;  // 记录当前层级已分配的热键
    char parentKey = node->parent ? node->parent->hotkey : '\0';

    for (Node* child : node->children) {
        vector<char> candidates = getCandidates(child->name);
        bool assigned = false;

        for (char c : candidates) {
            // 检查与父节点或兄弟节点冲突
            if (c == parentKey) continue;
            if (find(usedSiblingKeys.begin(), usedSiblingKeys.end(), c) != usedSiblingKeys.end()) continue;

            child->hotkey = c;
            usedSiblingKeys.push_back(c);
            // 递归处理子节点
            if (assignHotkeys(child)) {
                assigned = true;
                break;
            }
            // 回溯
            usedSiblingKeys.pop_back();
            child->hotkey = '\0';
        }
        if (!assigned) return false;
    }
    return true;
}

int main() {
    stack<Node*> st;
    Node root("", nullptr);  // 虚拟根节点
    st.push(&root);

    string line;
    getline(cin, line);  // 读取首行的 '<'
    while (getline(cin, line)) {
        if (line == "<") {
            // 进入子菜单层级
            st.push(st.top()->children.back());
        } else if (line == ">") {
            // 返回父层级
            st.pop();
        } else {
            // 新建菜单项并加入当前层级
            Node* newNode = new Node(line, st.top());
            st.top()->children.push_back(newNode);
        }
    }

    // 处理根节点的所有子节点（顶层菜单）
    bool success = true;
    for (Node* child : root.children) {
        vector<char> candidates = getCandidates(child->name);
        bool assigned = false;
        for (char c : candidates) {
            child->hotkey = c;
            if (assignHotkeys(child)) {
                assigned = true;
                break;
            }
            child->hotkey = '\0';
        }
        if (!assigned) {
            success = false;
            break;
        }
    }

    cout << (success ? "Got It!" : "No Solution") << endl;
    return 0;
}

代码说明

1. 树形结构构建：使用栈处理 < 和 > 的层级关系，构建菜单树。
2. 候选热键生成：提取菜单项名称的首字母，去重后作为候选。
3. 递归分配与回溯：为每个节点尝试所有候选字母，若冲突则回溯，直到找到合法分配或无解。