华为OD机试新系统真题【云服务安全策略最优选择】

云服务安全策略最优选择(C/C++/Py/Java/Js/Go)题解

华为OD机试新系统真题 华为OD上机考试新系统真题 6月24号 200分题型

华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录｜机考题库 + 算法考点详解

题目内容

在云服务中，有

n

n

n 个安全策略，编号

1

1

1 到

n

n

n。每个策略有一个重要度权重（正整数）。某些策略对之间互斥，不能同时启用。 现在需要为某个实例恰好选择

k

k

k 个策略，要求：

输入描述

• 第一行：整数 $n$
• 第二行：整数 $k$
• 第三行：长度为 $n$
• 第四行：二维整数数组 $conflicts$

数据规模：

• $1\le n\le 25$
• $0\le k\le n$
• $1\le$
• $0\le$

输出描述

• 每个组合内的策略编号按升序排列；
• 所有组合按字典序排列（将每个组合视为一个数字序列）；
• 如果没有合法组合（例如不存在大小为 $k$

注意

• 如果没有大小为 $k$

样例1

输入

4
2
5,1,3,4
1,2 2,3

输出

1,4

说明 所有大小为

2

2

2 的策略组合及互斥检查：

• [1,2] 冲突不考虑
• [1,3] 不冲突，5 + 3 = 8
• [1,4] 不冲突，5 + 4 = 9
• [2,3]冲突，不考虑
• [2,4]不冲突，1 +4=5
• [3,4]不冲突，3 + 4 = 7
• 所以结果为1,4

样例2

输入

5
3
3,4,3,4,3
1,3 2,4 3,5

输出

1,2,5 1,4,5

说明 所有大小为3且无互斥的组合：

• [1,2,3]冲突
• [1,2,4]冲突
• [1,2,5]不冲突，3 + 4 +3 = 10
• [1,3,4]冲突
• [1,3,5]冲突
• [1,4,5]不冲突，3+4+3=10
• [2,3,4]冲突
• [2,3,5]冲突
• [2,4,5]冲突
• [3,4,5]冲突
• 合法组合只有[1,2,5]和[1,4,5]权重和均为10，按字典序进行排序输出。

题解

思路：递归回溯

C++

#include <algorithm>
#include<bits/stdc++.h>
#include <string>
#include <vector>
using namespace std;

// 当前最大权重和
int maxWeightSum = 0;
// 所有最优方案
vector<vector<int>> ans;

// conflict[i]值对应二进制位1位置表示和i冲突
vector<int> conflictMask;
// 通用 切割函数 函数 将字符串str根据delimiter进行切割
vector<string> split(const string& str, const string& delimiter) {
vector<string> result;
size_t start = 0;
size_t end = str.find(delimiter);
while (end != string::npos) {
result.push_back(str.substr(start, end – start));
start = end + delimiter.length();
end = str.find(delimiter, start);
}
// 添加最后一个部分
result.push_back(str.substr(start));
return result;
}

void dfs(int n, int k, int idx,int selectedMask ,vector<int>& weights, vector<int>& path) {
// 剩余数量剪枝
if (path.size() + (n – idx) < k) return;
if (path.size() == k) {
int weightSum = 0;
for (int i = 0; i < k; i++) {
weightSum += weights[path[i] – 1];
}
if (weightSum > maxWeightSum) {
maxWeightSum = weightSum;
ans.clear();
ans.push_back(path);
} else if (weightSum == maxWeightSum) {
ans.push_back(path);
}
return;
}

if (idx >= n) {
return;
}

for (int i = idx; i < n; i++) {
// 冲突判断
if ((conflictMask[i] & selectedMask) == 0) {
path.push_back(i + 1);
dfs(n, k, i + 1, selectedMask | (1 << i), weights, path);
// 回溯
path.pop_back();
}
}
}

vector<vector<int>> selectSchema(int n, int k, vector<int>& weights, vector<vector<int>>& conflicts) {
// 特例
if (k == 0) {
return {};
}
conflictMask.assign(n, 0);
// 将冲突转换为对应mask
for (int i = 0; i < conflicts.size(); i++) {
int a = conflicts[i][0] – 1;
int b = conflicts[i][1] – 1;
conflictMask[a] |= (1 << b);
conflictMask[b] |= (1 << a);
}
vector<int> path;
dfs(n, k, 0, 0, weights, path);
return ans;
}

int main() {
int n ,k;
cin >> n;
cin >> k;
// 忽略空行
cin.ignore();
string input;
getline(cin, input);
vector<string> tmp1 = split(input, ",");
vector<int> weights(tmp1.size());
for (int i = 0; i < tmp1.size(); i++) {
weights[i] = stoi(tmp1[i]);
}

vector<vector<int>> conflicts;
string input2;
getline(cin, input2);
if (!input2.empty()) {
vector<string> tmp2 = split(input2, " ");
for (int i = 0; i < tmp2.size(); i++) {
vector<string> tmp3 = split(tmp2[i], ",");
conflicts.push_back({stoi(tmp3[0]), stoi(tmp3[1])});
}
}

vector<vector<int>> ans = selectSchema(n, k, weights, conflicts);
// 输出结果
for (int i = 0; i < ans.size(); i++) {
if (i > 0) {
cout << " ";
}
for (int j = 0; j < k; j++) {
if (j > 0) {
cout << ",";
}
cout << ans[i][j];
}
}
return 0;
}

JAVA

import java.util.*;

public class Main {

static int n, k;
// 当前最大权重和
static int maxWeightSum = 0;
// 所有最优方案
static List<List<Integer>> ans = new ArrayList<>();
static List<Integer> path = new ArrayList<>();

// conflict[i]值对应二进制位1位置表示和i冲突
static int[] conflictMask;
static int[] weights;

// DFS
static void dfs(int idx, int selectedMask) {

// 剩余数量剪枝
if (path.size() + (n – idx) < k) return;

if (path.size() == k) {

int sum = 0;
for (int i = 0; i < k; i++) {
sum += weights[path.get(i) – 1];
}

if (sum > maxWeightSum) {
maxWeightSum = sum;
ans.clear();
ans.add(new ArrayList<>(path));
} else if (sum == maxWeightSum) {
ans.add(new ArrayList<>(path));
}
return;
}

for (int i = idx; i < n; i++) {
// 冲突检测
if ((conflictMask[i] & selectedMask) == 0) {
path.add(i + 1);
dfs(i + 1, selectedMask | (1 << i));
path.remove(path.size() – 1);
}
}
}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n = Integer.parseInt(sc.nextLine());
k = Integer.parseInt(sc.nextLine());

String[] w = sc.nextLine().split(",");
weights = new int[n];
for (int i = 0; i < n; i++) weights[i] = Integer.parseInt(w[i]);

conflictMask = new int[n];

if (sc.hasNextLine()) {
String line = sc.nextLine().trim();
if (!line.isEmpty()) {
for (String p : line.split(" ")) {
String[] ab = p.split(",");
int a = Integer.parseInt(ab[0]) – 1;
int b = Integer.parseInt(ab[1]) – 1;
conflictMask[a] |= (1 << b);
conflictMask[b] |= (1 << a);
}
}
}

dfs(0, 0);

for (int i = 0; i < ans.size(); i++) {
if (i > 0) System.out.print(" ");
for (int j = 0; j < ans.get(i).size(); j++) {
if (j > 0) System.out.print(",");
System.out.print(ans.get(i).get(j));
}
}
}
}

Python

import sys
# 当前最大权重和
maxWeightSum = 0
# 所有最优方案
ans = []
path = []
# conflictMask[i]：第i个点的冲突集合（bitmask表示）
conflictMask = []
weights = []
n = k = 0

# DFS
def dfs(idx, selectedMask):
global maxWeightSum, ans

# 剩余数量剪枝
if len(path) + (n – idx) < k:
return

if len(path) == k:
s = 0
for i in range(k):
s += weights[path[i] – 1]

if s > maxWeightSum:
maxWeightSum = s
ans = [path[:]]
elif s == maxWeightSum:
ans.append(path[:])
return

for i in range(idx, n):
# 冲突检测
if (conflictMask[i] & selectedMask) == 0:
path.append(i + 1)
dfs(i + 1, selectedMask | (1 << i))
path.pop()

n = int(sys.stdin.readline())
k = int(sys.stdin.readline())

weights = list(map(int, sys.stdin.readline().strip().split(",")))
conflictMask = [0] * n

line = sys.stdin.readline().strip()
if line:
for p in line.split():
a, b = map(int, p.split(","))
conflictMask[a – 1] |= (1 << (b – 1))
conflictMask[b – 1] |= (1 << (a – 1))

dfs(0, 0)

for i, g in enumerate(ans):
if i > 0:
print(" ", end="")
print(",".join(map(str, g)), end="")

JavaScript

const readline = require('readline');

const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});

let input = [];

// maxWeightSum：当前最大权重和
let maxWeightSum = 0;

// ans：所有最优方案
let ans = [];

// path：当前路径
let path = [];

// conflictMask[i]：第i个点的冲突集合（bitmask表示）
let conflictMask = [];

// weights：权重数组
let weights = [];

// n,k
let n = 0, k = 0;

rl.on('line', (line) => {
input.push(line.trim());
});

rl.on('close', () => {

n = Number(input[0]);
k = Number(input[1]);

// 权重数组（逗号分隔）
weights = input[2].split(',').map(Number);

conflictMask = new Array(n).fill(0);

// 冲突解析（空格分隔 pair）
if (input[3] && input[3].length > 0) {
let parts = input[3].split(' ');

for (let p of parts) {
let [a, b] = p.split(',').map(x => Number(x) – 1);

// conflict[i]值对应二进制位1位置表示和i冲突
conflictMask[a] |= (1 << b);
conflictMask[b] |= (1 << a);
}
}

dfs(0, 0);

// 输出结果
let out = ans.map(x => x.join(',')).join(' ');
console.log(out);
});

function dfs(idx, selectedMask) {

// 剩余数量剪枝
if (path.length + (n – idx) < k) return;

if (path.length === k) {

let sum = 0;

for (let i = 0; i < k; i++) {
sum += weights[path[i] – 1];
}

if (sum > maxWeightSum) {
maxWeightSum = sum;
ans = [path.slice()];
} else if (sum === maxWeightSum) {
ans.push(path.slice());
}
return;
}

if (idx >= n) return;

for (let i = idx; i < n; i++) {

// 冲突判断
if ((conflictMask[i] & selectedMask) === 0) {

path.push(i + 1);

dfs(i + 1, selectedMask | (1 << i));

// 回溯
path.pop();
}
}
}

Go

package main

import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)

var (
n, k int
// 当前最大权重和
maxWeightSum int
// 所有最优方案
ans [][]int
path []int
// conflictMask[i]：第i个点的冲突集合（bitmask表示）
conflictMask []int
weights []int
)

// DFS
func dfs(idx int, selectedMask int) {

// 剩余数量剪枝
if len(path)+(n–idx) < k {
return
}

if len(path) == k {

sum := 0
for i := 0; i < k; i++ {
sum += weights[path[i]–1]
}

if sum > maxWeightSum {
maxWeightSum = sum
ans = [][]int{append([]int{}, path…)}
} else if sum == maxWeightSum {
ans = append(ans, append([]int{}, path…))
}
return
}

for i := idx; i < n; i++ {
// 冲突检测
if conflictMask[i]&selectedMask == 0 {
path = append(path, i+1)
dfs(i+1, selectedMask|(1<<i))
path = path[:len(path)–1]
}
}
}

func main() {

reader := bufio.NewReader(os.Stdin)

fmt.Fscanln(reader, &n)
fmt.Fscanln(reader, &k)

line, _ := reader.ReadString('\\n')
line = strings.TrimSpace(line)

w := strings.Split(line, ",")
weights = make([]int, n)

for i := 0; i < n; i++ {
weights[i], _ = strconv.Atoi(w[i])
}

conflictMask = make([]int, n)

line, _ = reader.ReadString('\\n')
line = strings.TrimSpace(line)

if line != "" {
for _, p := range strings.Split(line, " ") {
ab := strings.Split(p, ",")
a, _ := strconv.Atoi(ab[0])
b, _ := strconv.Atoi(ab[1])
a—
b—
conflictMask[a] |= 1 << b
conflictMask[b] |= 1 << a
}
}

dfs(0, 0)

for i, g := range ans {
if i > 0 {
fmt.Print(" ")
}
for j, v := range g {
if j > 0 {
fmt.Print(",")
}
fmt.Print(v)
}
}
}

C语言

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 25

int n, k;
// 当前最大权重和
int maxWeightSum = 0;

int weights[MAXN];
// conflictMask[i]：第i个点的冲突集合（bitmask表示）
int conflictMask[MAXN];

int path[MAXN];
int pathSize = 0;
// 存储所有最佳结果
int ans[MAXN][MAXN];
int ansCount = 0;

// DFS
void dfs(int idx, int selectedMask) {

// 剩余数量剪枝
if (pathSize + (n – idx) < k) return;

if (pathSize == k) {

int sum = 0;
for (int i = 0; i < k; i++) {
sum += weights[path[i] – 1];
}

if (sum > maxWeightSum) {
maxWeightSum = sum;
ansCount = 0;
memcpy(ans[ansCount], path, sizeof(int) * k);
ansCount = 1;
} else if (sum == maxWeightSum) {
memcpy(ans[ansCount], path, sizeof(int) * k);
ansCount++;
}
return;
}

for (int i = idx; i < n; i++) {
if ((conflictMask[i] & selectedMask) == 0) {
path[pathSize++] = i + 1;
dfs(i + 1, selectedMask | (1 << i));
pathSize—;
}
}
}

int main() {

scanf("%d", &n);
scanf("%d", &k);

for (int i = 0; i < n; i++) {
scanf("%d,", &weights[i]);
}

char buf[1000];
getchar();
fgets(buf, sizeof(buf), stdin);

if (strlen(buf) > 1) {
char *p = strtok(buf, " ");
while (p) {
int a, b;
sscanf(p, "%d,%d", &a, &b);
a—; b—;
conflictMask[a] |= (1 << b);
conflictMask[b] |= (1 << a);
p = strtok(NULL, " ");
}
}

dfs(0, 0);

for (int i = 0; i < ansCount; i++) {
for (int j = 0; j < k; j++) {
if (j) printf(",");
printf("%d", ans[i][j]);
}
if (i < ansCount – 1) printf(" ");
}

return 0;
}

​