发帖
雷达卡
北京大学计算机保研机试真题精选
N 诺 DreamJudge 题库收录了多所高校的历年计算机考研与保研上机真题，搜索“北京大学”即可快速筛选出该校相关题目。所有题目均在考试大纲范围内，并支持按难度排序，便于针对性练习。配合《计算机考研机试攻略》使用效果更佳，书中例题可通过题号直接在题库中定位查找。
最小生成树问题
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
现有一个包含 n 个顶点的完全图，图中每条边的权重只能是 0 或 1，其中恰好有 m 条边的权重为 1，其余为 0。要求计算该图的最小生成树（MST）的总边权值，仅需输出边权之和。
输入格式说明：
第一行给出两个整数 n 和 m，分别代表节点数量和权重为 1 的边的数量（满足 m ≤ min{200000, n(n1)/2}）。
接下来 m 行，每行包含两个整数 a[i] 与 b[i]，表示一条连接 a[i] 和 b[i] 的无向边，其权重为 1（保证 1 ≤ a[i] < b[i] ≤ n），且所有输入的边互不重复。
输出格式说明：
输出一行，仅包含一个整数，即最小生成树的所有边权之和。
样例输入：
6 11
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
样例输出：
2
田忌赛马策略问题
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
源自经典典故“田忌赛马”，现扩展为 N 匹马的比赛场景。双方各有 N 匹马，分为 N 个等级，等级越高实力越强。比赛规则如下：只有当己方马匹的等级高于对方对应场次马匹至少 X 等（含 X）时，才能赢得该场比赛。若在整个 N 场比赛中，己方获胜次数超过对手，则视为整体胜利。已知对手的出场顺序，请枚举所有能使己方获胜的出战方案。
输入格式说明：
第一行两个整数 N 和 X，其中 N 表示比赛场数（N ≤ 9），X 表示获胜所需的最低等级差（0 ≤ X < N）。
第二行包含 N 个正整数 A(1) 到 A(N)，A(i) 表示第 i 场比赛中对手派出马匹的等级。
输出格式说明：
按照字典序升序输出所有能确保己方最终获胜的出战方案，每个方案占一行。
每行包含 N 个正整数，第 i 个数字表示己方在第 i 场比赛中派出马匹的等级。
样例输入：
3 1
3 2 1
样例输出：
1 3 2
京公网安备 11010802022788号
