CSP-S 提高级 · CSP 2019 提高级第一轮 第 19 题

三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）

1. （匠人的自我修养）

一个匠人决定要学习 $n$ 个新技术。要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。

输入第一行有两个数，分别为新技术个数 $n(l\leq n\leq 10^3)$，以及己有经验值（$\le10^7$）。

接下来 $n$ 行。第 $i$ 行的两个正整数，分别表示学习第 $i$ 个技术所需的最低经验值（$\le10^7$），以及学会第 $i$ 个技术后可获得的经验值（$\leq 10^7$）。

接下来 $n$ 行。第 $i$ 行的第一个数 $m_i$（$0\le m_i<n$），表示第 $i$ 个技术的相关技术数量。紧跟着 $m$ 个两两不同的数，表示第 $i$ 个技术的相关技术编号。

输出最多能学会的新技术个数。

下面的程序以 $O(n^2)$ 的时间复杂度完成这个问题，试补全程序。

#include<cstdio>
using namespace std;
const int maxn = 1001;

int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn], bonus[maxn];
int points;
bool find(){
    int target = -1;
    for (int i = 1; i <= n; ++i)
        if(① && ②){
            target = i;
            break;
    }
    if(target == -1)
        return false;
    unlock[target] = -1;
    ③
    for (int i

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这道题是贪心+拓扑排序的混合体，核心就是每次挑一个‘前置已满足且经验够’的技术学，学完再更新依赖它的技术。

最容易把 unlock 数组理解反了，以为 cnt 是前置数，其实 cnt 存的是出度（子节点数），unlock 才是入度（未学前置数）。初始化时 unlock[i] 必须设成 m_i（依赖个数），很多人直接设 0 或设成 m_i 却忘了后续要递减。判断条件里把 points>=threshold 写成 points>threshold 也会漏掉刚好够的情况。

考点与命题视角

这题考的是贪心策略与拓扑排序思想的结合。题目给出一堆技术，每个技术有门槛和经验奖励，且学之前必须先把若干前置技术学会。这种依赖关系天然构成一个有向图：若 i 是 j 的前置，就画一条 i→j 的边。我们要不断找一个“入度为 0 且经验够”的点把它删掉（学掉），然后把它的所有出边对应的入度减 1，重复直到没可选点为止。

命题人喜欢在这里挖两个坑： 1. 数组语义混淆：cnt 存的是每个点的出度（子节点数），unlock 存的是入度（未学前置数）。很多学生看到 cnt 就以为是前置数，初始化时就会搞错。 2. 经验判断的边界：门槛是“至少需要”，所以是 points >= threshold，不是严格大于。

数据结构与初始化

程序里定义了：

• cnt[i]：i 的子节点个数（出度）
• child[i][0..cnt[i]-1]：i 的子节点列表
• unlock[i]：i 还剩下多少个前置没学（入度）
• threshold[i]、bonus[i]：门槛与奖励
• points：当前总经验

读入 n 和初始经验后，先读每个技术的门槛和奖励。接着读依赖关系：第 i 行给出 m_i 和 m_i 个前置编号。这里就是填⑤的地方。因为 m_i 就是 i 的前置数量，也就是 i 的入度，所以要把 unlock[i] 初始化为 m。unlock[i] = m 对应选项 B。