云服务安全策略最优选择2026 华为OD机试真题 6月24日华为OD上机新系统考试真题 100 分题型点击查看华为 OD 机试真题完整目录2026最新华为OD机试新系统卷 双机位C卷 真题题库目录全覆盖题库 逐点算法考点详解题目描述在云服务中有 n 个安全策略编号 1 到 n。每个策略有一个重要度权重正整数。某些策略对之间互斥不能同时启用。现在需要为某个实例恰好选择k个策略要求选中的策略之间没有互斥关系即构成一个独立集在满足条件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≤250≤k≤n1≤ weights[i] ≤10000≤ conflicts.length ≤n(n−1)/2示例1输入4,2,[5,1,3,4],[[1,2],[2,3]]输出[[1,4]]说明组合 [1,4] 权重和为 549是最大合法值。示例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是最大值。解题思路核心思想最大权重独立集问题核心思想位掩码枚举n≤25枚举所有可能的 k 元素组合2^n 枚举冲突检测使用位掩码表示冲突关系高效检测组合是否合法最优选择遍历所有合法组合记录最大权重和收集所有达到最大权重的组合算法步骤构建冲突掩码数组conflict_mask[i]表示与策略 i1 冲突的所有节点枚举所有大小为 k 的组合位掩码对每个组合检查是否为独立集遍历掩码中的每个选中节点检查冲突掩码计算合法组合的权重和记录最大值返回所有权重和等于最大值的组合复杂度分析时间复杂度O(2^n * n)n≤25 时可接受空间复杂度O(n)存