PTA-学校-数据结构（树2-2以后）

2-3 有趣的最近公共祖先问题

分数 4

作者 章立晨

单位 浙大城市学院

给出一颗二叉树的后序遍历和中序遍历，你能计算出两个结点的最近公共祖先吗？

输入格式:

第一行给出两个整数N(N<=10000)和M(M<=10000)，分别代表二叉树的结点数和我们接下来的询问数。

第二行和第三行分别给出N个整数，每个整数用空格分开，分别代表二叉树的后序遍历和中序遍历。

接下来M行，每行给出两个整数，代表我们要询问的两个结点的编号a和b。

输出格式:

对于每个我们要求的询问：

1.如果a和b中有一个或两个不在树上，输出"ERROR"。

2.否则在一行中输出一个整数，表示a和b的最近公共祖先。

输入样例:

在这里给出一组输入。例如：

3 3
2 3 1
2 1 3
1 2
2 3
0 3

输出样例:

在这里给出相应的输出。例如：

1
1
ERROR

解析

#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
#include <string>
using namespace std;

const int MAX_LEVEL = 20;  // 2^20 足够覆盖 1e4 深度

// 栈中存储的子树信息结构体
struct SubtreeInfo {
    int post_s, post_e;  // 后序遍历的起始和结束索引
    int in_s, in_e;      // 中序遍历的起始和结束索引
    int parent;          // 当前子树根的父节点
    int depth;           // 当前子树根的深度
    SubtreeInfo(int ps, int pe, int is, int ie, int p, int d)
        : post_s(ps), post_e(pe), in_s(is), in_e(ie), parent(p), depth(d) {}
};

int main() {
    int N, M;
    cin >> N >> M;

    vector<int> post(N), in_order(N);
    unordered_map<int, int> pos_map;  // 节点值 -> 中序索引

    for (int i = 0; i < N; ++i) {
        cin >> post[i];
    }
    for (int i = 0; i < N; ++i) {
        cin >> in_order[i];
        pos_map[in_order[i]] = i;
    }

    unordered_map<int, int> parent;  // 节点 -> 父节点（根的父节点设为 -1）
    unordered_map<int, int> depth;   // 节点 -> 深度

    // 迭代构建父节点和深度信息（避免递归栈溢出）
    stack<SubtreeInfo> stk;
    stk.emplace(0, N-1, 0, N-1, -1, 1);  // 初始子树：整个树，父节点 -1，深度 1

    while (!stk.empty()) {
        auto info = stk.top();
        stk.pop();

        int ps = info.post_s, pe = info.post_e;
        int is = info.in_s, ie = info.in_e;
        int p = info.parent, d = info.depth;

        if (ps > pe || is > ie) continue;

        // 当前子树的根：后序遍历的最后一个元素
        int root = post[pe];
        parent[root] = p;
        depth[root] = d;

        // 找到根在中序中的位置
        int k = pos_map[root];
        int left_len = k - is;   // 左子树节点数
        int right_len = ie - k;  // 右子树节点数

        // 先压右子树（栈先进后出，保证左子树先处理）
        if (right_len > 0) {
            int r_ps = ps + left_len;
            int r_pe = pe - 1;
            int r_is = k + 1;
            int r_ie = ie;
            stk.emplace(r_ps, r_pe, r_is, r_ie, root, d + 1);
        }
        // 再压左子树
        if (left_len > 0) {
            int l_ps = ps;
            int l_pe = ps + left_len - 1;
            int l_is = is;
            int l_ie = k - 1;
            stk.emplace(l_ps, l_pe, l_is, l_ie, root, d + 1);
        }
    }

    // 构建倍增数组：up[k][u] 表示 u 的 2^k 级祖先
    vector<unordered_map<int, int>> up(MAX_LEVEL);

    // 初始化 0 级祖先（直接父节点）
    for (auto& [u, p] : parent) {
        up[0][u] = p;
    }

    // 填充各级祖先
    for (int k = 1; k < MAX_LEVEL; ++k) {
        for (auto& [u, _] : up[k-1]) {
            int prev_ancestor = up[k-1][u];
            if (prev_ancestor != -1) {
                up[k][u] = up[k-1][prev_ancestor];
            } else {
                up[k][u] = -1;
            }
        }
    }

    // 处理查询
    vector<string> results;
    results.reserve(M);  // 预分配空间，提升效率
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;

        // 检查节点是否存在
        if (pos_map.find(a) == pos_map.end() || pos_map.find(b) == pos_map.end()) {
            results.push_back("ERROR");
            continue;
        }

        int x = a, y = b;
        // 确保 x 是深度更深的节点
        if (depth[x] < depth[y]) {
            swap(x, y);
        }

        // 第一步：将 x 上跳到与 y 同一深度
        for (int k = MAX_LEVEL - 1; k >= 0; --k) {
            if (depth[x] - (1 << k) >= depth[y]) {
                x = up[k][x];
            }
        }

        if (x == y) {
            results.push_back(to_string(x));
            continue;
        }

        // 第二步：共同上跳，直到 LCA 的下一层
        for (int k = MAX_LEVEL - 1; k >= 0; --k) {
            if (up[k][x] != -1 && up[k][x] != up[k][y]) {
                x = up[k][x];
                y = up[k][y];
            }
        }

        results.push_back(to_string(up[0][x]));
    }

    // 批量输出结果
    for (const string& res : results) {
        cout << res << '\n';
    }

    return 0;
}

2-4 修理牧场

分数 5

作者 DS课程组

单位 浙江大学

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要 n 块木头，每块木头长度为整数 l**i 个长度单位，于是他购买了一条很长的、能锯成 n 块的木头，即该木头的长度是 l**i 的总和。

但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为 20 的木头锯成长度为 8、7 和 5 的三段，第一次锯木头花费 20，将木头锯成 12 和 8；第二次锯木头花费 12，将长度为 12 的木头锯成 7 和 5，总花费为 32。如果第一次将木头锯成 15 和 5，则第二次锯木头花费 15，总花费为 35（大于 32）。

请编写程序帮助农夫计算将木头锯成 n 块的最少花费。

输入格式:

输入首先给出正整数 n（≤104），表示要将木头锯成 n 块。第二行给出 n 个正整数（≤50），表示每段木块的长度。

输出格式:

输出一个整数，即将木头锯成 n 块的最少花费。

输入样例:

8
4 5 1 2 1 3 1 1

输出样例:

49

解析

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    // 定义最小堆（优先队列，greater<int> 表示小顶堆）
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    // 读取所有木头长度并加入最小堆
    for (int i = 0; i < n; ++i) {
        int len;
        cin >> len;
        minHeap.push(len);
    }
    
    int totalCost = 0;
    // 当堆中不止一段木头时，持续合并
    while (minHeap.size() > 1) {
        // 取出两段最小的木头
        int a = minHeap.top();
        minHeap.pop();
        int b = minHeap.top();
        minHeap.pop();
        
        // 计算合并代价，累加到总花费
        int sum = a + b;
        totalCost += sum;
        
        // 将合并后的木头重新入堆
        minHeap.push(sum);
    }
    
    cout << totalCost << endl;
    return 0;
}

2-5 满树的遍历

分数 6

作者 陈越

单位 浙江大学

一棵“k 阶满树”是指树中所有非叶结点的度都是 k 的树。给定一棵树，你需要判断其是否为 k 阶满树，并输出其前序遍历序列。

注：树中结点的度是其拥有的子树的个数，而树的度是树内各结点的度的最大值。

输入格式：

输入首先在第一行给出一个正整数 n（≤105），是树中结点的个数。于是设所有结点从 1 到 n 编号。
随后 n 行，第 i 行（1≤i≤n）给出第 i 个结点的父结点编号。根结点没有父结点，则对应的父结点编号为 0。题目保证给出的是一棵合法多叉树，只有唯一根结点。

输出格式：

首先在一行中输出该树的度。如果输入的树是 k 阶满树，则加 1 个空格后输出 yes，否则输出 no。最后在第二行输出该树的前序遍历序列，数字间以 1 个空格分隔，行首尾不得有多余空格。
注意：兄弟结点按编号升序访问。

输入样例 1：

7
6
5
5
6
6
0
5

输出样例 1：

3 yes
6 1 4 5 2 3 7

输入样例 2：

7
6
5
5
6
6
0
4

输出样例 2：

3 no
6 1 4 7 5 2 3

解析

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

int main() {
    int n;
    cin >> n;

    // 存储每个节点的子节点列表（节点编号 1~n）
    vector<int> children[n + 1];
    int root = 0;

    // 1. 读取输入，构建树结构，找到根节点
    for (int i = 1; i <= n; ++i) {
        int parent;
        cin >> parent;
        if (parent == 0) {
            root = i; // 父节点为 0 的是根节点
        } else {
            children[parent].push_back(i); // 给父节点添加子节点
        }
    }

    // 2. 对每个节点的子节点按编号升序排序（满足兄弟节点访问顺序）
    for (int u = 1; u <= n; ++u) {
        sort(children[u].begin(), children[u].end());
    }

    // 3. 计算树的度 k（所有节点的最大子节点数）
    int k = 0;
    for (int u = 1; u <= n; ++u) {
        if (children[u].size() > k) {
            k = children[u].size();
        }
    }

    // 4. 判断是否为 k 阶满树（所有非叶节点的度都等于 k）
    bool is_full = true;
    for (int u = 1; u <= n; ++u) {
        // 非叶节点（子节点数 > 0）且度不等于 k → 不是满树
        if (children[u].size() != 0 && children[u].size() != k) {
            is_full = false;
            break;
        }
    }

    // 5. 迭代实现前序遍历（避免递归栈溢出）
    vector<int> pre_order;
    stack<int> st;
    st.push(root);

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        pre_order.push_back(u); // 访问当前节点

        // 逆序压入子节点（栈先进后出，逆序压入保证弹出时升序）
        for (int i = children[u].size() - 1; i >= 0; --i) {
            st.push(children[u][i]);
        }
    }

    // 6. 输出结果
    cout << k << " " << (is_full ? "yes" : "no") << endl;
    for (int i = 0; i < pre_order.size(); ++i) {
        if (i > 0) cout << " ";
        cout << pre_order[i];
    }
    cout << endl;

    return 0;
}

2-6 根据后序和中序遍历输出前序遍历

分数 6

作者 DS课程组

单位 浙江大学

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的前序遍历结果。

输入格式:

第一行给出正整数 n (≤30)，是树中结点的个数。随后两行，每行给出 n 个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式:

在一行中输出Preorder: 以及该树的前序遍历结果。数字间有1个空格，行末不得有多余空格。

输入样例:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例:

Preorder: 4 1 3 2 6 5 7

解析

#include <iostream>
#include <vector>
using namespace std;

// 递归构建前序遍历：post[in]为后序[中序]遍历数组，s/e为对应遍历的起始/结束索引，pre存储结果
void buildPreorder(vector<int>& post, vector<int>& in, int post_s, int post_e, int in_s, int in_e, vector<int>& pre) {
    if (post_s > post_e) return; // 递归终止条件：当前子树为空
    
    // 1. 后序遍历的最后一个元素是当前子树的根节点
    int root = post[post_e];
    pre.push_back(root); // 前序遍历：先访问根节点
    
    // 2. 在中序遍历中找到根节点的位置mid，划分左/右子树
    int mid = in_s;
    while (mid <= in_e && in[mid] != root) {
        mid++; // 找到根节点在中序中的索引
    }
    
    // 计算左子树的节点个数（中序中根左侧的节点数）
    int left_len = mid - in_s;
    
    // 3. 递归处理左子树
    // 后序左子树范围：[post_s, post_s + left_len - 1]
    // 中序左子树范围：[in_s, mid - 1]
    buildPreorder(post, in, post_s, post_s + left_len - 1, in_s, mid - 1, pre);
    
    // 4. 递归处理右子树
    // 后序右子树范围：[post_s + left_len, post_e - 1]
    // 中序右子树范围：[mid + 1, in_e]
    buildPreorder(post, in, post_s + left_len, post_e - 1, mid + 1, in_e, pre);
}

int main() {
    int n;
    cin >> n;
    
    vector<int> post(n); // 后序遍历数组
    vector<int> in(n);   // 中序遍历数组
    vector<int> pre;     // 存储前序遍历结果
    
    // 读取输入
    for (int i = 0; i < n; ++i) {
        cin >> post[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> in[i];
    }
    
    // 递归构建前序遍历（初始范围：后序和中序均为整个数组）
    buildPreorder(post, in, 0, n-1, 0, n-1, pre);
    
    // 输出结果
    cout << "Preorder: ";
    for (int i = 0; i < pre.size(); ++i) {
        if (i > 0) cout << " "; // 元素间加空格，行首无空格
        cout << pre[i];
    }
    cout << endl;
    
    return 0;
}

2-7 树的遍历

分数 7

作者 陈越

单位 浙江大学

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

解析

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

const int MAX_NODE = 100;  // 节点值为正整数，100 足够覆盖 N≤30 的场景
int leftChild[MAX_NODE] = {0};  // 存储左孩子，0 表示无孩子
int rightChild[MAX_NODE] = {0}; // 存储右孩子，0 表示无孩子

// 递归构建二叉树，返回当前子树的根节点值
// postS/postE: 后序遍历当前子树的起止索引
// inS/inE: 中序遍历当前子树的起止索引
int buildTree(int postS, int postE, int inS, int inE, 
              vector<int>& post, vector<int>& in, unordered_map<int, int>& inMap) {
    if (postS > postE) {
        return 0;  // 递归终止：当前子树为空
    }

    // 1. 后序遍历的最后一个元素是当前子树的根节点
    int rootVal = post[postE];

    // 2. 找到根节点在中序遍历中的位置，划分左右子树
    int mid = inMap[rootVal];
    int leftLen = mid - inS;  // 左子树的节点个数

    // 3. 递归构建左子树
    int left = buildTree(postS, postS + leftLen - 1, inS, mid - 1, post, in, inMap);
    // 4. 递归构建右子树
    int right = buildTree(postS + leftLen, postE - 1, mid + 1, inE, post, in, inMap);

    // 5. 记录当前根节点的左右孩子
    leftChild[rootVal] = left;
    rightChild[rootVal] = right;

    return rootVal;
}

int main() {
    int n;
    cin >> n;

    vector<int> post(n);  // 后序遍历序列
    vector<int> in(n);    // 中序遍历序列
    unordered_map<int, int> inMap;  // 中序值→索引映射（快速查找根节点）

    // 读取后序遍历
    for (int i = 0; i < n; ++i) {
        cin >> post[i];
    }

    // 读取中序遍历并构建映射
    for (int i = 0; i < n; ++i) {
        cin >> in[i];
        inMap[in[i]] = i;
    }

    // 构建二叉树，获取根节点
    int root = buildTree(0, n - 1, 0, n - 1, post, in, inMap);

    // 层序遍历（BFS）
    queue<int> q;
    vector<int> levelOrder;
    q.push(root);

    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        levelOrder.push_back(curr);  // 访问当前节点

        // 左孩子存在则入队
        if (leftChild[curr] != 0) {
            q.push(leftChild[curr]);
        }
        // 右孩子存在则入队
        if (rightChild[curr] != 0) {
            q.push(rightChild[curr]);
        }
    }

    // 输出结果（行首尾无多余空格）
    for (int i = 0; i < levelOrder.size(); ++i) {
        if (i > 0) {
            cout << " ";
        }
        cout << levelOrder[i];
    }
    cout << endl;

    return 0;
}

2-8 列出叶结点

分数 6

作者 陈越

单位 浙江大学

对于给定的二叉树，本题要求你按从上到下、从左到右的顺序输出其所有叶结点。

输入格式：

首先第一行给出一个正整数 n（≤10），为树中结点总数。树中的结点从 0 到 n−1 编号。随后 n 行，每行给出一个对应结点左右孩子的编号。如果某个孩子不存在，则在对应位置给出 “-”。编号间以 1 个空格分隔。

输出格式：

在一行中按规定顺序输出叶结点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

输出样例：

4 1 5

解析

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

int main() {
    int n;
    cin >> n;

    // 存储每个节点的左右孩子（-1 表示无孩子）
    vector<int> left(n, -1);
    vector<int> right(n, -1);
    vector<bool> is_child(n, false);  // 标记节点是否为某个节点的孩子

    // 1. 读取节点信息，构建二叉树
    for (int i = 0; i < n; ++i) {
        string l, r;
        cin >> l >> r;
        // 处理左孩子
        if (l != "-") {
            left[i] = stoi(l);
            is_child[left[i]] = true;  // 标记该节点为孩子
        }
        // 处理右孩子
        if (r != "-") {
            right[i] = stoi(r);
            is_child[right[i]] = true;  // 标记该节点为孩子
        }
    }

    // 2. 找到根节点（根节点不是任何节点的孩子）
    int root = -1;
    for (int i = 0; i < n; ++i) {
        if (!is_child[i]) {
            root = i;
            break;
        }
    }

    // 3. 层序遍历（BFS），收集叶节点
    vector<int> leaves;
    queue<int> q;
    q.push(root);

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        // 判断是否为叶节点（左右孩子均不存在）
        if (left[curr] == -1 && right[curr] == -1) {
            leaves.push_back(curr);
        } else {
            // 非叶节点，将左右孩子入队（左在前，右在后，保证顺序）
            if (left[curr] != -1) {
                q.push(left[curr]);
            }
            if (right[curr] != -1) {
                q.push(right[curr]);
            }
        }
    }

    // 4. 格式化输出
    for (int i = 0; i < leaves.size(); ++i) {
        if (i > 0) {
            cout << " ";
        }
        cout << leaves[i];
    }
    cout << endl;

    return 0;
}

2-9 哈夫曼编码

分数 8

作者 陈越

单位 浙江大学

给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。例如对字符串"aaaxuaxz"，容易得到字母 ‘a’、‘x’、‘u’、‘z’ 的出现频率对应为 4、2、1、1。我们可以设计编码 {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}，也可以用另一套 {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}，还可以用 {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}，三套编码都可以把原文压缩到 14 个字节。但是 {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} 就不是哈夫曼编码，因为用这套编码压缩得到 00001011001001 后，解码的结果不唯一，“aaaxuaxz” 和 “aazuaxax” 都可以对应解码的结果。本题就请你判断任一套编码是否哈夫曼编码。

输入格式：

首先第一行给出一个正整数 N（2≤N≤63），随后第二行给出 N 个不重复的字符及其出现频率，格式如下：

c[1] f[1] c[2] f[2] ... c[N] f[N]

其中c[i]是集合{‘0’ - ‘9’, ‘a’ - ‘z’, ‘A’ - ‘Z’, ‘_’}中的字符；f[i]是c[i]的出现频率，为不超过 1000 的整数。再下一行给出一个正整数 M（≤1000），随后是 M 套待检的编码。每套编码占 N 行，格式为：

c[i] code[i]

其中c[i]是第i个字符；code[i]是不超过63个’0’和’1’的非空字符串。

输出格式：

对每套待检编码，如果是正确的哈夫曼编码，就在一行中输出"Yes"，否则输出"No"。

注意：最优编码并不一定通过哈夫曼算法得到。任何能压缩到最优长度的前缀编码都应被判为正确。

输入样例：

7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11

输出样例：

Yes
Yes
No
No

解析

#include <iostream>
#include <map>       // 用基础的map存储字符-频率/编码映射（大二重点学过）
#include <queue>     // priority_queue在这个库里面，不是单独的头文件！
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;

    map<char, int> freq_map;  // 字符→频率（map有序，大二更熟悉）
    priority_queue<int, vector<int>, greater<int>> min_heap;  // 小顶堆（求最优总长）

    // 1. 读字符和频率，初始化小顶堆
    for (int i = 0; i < N; ++i) {
        char c;
        int f;
        cin >> c >> f;
        freq_map[c] = f;
        min_heap.push(f);  // 频率入堆，用于计算最优总长
    }

    // 2. 计算哈夫曼最优总长（最小加权路径长度）
    int optimal_len = 0;
    while (min_heap.size() > 1) {
        int f1 = min_heap.top();  // 取最小频率
        min_heap.pop();
        int f2 = min_heap.top();  // 取次小频率
        min_heap.pop();
        int sum_f = f1 + f2;
        optimal_len += sum_f;     // 累加合并代价（最优总长=所有合并和）
        min_heap.push(sum_f);     // 合并后的频率入堆
    }

    int M;
    cin >> M;

    // 3. 检查每套编码
    while (M--) {
        map<char, string> code_map;  // 字符→当前编码
        vector<string> codes;        // 存储所有编码，用于检查前缀
        bool is_valid = true;

        // 3.1 读当前套编码
        for (int i = 0; i < N; ++i) {
            char c;
            string code;
            cin >> c >> code;
            code_map[c] = code;
            codes.push_back(code);
        }

        // 3.2 验证条件1：编码总长是否等于最优总长
        int current_len = 0;
        for (auto it = freq_map.begin(); it != freq_map.end(); ++it) {
            char c = it->first;
            int f = it->second;
            current_len += code_map[c].size() * f;  // 编码长度×频率求和
        }
        if (current_len != optimal_len) {
            cout << "No" << endl;
            continue;
        }

        // 3.3 验证条件2：是否为前缀编码（排序后查相邻）
        sort(codes.begin(), codes.end());  // 字典序排序，前缀必在相邻
        for (int i = 0; i < codes.size() - 1; ++i) {
            string prev = codes[i];
            string curr = codes[i+1];
            // 前一个是后一个的前缀 → 不合法
            if (curr.substr(0, prev.size()) == prev) {
                is_valid = false;
                break;
            }
        }

        cout << (is_valid ? "Yes" : "No") << endl;
    }

    return 0;
}

2-10 到底爱不爱我

分数 10

作者 陈越

单位 浙江大学

古代少女有了心上人时，会悄悄折一条树枝，揪那枝上的叶子，揪一片叶子念一句“爱我”，再揪一片念一句“不爱我”…… 这样揪落最后一片叶子的时候，看看是停在“爱”还是“不爱”。

但聪明的慧娘一眼洞穿，只要数一下叶子有多少片，根据这个数字的奇偶性判断是以“爱”开始还是以“不爱”开始，就总是可以最后落在“爱”上。这个游戏顿时就变得无趣了 —— 真的是文科生制造浪漫，理科生杀死浪漫。

于是有着工科生大脑的慧娘打算另外制作一个更有趣的浪漫游戏。她用不同植物的枝条做成了三种“情枝”：

• “专情枝”：是一根有两个分岔的树枝，只有当两个分岔上连接的枝条传过来的情话都是“爱”的时候，这根枝条的根部才传出“爱”；否则树枝根部传出的是“不爱”。
• “博爱枝”：也是一根有两个分岔的树枝，只有当两个分岔上连接的枝条传过来的情话都是“不爱”的时候，这根枝条的根部才传出“不爱”；否则树枝根部传出的都是“爱”。
• “情变枝”：是没有分岔的一根直枝，如果一端接到“爱”，另一端必须传出“不爱”；反之如果一端接到“不爱”，另一端则会传出“爱”。

慧娘将这些树枝摆放在院子里，布了一个“情阵”，先选一根特殊的枝条作为初试一枝，从这枝条的根部开始，扩散开去，令它们根枝相连。然后她在末梢的枝杈旁随意写下“爱”或“不爱”。现在请你写个程序帮她算出来，在初始一枝的根部，她能得到“爱”还是“不爱”？

输入格式：

输入在第一行中给出正整数 N（≤30），是慧娘制作的情枝数量。这里假设她将所有的情枝从 1 到 N 做好了编号。随后 N 行，第 i 行给出第 i 枝的描述，格式为

类型 左分枝连接的编号 右分枝连接的编号

其中 类型 为 1 代表专情、2 代表博爱、3 代表情变。当然如果是情变枝，则后面跟的是其唯一末端连接的情枝编号，并没有两个分枝的信息。如果一个分枝是末梢，并没有连接其它枝条，则对应编号为 0。

接下来一行中给出正整数 K（≤30），是慧娘询问的次数。以下 K 行，每行给出一个由 0 和 1 组成的字符串，其中 0 表示“不爱”，1 表示“爱”—— 这是慧娘从左到右在每个枝杈末梢处写下的。（注意：“从左到右”的意思是，我们从初试一枝出发去遍历所有枝条的末梢时，总是遵循先遍历左边情阵、再遍历右边情阵的顺序）

输出格式：

对慧娘的每个询问，如果她在初始一枝的根部能得到“爱”，就输出 Ai；否则输出 BuAi。

输入样例：

6
2 6 4
1 0 0
3 1
2 0 0
3 0
1 5 2
5
11111
00000
11100
10011
01100

输出样例：

BuAi
Ai
Ai
BuAi
BuAi

样例说明：

样例对应的情阵以及慧娘第 3 问的情势如图所示，其中完整的心对应 1，裂开的心对应 0。

解析

#include <iostream>
#include <vector>
#include <unordered_map>
#include <functional>
#include <string>
using namespace std;

// 情枝结构体：存储类型和连接关系
struct Branch {
    int type;       // 1=专情，2=博爱，3=情变
    int left, right;// 类型1/2用：左/右连接的枝编号（0=末梢）
    int next;       // 类型3用：唯一连接的枝编号（0=末梢）
};

const int MAXN = 31;  // N≤30，编号1~30
Branch branches[MAXN]; // 存储所有情枝
int in_degree[MAXN] = {0}; // 记录每个枝的入度（找初始枝用）
int root = -1;        // 初始枝（根节点）编号

vector<string> leaves; // 存储末梢标识（顺序=输入字符串顺序）
unordered_map<string, int> leaf_index; // 末梢标识→输入字符串索引

// DFS收集末梢：从初始枝出发，先左后右遍历，记录末梢顺序
void dfs_collect_leaves(int id) {
    Branch& b = branches[id];
    if (b.type == 1 || b.type == 2) { // 专情/博爱枝：先左后右
        // 处理左分枝
        if (b.left == 0) {
            string key = to_string(id) + "_0"; // 末梢标识：枝id_左分枝
            leaves.push_back(key);
            leaf_index[key] = leaves.size() - 1; // 记录输入字符串中的索引
        } else {
            dfs_collect_leaves(b.left);
        }
        // 处理右分枝
        if (b.right == 0) {
            string key = to_string(id) + "_1"; // 末梢标识：枝id_右分枝
            leaves.push_back(key);
            leaf_index[key] = leaves.size() - 1;
        } else {
            dfs_collect_leaves(b.right);
        }
    } else if (b.type == 3) { // 情变枝：唯一分枝
        if (b.next == 0) {
            string key = to_string(id) + "_2"; // 末梢标识：枝id_情变分枝
            leaves.push_back(key);
            leaf_index[key] = leaves.size() - 1;
        } else {
            dfs_collect_leaves(b.next);
        }
    }
}

int main() {
    int N;
    cin >> N;

    // 1. 读取情枝信息，构建结构并计算入度
    for (int i = 1; i <= N; ++i) {
        cin >> branches[i].type;
        if (branches[i].type == 1 || branches[i].type == 2) {
            cin >> branches[i].left >> branches[i].right;
            // 更新入度：被连接的枝入度+1
            if (branches[i].left != 0) in_degree[branches[i].left]++;
            if (branches[i].right != 0) in_degree[branches[i].right]++;
        } else if (branches[i].type == 3) {
            cin >> branches[i].next;
            if (branches[i].next != 0) in_degree[branches[i].next]++;
        }
    }

    // 2. 找到初始枝（入度为0：没有被任何枝连接）
    for (int i = 1; i <= N; ++i) {
        if (in_degree[i] == 0) {
            root = i;
            break;
        }
    }

    // 3. 收集末梢，确定输入字符串的顺序
    dfs_collect_leaves(root);

    // 4. 处理K个询问
    int K;
    cin >> K;
    while (K--) {
        string s;
        cin >> s;
        // 构建末梢值映射：末梢标识→0（不爱）/1（爱）
        unordered_map<string, int> leaf_val;
        for (string& key : leaves) {
            int idx = leaf_index[key]; // 找到输入字符串中的位置
            leaf_val[key] = (s[idx] == '1') ? 1 : 0;
        }

        // 递归计算某个枝的输出值（记忆化搜索，避免重复计算）
        unordered_map<int, int> memo; // 缓存枝id→输出值
        function<int(int)> compute = [&](int id) -> int {
            if (memo.count(id)) return memo[id]; // 已计算过，直接返回
            int res;
            Branch& b = branches[id];

            if (b.type == 3) { // 情变枝：输入值取反
                if (b.next == 0) { // 连接末梢
                    string key = to_string(id) + "_2";
                    res = 1 - leaf_val[key];
                } else { // 连接其他枝，递归计算
                    res = 1 - compute(b.next);
                }
            } else if (b.type == 1) { // 专情枝：左右都为1才输出1
                int left_val, right_val;
                // 计算左分枝值
                if (b.left == 0) {
                    string key = to_string(id) + "_0";
                    left_val = leaf_val[key];
                } else {
                    left_val = compute(b.left);
                }
                // 计算右分枝值
                if (b.right == 0) {
                    string key = to_string(id) + "_1";
                    right_val = leaf_val[key];
                } else {
                    right_val = compute(b.right);
                }
                res = (left_val && right_val) ? 1 : 0;
            } else { // 博爱枝：左右都为0才输出0
                int left_val, right_val;
                if (b.left == 0) {
                    string key = to_string(id) + "_0";
                    left_val = leaf_val[key];
                } else {
                    left_val = compute(b.left);
                }
                if (b.right == 0) {
                    string key = to_string(id) + "_1";
                    right_val = leaf_val[key];
                } else {
                    right_val = compute(b.right);
                }
                res = (left_val == 0 && right_val == 0) ? 0 : 1;
            }

            memo[id] = res; // 缓存结果
            return res;
        };

        // 计算初始枝的输出值，输出结果
        int result = compute(root);
        cout << (result == 1 ? "Ai" : "BuAi") << endl;
    }

    return 0;
}

2-11 创建哈夫曼树

分数 5

作者 陈越

单位 浙江大学

请编写程序，根据给定的权重值序列，构建哈夫曼树，并计算带权路径长度。

输入格式：

输入首先给出一个不超 20 的正整数 n，随后一行给出 n 个权重值。其中权重值都是不超过 100 的正整数。

输出格式：

在一行中输出哈夫曼树的带权路径长度。

输入样例：

5
1 2 3 4 5

输出样例：

33

解析

#include <iostream>
#include <queue>   // 优先级队列（小顶堆）在此库中
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    // 1. 定义小顶堆（每次能快速取出最小的两个权重）
    // priority_queue默认是大顶堆，加greater<int>改成小顶堆
    priority_queue<int, vector<int>, greater<int>> min_heap;

    // 2. 读取所有权重，存入小顶堆
    for (int i = 0; i < n; ++i) {
        int weight;
        cin >> weight;
        min_heap.push(weight);
    }

    int wpl = 0;  // 带权路径长度（最终结果）

    // 3. 构建哈夫曼树，计算WPL
    // 循环条件：堆中节点数 > 1（直到合并成一个根节点）
    while (min_heap.size() > 1) {
        // 取出两个权重最小的节点
        int min1 = min_heap.top();
        min_heap.pop();
        int min2 = min_heap.top();
        min_heap.pop();

        // 合并节点：新节点权重 = 两个子节点权重之和
        int new_weight = min1 + min2;

        // 关键：哈夫曼树的WPL = 所有合并节点的权重之和
        wpl += new_weight;

        // 把合并后的新节点放回堆中，继续下一轮合并
        min_heap.push(new_weight);
    }

    // 4. 输出带权路径长度
    cout << wpl << endl;

    return 0;
}