CCF-GESP 等级考试 2025年12月认证C++六级真题解析

1 单选题（每题 2 分，共 30 分）

第1题 在面向对象编程中，下列关于 虚函数 的描述中，错误的是（   ）。

A. 虚函数用于支持运行时多态

B. 通过基类指针调用虚函数时，会根据对象实际类型决定调用版本

C. 构造函数可以声明为虚函数以支持多态

D. 基类析构函数常声明为虚函数以避免资源泄漏

解析：答案C。虚函数是实现运行时多态的关键机制，通过基类指针调用时会动态绑定到派生类实现,A正确。通过基类指针调用虚函数时，会根据对象实际类型决定调用版本是虚函数的核心特性，称为动态绑定或后期绑定，B正确。构造函数不能声明为虚函数，这是C++标准规定，C错误。虚析构函数确保派生类资源被正确释放，D正确。故选C。

第2题 执行如下代码，会输出 钢琴：叮咚叮咚 和 吉他：咚咚当当 。这体现了面向对象编程的（   ）特性。

class Instrument { public:     virtual void play() {         cout << "乐器在演奏声音" << endl;     }     virtual ~Instrument() {} }; class Piano : public Instrument { public:     void play() override {         cout << "钢琴：叮咚叮咚" << endl;     } }; class Guitar : public Instrument { public:     void play() override {         cout << "吉他：咚咚当当" << endl;     } }; int main() {     Instrument* instruments[2];     instruments[0] = new Piano();     instruments[1] = new Guitar();     for (int i = 0; i < 2; ++i) {         instruments[i]->play();     }     for (int i = 0; i < 3; ++i) {         delete instruments[i];     }     return 0; }

A. 继承                                B. 封装                                C. 多态                               D. 链接

解析：答案C。该代码通过多态性实现了不同乐器的特定演奏方式。具体分析如下：‌基类与派生类‌：Instrument 是基类，定义了 play() 方法。Piano 和 Guitar 是派生类，分别重写了 play() 方法，输出特定的演奏声。‌多态性体现‌：在 main() 函数中，Instrument* instruments[2] 声明了一个基类指针数组。将 Piano 和 Guitar 对象赋值给该数组，但通过基类指针调用 play() 方法。由于 play() 方法被声明为 virtual，实际调用的是派生类的重写方法，输出：钢琴：叮咚叮咚、吉他：咚咚当当。所以是多态。故选C。

第3题 关于以下代码，说法正确的是（   ）。

class Instrument { public:     void play() {         cout << "乐器在演奏声音" << endl;     }     virtual ~Instrument() {} }; class Piano : public Instrument { public:     void play() override {         cout << "钢琴：叮咚叮咚" << endl;     } }; class Guitar : public Instrument { public:     void play() override {         cout << "吉他：咚咚当当" << endl;     } }; int main() {     Instrument* instruments[2];     instruments[0] = new Piano();     instruments[1] = new Guitar();     for (int i = 0; i < 2; ++i) {         instruments[i]->play();     }     for (int i = 0; i < 3; ++i) {         delete instruments[i];     }     return 0; }

A. 执行代码会输出两行，内容分别为： 钢琴：叮咚叮咚 和 吉他：咚咚当当

B. 执行代码会输出两行，内容分别为： 乐器在演奏声音 和 乐器在演奏声音

C. 代码编译出现错误

D. 代码运行出现错误

解析：答案C。程序代码，在基类 Instrument 中，play 成员函数未被声明为 virtual，因此不具备多态性。派生类 Piano 和 Guitar 中的 play 函数使用了 override 关键字，但基类中不存在可覆盖的虚函数 play，这会导致编译错误。所以C正确。故选C。

第4题 某文本编辑器把用户输入的字符依次压入栈 S。用户依次输入 A , B , C , D 后，用户按了两次撤销（每次 撤销，弹出栈顶一个字符）。此时栈从栈底到栈顶的内容是：（   ）。

A. A B                                    B. A B C                                C. A B D                             D. B C

解析：答案A。根据题目描述，用户依次输入字符 A, B, C, D 后，栈的内容为 A, B, C, D（从栈底到栈顶）。用户按了两次撤销操作，每次撤销会弹出栈顶字符。因此，撤销两次后，栈顶的 D 和 C 被弹出，栈中剩余的字符为 A, B。故选A。

第5题 假设循环队列数组长度为 N ，其中队空判断条件为： front == rear ，队满判断条件为： (rear + 1) % N == front ，出队对应的操作为： front = (front + 1) % N ，入队对于的操作为： rear = (rear + 1) % N 。循环队列长度 N = 6 ，初始 front = 1 , rear = 1 ，执行操作序列为：入队, 入队, 入队, 出队, 入队, 入队， 则最终 (front, rear) 的值是（   ）。

A. (2, 5)                                 B. (2, 0)                               C. (3, 5)                             D. (3, 0)

解析：答案B。根据题目描述的循环队列操作规则，我们逐步分析执行操作序列后的状态变化：‌初始状态‌：front = 1, rear = 1；‌入队‌：rear = (rear + 1) % 6 = 2；‌入队‌：rear = (rear + 1) % 6 = 3；‌入队‌：rear = (rear + 1) % 6 = 4；‌出队‌：front = (front + 1) % 6 = 2；‌入队‌：rear = (rear + 1) % 6 = 5；‌入队‌：rear = (rear + 1) % 6 = 0。最终状态：front = 2, rear = 0。故选B。

第6题 以下函数 check() 用于判断一棵二叉树是否为（   ）。

bool check(TreeNode* root) {     if (!root) return true;     queue<TreeNode*> q;     q.push(root);     bool hasNull = false;     while (!q.empty()) {         TreeNode* cur = q.front(); q.pop();         if (!cur) {             hasNull = true;         } else {             if (hasNull) return false;             q.push(cur->left);             q.push(cur->right);         }     }     return true; }

A. 满二叉树                       B. 完全二叉树                  C. 二叉搜索树                    D. 平衡二叉树

解析：答案B。程序代码使用队列，使用广度优先搜索（BFS）遍历二叉树，通过队列记录节点，按层序遍历，遇到空节点后，后续节点必须全为空。若违反此规则，返回false。该算法判断二叉树是否为完全二叉树。故选B。

第7题 以下代码实现了二叉树的（   ）。

void traverse(TreeNode* root) {     if (!root) return;     traverse(root->left);     traverse(root->right);     cout << root->val << " "; }

A. 前序遍历                       B. 中序遍历                      C. 后序遍历                            D. 层序遍历

解析：答案C。程序代码实现二叉树的后序遍历（左-右-根），递归访问左子树，递归访问右子树，访问根节点并输出值，无显式栈或队列辅助结构。故选C。

第8题 下面代码实现了哈夫曼编码，则横线处应填写的代码是（   ）。

struct Symbol {     char ch;        //字符     long long freq; //频率     string code;    //哈夫曼编码 }; struct Node {    long long w; //权值     int l, r; //左右孩子（节点下标），-1 表示空     int sym; // 叶子对应符号下标；内部节点为 -1     Node(long long _w=0, int _l=-1, int _r=-1, int _sym=-1)         : w(_w), l(_l), r(_r), sym(_sym) {} }; // 从 A(leafIdx) 和 B(internalIdx) 的队首取最小的一个节点下标 static int PopMinNode(const vector<Node>& nodes,                       const vector<int>& leafIdx, int n, int& pA,                       const vector<int>& internalIdx, int& pB) {     if (pA < n && (pB >= (int)internalIdx.size() ||                    nodes[leafIdx[pA]].w <= nodes[internalIdx[pB]].w)) {         return leafIdx[pA++];     }     else {         return internalIdx[pB++];     } } // DFS 生成编码（左 0，右 1） static void DFSBuildCodes(int u, const vector<Node>& nodes, Symbol sym[], string& path) {     if (u == -1) return;     if (nodes[u].sym != -1) { // 叶子         sym[nodes[u].sym].code = path;         return;     }     path.push_back('0');     DFSBuildCodes(nodes[u].l, nodes, sym, path);     path.pop_back();     path.push_back('1');     DFSBuildCodes(nodes[u].r, nodes, sym, path);     path.pop_back(); } int BuildHuffmanCodes(Symbol sym[], int n) {     for (int i = 0; i < n; i++) sym[i].code.clear();     if (n <= 0) return -1;     // 只有一个字符：约定编码为 "0"     if (n == 1) {         sym[0].code = "0";         return 0;     }     vector<Node> nodes;     nodes.reserve(2 * n);     // 1) 建立叶子节点     vector<int> leafIdx(n);     for (int i = 0; i < n; i++) {            leafIdx[i] = (int)nodes.size();         nodes.push_back(Node(sym[i].freq, -1, -1, i));     }     // 2) 叶子按权值排序（A 队列）     sort(leafIdx.begin(), leafIdx.end(),          [&](int a, int b) {             if (nodes[a].w != nodes[b].w) return nodes[a].w < nodes[b].w;             return nodes[a].sym < nodes[b].sym; // 稳定一下          });     // B 队列（内部节点下标队列）     vector<int> internalIdx;     internalIdx.reserve(n);     int pA = 0, pB = 0;     // 3) 合并 n-1 次     for (int k = 1; k < n; k++) {         int x = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);         int y = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);         int z = (int)nodes.size();         ________________________ // 在此处填写代码     }     int root = internalIdx.back();     // 4) DFS 生成编码     string path;     DFSBuildCodes(root, nodes, sym, path);     return root; }

A.

nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1)); internalIdx.push_back(z);

B.

nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1)); leafIdx.push_back(z);

C.

internalIdx.push_back(z); nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y));

D.

nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y)); leafIdx.push_back(z);

解析：答案A。程序代码创建新节点：合并两个子节点x和y，权值为它们之和，左右孩子分别为x和y，标记为非叶子节点（sym=-1）。内部节点队列添加：新节点加入内部节点队列，用于后续合并。符合哈夫曼树构建规则：每次合并最小权值节点，生成新节点并更新队列，选择A选项：符合哈夫曼编码标准实现，确保正确构建最优编码树。故选A。

第9题 以下关于哈夫曼编码的说法，正确的是（   ）。

A. 哈夫曼编码是定长编码

B. 哈夫曼编码中，没有任何一个字符的编码是另一个字符编码的前缀

C. 哈夫曼编码一定唯一

D. 哈夫曼编码不能用于数据压缩

解析：答案B。哈夫曼编码是一种‌无损数据压缩算法‌，通过为高频字符分配短编码、低频字符分配长编码，实现高效压缩。其核心是构建哈夫曼树，确保编码无前缀冲突，广泛用于文件压缩（如ZIP）和通信协议。所以B正确。故选B。

第10题 以下函数实现了二叉排序树（BST）的（   ）操作。

TreeNode* op(TreeNode* root, int x) {     if (!root) return new TreeNode(x);     if (x < root->val)         root->left = op(root->left, x);     else         root->right = op(root->right, x);     return root; }

A. 查找                                B. 插入                                C. 删除                              D. 遍历

解析：答案B。程序代码实现二叉搜索树的插入操作：递归查找插入位置，保持BST性质：左子树<根<右子树，插入新节点后返回根节点。所以B正确。故选B。

第11题 下列代码实现了树的深度优先遍历，则横线处应填入（   ）。

struct TreeNode {     int val;     TreeNode* left;     TreeNode* right;     TreeNode(int x): val(x), left(nullptr), right(nullptr) {} }; void dfs(TreeNode* root) {     if (!root) return;     stack<TreeNode*> st;     st.push(root);     while (!st.empty()) {         TreeNode* node = st.top(); st.pop();         cout << node->val << " ";         if (node->right) st.push(node->right);         ________________________     } }

A. if (node->left) st.push(node->left);                        B. if (node->left) st.pop(node->left);

C. if (node->left) st.front(node->left);                        D. if (node->left) st.push(node->right);

解析：答案A。程序代码实现了树的深度优先遍历算法：使用栈结构存储待访问节点，先访问右子节点再访问左子节点（符合深度优先特性），横线处应填入访问左子节点的语句，if (node->left) st.push(node->left); 以正确实现遍历逻辑。所以A正确。故选A。

第12题 给定一棵普通二叉树（节点值没有大小规律），下面代码判断是否存在值为 x 的结点，则横线处应填入（   ）。

struct TreeNode {     int val;     TreeNode* left;     TreeNode* right;     TreeNode(int x): val(x), left(nullptr), right(nullptr) {} }; TreeNode* bfsFind(TreeNode* root, int x) {     if (!root) return nullptr;     queue<TreeNode*> q;     q.push(root);     while (!q.empty()) {         TreeNode* cur = q.front(); q.pop();         if (cur->val == x) return cur;         ________________________     }     return nullptr; }

A. q.push(cur);                                                                  B. if (cur->right) q.push(cur->right);

C.

if (cur->left)     q.push(cur->left); if (cur->right)     q.push(cur->right);

D.

q.push(cur->left); q.push(cur->right);

解析：答案C。程序代码实现广度优先搜索（BFS）遍历二叉树，使用队列存储待访问节点，检查当前节点值是否等于目标值x，将非空子节点（左/右）加入队列，适用于普通二叉树（无节点值大小规律）。‌BFS遍历原理‌：广度优先搜索需按层级遍历节点，需将当前节点的‌非空子节点‌加入队列。选项C通过条件判断确保：左子节点存在时入队（if (cur->left) q.push(cur->left);），右子节点存在时入队（if (cur->right) q.push(cur->right);）。q.push(cur) 会导致当前节点重复入队，形成死循环，A错误。if (cur->right) q.push(cur->right) 忽略左子树，遍历不完整，B错误。q.push(cur->left); q.push(cur->right); 未判空，若子节点为空则队列引入非法空指针，引发运行时错误，D错误。选项C严格检查子节点非空后才入队，确保：所有有效节点被遍历，避免空指针访问。故选C。

第13题 在二叉排序树（Binary Search Tree, BST）中，假设节点值互不相同。给定如下搜索函数，以下说法一定正确的是（   ）。

bool find(Node* root, int x) { while (root) {     if (root->val == x) return true;         root = (x < root->val) ? root->left : root->right;     }     return false; }

A. 最坏情况下，访问结点数是𝑂(log 𝑛)

B. 最坏情况下，访问结点数是𝑂(𝑛)

C. 无论如何，访问结点数都不超过树高的一半

D. 一定比在普通二叉树中搜索快

解析：答案B。在二叉排序树（BST）中，给定搜索函数的行为和特性如下分析：‌BST可能退化‌：当插入节点按顺序递增或递减时，BST会退化成单链表（例如根节点为1，后续插入2、3、4...）。‌最坏时间复杂度‌：此时搜索需遍历所有节点（如查找最大值需访问全部𝑛个节点），时间复杂度为𝑂(𝑛)。𝑂(log 𝑛)仅在平衡BST（如AVL树）中成立，但题目未保证平衡性，A错误。当BST退化为链表时，搜索叶节点需访问𝑛个节点，而树高为𝑛，𝑛 > 𝑛/2，故C错误。普通二叉树搜索（如BFS）最坏也是𝑂(𝑛)，且BST退化时性能相同，故D错误。故选B。

第14题 0/1 背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。则下面说法正确的是（   ）。

for each item (w, v):     for (int j = W; j >= w; --j)         dp[j] = max(dp[j], dp[j-w] + v);

A. 内层 j 必须从小到大，否则会漏解

B. 内层 j 必须从大到小，否则同一件物品会被用多次

C. j 从大到小或从小到大都一样

D. 只要 dp 初始为 0 ，方向无所谓

解析：答案B。‌‌状态依赖特性‌：一维 dp[j] 表示容量 j 下的最大价值。更新 dp[j] 时需依赖 ‌未更新‌ 的 dp[j - w[i]]（即前一轮物品的状态）。‌遍历方向的影响‌：‌从大到小遍历‌（j=m to w[i]）：更新 dp[j] 时，dp[j - w[i]] 仍为上一物品状态，确保物品仅使用 ‌一次‌（0/1背包）。‌从小到大遍历‌（j=w[i] to m）：p[j - w[i]] 可能已被当前物品更新过，导致同一物品被重复使用（转化为 ‌完全背包‌ 逻辑）。‌若从小到大遍历，会重复使用物品（漏解≠重复使用），A错误。内层 j 必须从大到小，否则同一件物品会被用多次‌，B正确。方向不同导致结果不同（0/1背包≠完全背包），C错误。初始值无法避免状态依赖错误，D错误。故选B。

第15题 以下关于动态规划的说法中，错误的是（   ）。

A. 动态规划方法通常能够列出递推公式。

B. 动态规划方法的时间复杂度通常为状态的个数。

C. 动态规划方法有递推和递归两种实现形式。

D. 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。

解析：答案B。‌‌关于动态规划，其核心是定义状态和状态转移方程（递推公式）。对于大多数动态规划问题（如背包问题、斐波那契数列等），递推公式是设计解决方案的基础。所以A正确。动态规划的时间复杂度取决于两个因素：状态的个数和每个状态转移所需的时间。如果每个状态转移的时间复杂度为𝑂(1)，则总时间复杂度通常与状态个数成正比。然而，在许多问题中，状态转移的时间复杂度不是𝑂(1)，例如：在最长回文子序列问题中，状态转移可能涉及复杂的操作，时间复杂度不仅取决于状态个数，所以B错误，因为它忽略了状态转移的时间复杂度，仅考虑状态个数是不准确的。动态规划的实现方式包括：‌自顶向下（递归实现）‌：使用递归加记忆化（memoization）来避免重复计算；‌自底向上（递推实现）‌：使用迭代方式从基础状态逐步计算到目标状态，两种形式均被广泛使用，所以C正确。对于同一动态规划问题，递归实现（带记忆化）和递推实现的时间复杂度在渐近意义下（asymptotically）通常相同，因为记忆化确保每个状态只计算一次。尽管递归实现可能有额外的函数调用开销（常数因子差异），但大𝑂表示法下的时间复杂度是相同的，所以D正确。故选‌B‌。

2 判断题（每题 2 分，共 20 分）

第1题 以下代码中，构造函数被调用的次数是1次。

class Test { public:     Test() { cout << "T "; } }; int main() {     Test a;     Test b = a; }

‌解析：答案╳(错误)。‌Test a;‌：直接初始化对象 a，调用用户定义的默认构造函数 Test()，输出 "T "。这是用户定义构造函数的唯一一次调用。‌Test b = a;‌：这是拷贝初始化，调用编译器隐式生成的默认拷贝构造函数（因为用户未定义拷贝构造函数）。隐式拷贝构造函数‌不会调用用户定义的默认构造函数‌，且无输出。因此，输出结果仅为 "T "（一次），但构造函数总调用次数为：用户定义的默认构造函数：1次；隐式拷贝构造函数：1次（无用户定义行为）。共2次。故错误。

第2题 面向对象编程中，封装是指将数据和操作数据的方法绑定在一起，并对外隐藏实现细节。

解析：答案√(正确)。在面向对象编程中，封装的核心机制包括：‌数据与方法的绑定‌，将数据（属性）和操作这些数据的方法（函数）整合为一个独立的类单元，形成自包含的逻辑实体。‌对外隐藏实现细节，通过访问控制（如 private 或 protected 修饰符）限制外部直接访问内部数据，仅暴露必要的公共接口（如公共方法）。目的：防止非法修改，降低模块间耦合，提升代码安全性和可维护性。故正确。

第3题 以下代码能够正确统计二叉树中叶子结点的数量。

int countLeaf(TreeNode* root) {     if (!root) return 0;     if (!root->left && !root->right) return 1;     return countLeaf(root->left) + countLeaf(root->right); }

解析：答案√(正确)。题目中的程序代码‌递归终止条件：若节点为空（!root），返回 0（空树无叶子节点）。若当前节点为叶子节点（无左、右子节点，即 !root->left && !root->right），返回 1。‌递归分解问题：对非叶子节点，递归计算左子树和右子树的叶子节点数，并求和：return countLeaf(root->left) + countLeaf(root->right);。故正确。

第4题 广度优先遍历二叉树可用栈来实现。

‌解析：答案╳(错误)。广度优先遍历二叉树是用队列来实现。故错误。

第5题 函数调用管理可用栈来管理。

解析：答案√(正确)。在计算机程序中，函数调用管理‌确实通过栈来实现‌，这是现代编程语言的核心机制。函数调用栈的工作原理：‌函数调用时‌，当前函数的‌返回地址‌、‌局部变量‌和‌参数‌被压入栈顶（称为"栈帧"），CPU寄存器状态同时保存（如x86架构的ESP/EBP寄存器）；‌函数执行中‌，被调用函数在自己的栈帧内操作数据，嵌套调用时重复步骤，形成‌栈帧链。‌函数返回时，弹出当前栈帧，恢复调用方寄存器和栈指针，跳转回保存的返回地址继续执行。故正确。

第6题 在二叉排序树（BST）中，若某结点的左子树为空，则该结点一定是整棵树中的最小值结点。

解析：答案╳(错误)。在二叉排序树（BST）中，若某结点的左子树为空，该结点不一定是整棵树的最小值结点。BST的最小值结点始终是树中最左边的结点（即从根结点开始沿左子树递归下移直到左子树为空的结点）。只有当该结点恰好是整棵树的最左边结点时，其左子树为空才意味着它是最小值结点；否则，可能存在其他结点值更小。故错误。

第7题 下面的函数能正确判断一棵树是不是二叉排序树（左边的数字要比当前数字小，右边的数字要比当前数字大）。

bool isBST(TreeNode* root, int minVal, int maxVal) {     if (!root) return true;     if (root->val <= minVal || root->val >= maxVal)         return false;     return isBST(root->left, minVal, root->val) &&     isBST(root->right, root->val, maxVal); }

解析：答案√(正确)。该函数 isBST 旨在判断二叉树是否为二叉排序树（BST），但存在‌边界值缺陷。二叉排序树的定义要求：对于每个节点，其左子树所有节点值‌严格小于‌该节点值，右子树所有节点值‌严格大于‌该节点值（通常假设无重复值）。函数使用递归方法，通过 minVal 和 maxVal 参数传递当前节点值的允许范围（开区间 (minVal, maxVal)）：若当前节点值超出范围（root->val <= minVal || root->val >= maxVal），返回 false。递归检查左子树时，更新范围 (minVal, root->val)；右子树时，更新范围 (root->val, maxVal)。算法逻辑本身正确。

‌边界值问题导致错误：函数使用 int 类型表示范围边界（minVal 和 maxVal）。当二叉树包含极值（如 INT_MIN 或 INT_MAX）时，函数可能错误返回 false。‌逻辑正确，但未考虑特殊性，除极端情况，正确。

第8题 格雷编码相邻两个编码之间必须有多位不同，以避免数据传输错误。

解析：答案╳(错误)。格雷编码（Gray Code）的核心特性是‌相邻两个编码之间仅有1位不同，这是其避免数据传输错误的关键设计。故错误。

第9题 小杨在玩一个闯关游戏，从第1 关走到第4 关。每一关的体力消耗如下（下标表示关卡编号）： cost = [ 0, 3, 5, 2, 4 ] ，其中 cost[i] 表示到达第i 关需要消耗的体力， cost[0]=0 表示在开始状态，体力消耗为 0。小杨每次可以从当前关卡前进 1 步或 2 步。按照上述规则，从第1 关到第4 关所需消耗的最小体力为7。

解析：答案╳(错误)。从第1 关可以走1步到第2关，消耗5，如走2步到第3关消耗2；再从第3关到第4关消耗4，合计6，不是7。故错误。

第10题 假定只有一个根节点的树的深度为1，则一棵有𝑛个节点的完全二叉树，则树的深度为⌊log₂𝑛⌋+1。

解析：答案√(正确)。设完全二叉树的深度(高度)为h，则节点数n满足：2ʰ⁻¹ ≤ n ≤ 2ʰ-1。

将上述不等式取对数：h-1 <= log₂(n) < h，因此，h = ⌊log₂(n)⌋ + 1。因此，这个结论是正确的。故正确。

3 编程题（每题 25 分，共 50 分）

3.1 编程题1

• 试题名称：路径覆盖
• 时间限制：1.0 s
• 内存限制：512.0 MB

3.1.1题目描述

给定一棵有𝑛个结点的有根树𝑇，结点依次以1, 2, ..., 𝑛编号，根结点编号为1。方便起见，编号为𝑖的结点称为结点𝑖。

初始时𝑇中的结点均为白色。你需要将𝑇中的若干个结点染为黑色，使得所有叶子到根的路径上至少有一个黑色结点。将结点𝑖染为黑色需要代价𝑐ᵢ，你需要在满足以上条件的情况下，最小化染色代价之和。

叶子是指𝑇中没有子结点的结点。

3.1.2 输入格式

第一行，一个正整数𝑛，表示结点数量。

第二行，𝑛-1个正整数𝑓₂, 𝑓₃, ..., 𝑓ₙ，其中𝑓ᵢ表示结点𝑖的父结点的编号，保证𝑓ᵢ≤𝑖。

第三行，𝑛个正整数𝑐₁, 𝑐₂, ..., 𝑐ₙ，其中𝑐ᵢ表示将结点𝑖染为黑色所需的代价。

3.1.3 输出格式

一行，一个整数，表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下，染色代价之和的最小值。

3.1.4 样例

3.1.4.1 输入样例1

4 1 2 3 5 6 2 3

3.1.4.2 输出样例1

2

3.1.4.3 输入样例2

7 1 1 2 2 3 3 64 16 15 4 3 2 1

3.1.4.4 输出样例2

10

3.1.5 数据范围

对于40%的测试点，保证2≤𝑛≤16。

对于另外20%的测试点，保证𝑓ᵢ=𝑖-1。

对于所有测试点，保证2≤𝑛≤10⁵，1≤𝑐ᵢ≤10⁹。

3.1.6 编写程序

编程思路：这是一个典型的树形DP问题，需要在有根树上选择一些节点染黑，使得：

  1. 每个叶子节点到根节点的路径上至少有一个黑色节点

  2. 最小化染色代价之和

关键点理解

  1. 叶子节点：没有子节点的节点

  2. 路径要求：每个叶子到根的路径都要被“覆盖”(至少有一个黑点)

  3. 代价最小化：每个节点染色有不同代价

状态定义

dp[i]：以节点i为根的子树，满足该子树内所有叶子节点到i的路径上至少有一个黑色节点的最小代价。

状态转移

  1. 如果i是叶子节点：

    路径只有i自己，所以必须染色i，代价

        dp[i] = cost[i]

  2．如果i不是叶子节点：

   染黑当前节点i，代价为cost[i]。染黑i后，所有经过i的路径都满足条件，不需要考虑子树

    不染黑当前节点i，代价为所有子节点的dp[i)之和。因为i不黑，所以每个子树必须自己保证覆盖

    每棵子树的dp[i]已经保证了i的子树内叶子到i的路径有黑点

    由于路径是从叶子到i，且经过各路径，所以这个黑点也覆盖了到i的路径

      dp[i] = min(c[i], dp[i]) // 其中右边的dp为各路径中染黑最小代价和

如果不是根结点，将dp[i](自己的最小代价加给父结点)

方法一：根结节为1，孩子结点编号大于1。先构造各结点的孩子数，孩子数为0即是叶子结点。从叶子结点向上计算染黑最小代码，并加到其父结点，直到根结点(不含根结点)，根结点的dp值就是答案。注意𝑐ᵢ≤10⁹，所以𝑐ᵢ的和dp要用long long。

算法与“数堆”相似。参考程序代码如下：

#include <iostream> using namespace std; const int N = 100005;  // 𝑛≤ 10⁵ int n;             // 结点数 int parentNod[N];  // parentNod[i]：i 的父结点，𝑓ᵢ int cost[N];       // cost[i]：把 i 染黑要花多少代价，𝑐ᵢ int childCnt[N];   // childCnt[i]：i 的孩子结点数 long long dp[N];   // dp[i]：保证“从 i 往下的路径”安全的最小代价 int main() {          cin >> n;          for (int i = 2; i <= n; i++) {                    cin >> parentNod[i];    // 读取父结点信息，𝑓ᵢ                    childCnt[parentNod[i]]++;  // 统计孩子结点数          }          for (int i = 1; i <= n; i++)                    cin >> cost[i];   // 读取染色代价，𝑐ᵢ         for (int i = n; i >= 1; i--) { // 从编号大的往小算(孩子结点→父结点，倒着算)                    if (childCnt[i] == 0) {         // 如果是叶子结点                             dp[i] = cost[i];       // 只能自己染                    }                    dp[i] = dp[i] < cost[i] ? dp[i] : cost[i];       // 选择代价小的染                    if (i != 1)                // 把自己的最小代价加给父结点                             dp[parentNod[i]] += dp[i];          }          cout << dp[1] << endl;            // 根结点的答案          return 0; }

方法二：根结节为1，孩子结点编号大于1。从最大编号结点开始到2号结点向上计算染黑最小代码，并加到其父结点，根结点的dp值就是答案。注意𝑐ᵢ≤10⁹，所以𝑐ᵢ的和dp要用long long。算法与方法一相同。参考程序代码如下：

​​​​​​​#include <iostream> using namespace std; const int N = 100005;  // 𝑛≤ 10⁵ int n, f[N], c[N], cnt[N]; // f[i]：𝑓ᵢ, c[i]：𝑐ᵢ, cnt[i]：i的孩子结点数 long long dp[N]; int main() {          cin >> n;          for (int i = 2; i <= n; i++) { // 读取父结点信息，𝑓ᵢ                    cin >> f[i];                    cnt[f[i]]++;               // 统计孩子结点数          }          for (int i = 1; i <= n; i++)                    cin >> c[i];               // 读取染色代价，𝑐ᵢ          for (int i = n; i >= 1; i--) { // 从编号大的往小算(孩子结点→父结点，倒着算)                    if (cnt[i] == 0)           // 如果是叶子结点                             dp[i] = c[i];     // 只能自己染                    dp[i] = dp[i] < c[i]? dp[i]:c[i];// 选择代价小的染                    dp[f[i]] += dp[i];         // 把自己的最小代价加给父结点          }          cout << dp[1] << endl;            // 根结点的答案          return 0; }

3.2 编程题2

• 试题名称：道具商店
• 时间限制：1.0 s
• 内存限制：512.0 MB

3.2.1题目描述

道具商店里有𝑛件道具可供挑选。第𝑖件道具可为玩家提升𝑎ᵢ点攻击力，需要𝑐ᵢ枚金币才能购买，每件道具只能购买一次。现在你有𝑘枚金币，请问你最多可以提升多少点攻击力？

3.2.2 输入格式

第一行，两个正整数𝑛, 𝑘，表示道具数量以及你所拥有的金币数量。

接下来𝑛行，每行两个正整数𝑎ᵢ, 𝑐ᵢ，表示道具所提升的攻击力点数，以及购买所需的金币数量。

3.2.3 输出格式

输出一行，一个整数，表示最多可以提升的攻击力点数。

3.2.4 样例

3.2.4.1 输入样例1

3 5 99 1 33 2 11 3

3.2.4.2 输出样例1

132

3.2.4.3 输入样例2

4 100 10 1 20 11 40 33 100 99

3.2.4.4 输出样例2

110

3.2.5 数据范围

对于60%的测试点，保证1≤𝑘≤500，1≤𝑐ᵢ≤500。

对于所有测试点，保证 1≤𝑛≤500，1≤𝑘≤10⁹，1≤𝑎ᵢ≤500，1≤𝑐ᵢ≤10⁹。

3.2.6 编写程序

编程思路：

这道题是一道典型的变形01背包问题，常规的01背包思路会因为金币容量𝑘过大(最大 10⁹)而无法直接实现，因此需要转换思考维度来解决。

方法一：

常规01背包会定义 dp[j] 为“花费 j 金币能获得的最大攻击力”，但本题中𝑘高达10⁹，无法开这么大的数组。观察数据范围发现：每件道具的攻击力𝑎ᵢ≤500，道具数量𝑛≤500，因此所有道具的总攻击力最大为 500×500=250000(这个数值很小，完全可以用数组存储)。

因此我们转换背包维度：定义 dp[j] 为“获得 j 点攻击力所需的最少金币数”。通过这个转换，我们只需要处理 j 从 0 到 250000 的情况，最后遍历所有可能的攻击力值，找到满足 dp[j] ≤ k 的最大 j 即可。参考程序代码如下：

#include <iostream> using namespace std; int n, k;       // n：道具数量，k：拥有的金币总数 int a[505];     // a[i]：第i件道具能提升的攻击力𝑎ᵢ int c[505];     // c[i]：第i件道具所需金币枚数𝑐ᵢ int dp[250005];  // dp[j]：获得j点攻击力需要的最少金币数，最大攻击力总和为500*500=250000 int pwr = 0;    // 所有道具的攻击力总和，作为dp遍历的上界 int ans = 0;    // 最终答案：最多能提升的攻击力 int main() {          cin >> n >> k; // 输入道具数量和金币数          for (int i = 1; i <= n; i++) {                    cin >> a[i] >> c[i];                    pwr += a[i]; // 累加所有道具的攻击力，得到最大可能的攻击力总和          }          for (int i = 1; i <= pwr; i++) {  // 初始化                    dp[i] = 2e9;  // 除dp[0]外，初始化为2×10⁹，大于k≤10⁹，可区分“可达”、“不可达”          }          for (int i = 1; i <= n; i++) {                   // 01背包核心循环(遍历每件道具)                   for (int j = pwr; j >= a[i]; j--)            // 逆序遍历攻击力(避免同一道具被重复选取)                             dp[j] = min(dp[j], dp[j - a[i]] + c[i]); // 状态转移(同等攻击力选需金币少的)          }          for (int i = 1; i <= pwr; i++) { // 遍历可能的攻击力，找花费≤k的最大攻击力                    if (dp[i] <= k) ans = i;     // 只要当前攻击力可达，就更新答案          }          cout << ans;     // 输出最终结果          return 0; }

方法二：

这题是0/1背包问题变体：将道具视为物品，攻击力视为价值，金币视为背包容量。

目标：在金币限制(𝑘)内最大化总攻击力（非传统背包的价值最大化）。

‌动态规划策略‌

‌状态定义‌：f[j] = 获得恰好 j 点攻击力所需的最小金币；

‌状态转移‌：f[j] = min(f[j], f[j - a] + c)  // 选择 or 不选当前道具

‌倒序遍历‌：内层循环 j 从 s 递减到 a(关键！避免同一道具重复使用)

‌复杂度分析‌

时间复杂度：𝑂(𝑛×𝑠) ≈ 𝑂(250,000n)~10⁸级(s为攻击力总和)，不会超时

空间复杂度：𝑂(𝑛²)(因数组大小N²=255,025）

‌初始化‌：f[0] = 0 是正确性的前提(零攻击力零消耗)，全局变量默认

‌倒序更新‌：正序遍历会导致完全背包问题（物品无限次使用）

‌边界处理‌：攻击力上限 s 动态累积，避免无效计算

参考程序代码如下：

#include <iostream> using namespace std; const int N = 505;          // 最大道具数量 const int oo = 2e9;         // 极大值（表示无穷大），因k最大为10^9 int n, k;                   // n-道具数量，k-拥有的金币总数 int f[N * N];               // DP数组：f[j]表示获得攻击力j所需的最小金币数(大小505²=255025) int main() {     cin >> n >> k;     // 初始化DP数组：所有攻击力状态初始化为无穷大（不可达）     for (int i = 1; i < N * N; i++) // 获得0攻击力的成本为0金币         f[i] = oo;     int s = 0;              // 累计最大可能攻击力     for (int i = 1; i <= n; i++) {         int a, c;           // a-道具攻击力𝑎ᵢ，c-道具金币成本𝑐ᵢ         cin >> a >> c;         s += a;             // 求总攻击力上限         for (int j = s; j >= a; j--) { // 0/1背包核心：倒序更新DP(防止物品重复使用)             f[j] =  f[j] < f[j - a] + c ? f[j] : f[j - a] + c; // 状态转移：min(不选当前道具, 选当前道具)         }     }     int ans = 0;     for (int i = 0; i <= s; i++) {  // 只需遍历到累计攻击力s，寻找满足f[i]≤k(总金币数)的最大攻击力i         if (f[i] <= k) ans = i;     // 更新最大合法攻击力(因i递增，最终为最大值)     }     cout << ans;                    // 输出结果     return 0; }