【笔试题汇总】华为春招笔试题解 2024-4-10_华为算法笔试

2024.04.10-春招第二场

01.LYA 的云服务计费系统

问题描述

LYA 是一家云服务提供商，她需要为客户提供云服务计费功能。现在，她有一份包含多条计费日志的文件，每条日志包含时间戳、客户标识、计费因子和计费时长四个字段。此外，她还有一份计费因子的单价列表。

LYA 需要编写一个程序，根据计费日志和计费因子单价列表，计算每个客户的话单总费用。需要注意的是，如果同一客户在相同时间戳上报了多条相同计费因子的日志，只能计费一次，并且选择先上报的日志进行计费。

输入格式

第一行包含一个正整数 $n$，表示计费日志的条数，$1\le n\le 1000$。

接下来的 $n$ 行，每行包含四个字段，分别表示时间戳（长度为 $10$ 的数字字符串）、客户标识（长度为 $1\sim 16$ 的字符串）、计费因子（长度为 $1\sim 16$ 的字符串）和计费时长（范围为 $0\sim 100$ 的整数），字段之间用逗号分隔。如果计费因子在单价列表中查不到，则认为其单价为 $0$；如果计费时长不在 $0\sim 100$ 的范围内，则认为计费时长为 $0$。

接下来一行包含一个正整数 $m$，表示计费因子的数量，$1\le m\le 100$。

最后的 $m$ 行，每行包含两个字段，分别表示计费因子（长度为 $1\sim 16$ 的字符串）和单价（范围为 $1\sim 100$ 的整数），字段之间用逗号分隔。

输出格式

输出每个客户的话单总费用，每行包含两个字段，分别表示客户标识和话单费用，字段之间用逗号分隔。输出按照客户标识的字典序升序排列。

样例输入

5
1627845600,client1,factorA,10
1627845605,client2,factorB,15
1627845610,client1,factorA,5
1627845615,client1,factorB,8
1627845620,client2,factorB,20
2
factorA,5
factorB,7
1
2
3
4
5
6
7
8
9

样例输出

client1,131
client2,245
1
2

数据范围

• $1\le n\le 1000$
• $1\le m\le 100$
• 时间戳是长度为 $10$ 的数字字符串
• 客户标识和计费因子是长度为 $1\sim 16$ 的字符串
• 计费时长的范围为 $0\sim 100$
• 计费因子的单价范围为 $1\sim 100$

【题目解析】

本题可以用DFS求解。基本思路如下：

1. 枚举断开的节点 $x$，将其从 $exposed$ 中移除。
2. 对于 $exposed$ 中的每个节点 $u$，从 $u$ 开始DFS搜索所有可达的节点，并记录数量。权限等级初始为 $10$。
3. 如果当前节点 $u$ 可以访问节点 $v$（即 $matrix[u][v]$ 不为 $0$ 且不超过当前权限等级），则将 $v$ 加入DFS，并将权限等级更新为 $matrix[u][v]$。
4. 选择最终被入侵节点数量最少的 $x$ 作为答案。如有多个，取编号最小的。

cpp

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
const int N = 30;
int a[N][N];
bool st[N];

int dfs(int id, int ra) {
    int num = 0, sm = 0;
    for (int i = 0; i < n; i++) {
        if (id == i || !a[id][i]) continue;
        if (ra >= a[id][i]) {
            if (st[i]) continue;
            st[i] = true;
            num += dfs(i, a[id][i]);
            st[i] = false;
        }
    }
    return num + 1;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    int x;
    int res = -1, ans = 0;
    while (cin >> x) {
        for (int i = 0; i < n; i++) {
            if (x == i) continue;
            st[x] = true;
            int t = dfs(x, 10);
            st[x] = false;
            if (t > ans) {
                ans = t;
                res = x;
            }
        }
    }
    cout << res;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

02.LYA 的图片分类算法

问题描述

LYA 是一位图像处理工程师，她需要设计一个算法来对一批图片进行分类。首先，她对每张图片提取特征，并计算任意两张图片之间的相似度。然后，根据以下规则将图片归类：

1. 如果两张图片的相似度大于 $0$，则认为它们是相似的；
2. 如果图片 $A$ 和 $B$ 相似，$B$ 和 $C$ 相似，但 $A$ 和 $C$ 不相似，则认为 $A$ 和 $C$ 是间接相似的，可以将 $A$、$B$、$C$ 归为一类，但不计算 $A$ 和 $C$ 的相似度；
3. 如果一张图片与所有其他图片都不相似，则它自成一类，相似度为 $0$。

给定一个大小为 $N\times N$ 的矩阵 $M$，其中 $M[i][j]$ 表示第 $i$ 张图片和第 $j$ 张图片的相似度，请按照从大到小的顺序返回每个相似类中所有图片的相似度之和。

输入格式

第一行包含一个正整数 $N$（$1\le N\le 900$），表示矩阵 $M$ 中图片的数量。

接下来的 $N$ 行，每行包含 $N$ 个用空格分隔的非负整数，表示矩阵 $M$。其中，$0\le M[i][j]\le 100$，并且保证 $M[i][j]=M[j][i]$。

注意：输入的矩阵元素之间的分隔符可能是一个或多个连续的空格。

输出格式

输出每个相似类的相似度之和，按照从大到小的顺序输出。每个数占一行，相邻两个数之间用一个空格分隔。

样例输入

5
0 0 50 0 0
0 0 0 25 0
50 0 0 0 15
0 25 0 0 0
0 0 15 0 0
1
2
3
4
5
6

样例输出

65 25
1

数据范围

• $1\le N\le 900$
• $0\le M[i][j]\le 100$

【题目解析】

首先，提取每张图片的特征并计算图片间的相似度矩阵。然后按照给定的规则对图片进行分类，并计算每个相似类中所有图片的相似度之和。

为了解决这个问题，我们可以采用深度优先搜索，并查集等方法来处理相似类的合并，然后计算相似度之和。使用并查集将相似的图片进行合并。接着计算每个相似类中所有图片的相似度之和，并按照从大到小的顺序输出。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
    
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    
    int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

int main() {
    int N;
    cin >> N;
    
    vector<vector<int>> M(N, vector<int>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> M[i][j];
        }
    }
    
    UnionFind uf(N);
    
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if (M[i][j] > 0) {
                uf.merge(i, j);
            }
        }
    }
    
    vector<int> sum(N, 0);
    for (int i = 0; i < N; ++i) {
        sum[uf.find(i)] += accumulate(M[i].begin(), M[i].end(), 0);
    }
    
    sort(sum.rbegin(), sum.rend());
    
    for (int i = 0; i < N; ++i) {
        if (sum[i] > 0) {
            cout << sum[i] << endl;
        }
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

03.网络入侵检测

问题描述

K小姐是一名网络安全工程师，她负责维护一个由 $N$ 个节点组成的内部网络。这个网络的连通性可以用一个 $N\times N$ 的矩阵 $matrix$ 来表示，其中 $matrix[i][j]=p$ 表示从节点 $i$ 到节点 $j$ 需要的最低权限等级为 $p$（$p=0$ 表示不连通）。如果成功访问了节点 $j$，则该节点的权限等级会被调整为 $p$。

某天，K小姐发现有一些节点暴露在了公网上，存在被外部攻击的风险。暴露节点的编号保存在数组 $exposed$ 中。如果攻击者从公网入侵了某个暴露节点，则该节点的权限等级会变为最高等级 $10$。同时，入侵可以在网络内部传播，只要满足权限等级的要求即可。

为了尽快控制损失，K小姐决定立即将某个暴露节点从公网断开。她希望你能帮忙计算，断开哪个节点能够使最终被入侵的节点数量最少。如果有多个答案，则输出编号最小的节点。

输入格式

第一行包含一个正整数 $N$，表示网络中节点的数量。

接下来 $N$ 行，每行包含 $N$ 个空格分隔的整数，表示矩阵 $matrix$。

最后一行包含若干个空格分隔的整数，表示数组 $exposed$。

输出格式

输出一个整数，表示应该断开的节点编号。

样例输入

4
1 0 0 0
0 1 2 0
0 1 1 4
0 0 3 1
1 3
1
2
3
4
5
6

样例输出

3
1

数据范围

• $2\le N\le 24$
• $0\le matrix[i][j]\le 10$
• $0\le exposed[i]<N$

【题目解析】

这个问题可以通过模拟攻击来解决。首先，我们需要遍历每个可能的断开的节点，然后模拟从公网入侵并在网络内部传播的过程，最终统计每个节点被入侵的次数。最后，选择使得被入侵节点数量最少的节点进行断开。

cpp

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int simulateAttack(vector<vector<int>>& matrix, vector<int>& exposed, int disconnected_node) {
    int n = matrix.size();
    vector<bool> visited(n, false);
    vector<int> permissions(n, INT_MAX);


    for (int i = 0; i < n; ++i) {
        matrix[i][disconnected_node] = 0;
    }


    int exposed_count = 0;
    for (int ex_node : exposed) {
        if (!visited[ex_node]) {
            exposed_count++;
            visited[ex_node] = true;
            permissions[ex_node] = 10;
            for (int i = 0; i < n; ++i) {
                if (matrix[ex_node][i] != 0 && matrix[ex_node][i] <= permissions[ex_node]) {
                    permissions[i] = min(permissions[i], matrix[ex_node][i]);
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            for (int ex_node : exposed) {
                if (matrix[i][ex_node] != 0 && matrix[i][ex_node] <= permissions[ex_node]) {
                    visited[i] = true;
                    exposed_count++;
                    break;
                }
            }
        }
    }

    return exposed_count;
}

int main() {
    int n;
    cin >> n;

    // Read matrix
    vector<vector<int>> matrix(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> matrix[i][j];
        }
    }

    // Read exposed nodes
    vector<int> exposed;
    int node;
    while (cin >> node) {
        exposed.push_back(node);
    }

    // Find the node to disconnect
    int min_exposed_count = INT_MAX;
    int disconnect_node = -1;
    for (int i = 0; i < n; ++i) {
        int exposed_count = simulateAttack(matrix, exposed, i);
        if (exposed_count < min_exposed_count) {
            min_exposed_count = exposed_count;
            disconnect_node = i;
        }
    }

    cout << disconnect_node << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

整理试题不易，你的关注是我更新的最大动力！关注博主 带你看更多面试及竞赛试题和实用算法。