题目与解析——2024年清华大学计算机系专项改革工程硕博&外校硕博推免机试

整体情况

4 小时，3 道传统题，每题 100 分，共 300 分。

我报了直博的专项改革工程博士志愿，考这套题花了约 1.5 小时 AK，感觉这套题比 9 月 9 日的第一场校内推免机试略简单。考前带了打印的一大摞 500 多页 OI-Wiki 怀疑又用不上，最后看到第三题非常感动（雾

具体题目

尽量脑补还原了考场代码，但因为没数据测了，不保证正确。

t1 — 阿瓦隆

签到题，略。

t2 — 网络

题目描述

个 A 类节点（编号 ）和 个 B 类节点（编号 ）。对于  个 A 类节点中的第 个节点，它可以向编号在 中的 B 类节点连边，每连一条边代价为 。对于整幅图，你需要选择一些边连接，使得在整幅图连通块数量最少的情况下，连边的代价之和最小。

输入：第一行 （注意顺序）；接下来 行，第 行为 。

输出：最小的总代价。

数据规模： 为 级别， 非负。

题解

从小到大枚举每一个 A 类节点，然后把对应的  编号范围内的 B 类节点连成一个大连通块。在这之前，如果  编号范围内的 B 类节点一共有 个连通块，那么总代价就需要增加 （每一个连通块都需要向第  个 A 类节点连一条边）。注意到任何时刻 B 类节点的连通块都必然是连续的线段，所以使用并查集维护 B 类节点的连通关系并记录每一个连通块当前的右端点即可。

。

代码：

t3 — 图定向

题目描述

个点 条边的无向简单图，节点编号为 ，第 个节点有权值 。往图中再添加任意一条边（可以添加已有的边），然后选择一条从 号节点出发，回到 号节点的路线，满足图中的每一条边在路线中只能单向通行，即对于一条边 ，如果路线中以 的方向经过了这条边，那么就不能再以 的方向经过这条边。你需要最大化路线经过的所有节点的权值和，注意多次经过同一节点只取得一次权值。

输入：第一行 ；第二行  个数 ；接下来  行，第  行为 ，表示一条边 。

输出：最大权值和。

数据规模： 为  级别， 非负。

题解

号节点的权值最长链即可。

。

代码：