2026 华为OD机试真题 6月24日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

在云服务中，有 n 个安全策略，编号 1 到 n。每个策略有一个重要度权重（正整数）。某些策略对之间互斥，不能同时启用。

现在需要为某个实例恰好选择 k 个策略，要求：

1. 选中的策略之间没有互斥关系（即构成一个独立集）；
2. 在满足条件1的所有大小为 k 的策略组合中，使得选中策略的权重之和最大（权重之和就是重要度权重数组中的权重的和）。

请返回所有满足上述条件的最优策略组合（即权重和最大的所有合法组合）。

2026 华为OD机试真题 6月24日华为OD上机新系统考试真题 100 分题型

输入描述

输入为单行，格式为：n,k,[weights],[[conflicts]]

• n：策略总数
• k：需要选择的策略数量
• weights：长度为 n 的整数数组，表示各策略权重
• conflicts：二维整数数组，每个元素为 [a, b]，表示策略 a 和 b 互斥（无向，无重复边）

输出描述

• 每个组合内的策略编号按升序排列；
• 所有组合按字典序排列（将每个组合视为一个数字序列）；
• 如果没有合法组合（例如不存在大小为 k 的独立集），则返回空数组 []。

注意

• 如果没有大小为 k 的独立集，则返回 []
• 输入格式：单行输入 n,k,[weights],[[conflicts]]

数据规模

• 1≤n≤25
• 0≤k≤n
• 1≤ weights[i] ≤1000
• 0≤ conflicts.length ≤n(n−1)/2

示例1

输入

4,2,[5,1,3,4],[[1,2],[2,3]]

输出

[[1,4]]

说明

组合 [1,4] 权重和为 5+4=9，是最大合法值。

示例2

输入

5,3,[3,4,3,4,3],[[1,3],[2,4],[3,5]]

输出

[[1,2,5],[1,4,5]]

说明

合法组合 [1,2,5] 和 [1,4,5] 权重和均为 10，是最大值。

解题思路

核心思想

最大权重独立集问题，核心思想：

1. 位掩码枚举：n≤25，枚举所有可能的 k 元素组合（2^n 枚举）
2. 冲突检测：使用位掩码表示冲突关系，高效检测组合是否合法
3. 最优选择：遍历所有合法组合，记录最大权重和，收集所有达到最大权重的组合

算法步骤

1. 构建冲突掩码数组：conflict_mask[i] 表示与策略 i+1 冲突的所有节点
2. 枚举所有大小为 k 的组合（位掩码）
3. 对每个组合检查是否为独立集：遍历掩码中的每个选中节点，检查冲突掩码
4. 计算合法组合的权重和，记录最大值
5. 返回所有权重和等于最大值的组合

复杂度分析

• 时间复杂度：O(2^n * n)，n≤25 时可接受
• 空间复杂度：O(n)，存