实习日记:华为暑期实习(研发)- 4月8日机试题解

实习日记:华为暑期实习(研发)- 4月8日机试题解

Ginkgo True love prevails.

整体难度中等偏上,但不算离谱。

1. 包裹的编码

原题

某快递公司的包裹编号系统采用混合进制编码,以高效分配和分拣包裹。每个包裹的编号由多个部分组成,每个部分对应不同的分层层级,且使用不同的进制表示。

给定一个十进制整数 (可为负数)和一组进制 (从高位到低位的顺序),进行符号位和混合进制编码的计算,最后按照要求输出转换后的包裹编码字符串,具体规则如下:

  • 符号位:若 N 为负数,编码的第一个元素为 1,其余部分为 |N| 的混合进制编码;若 N 为非负数,编码的第一个元素为 0,其余部分为 N 的混合进制编码。
  • 混合进制编码:按输入的 bases 顺序,从高位到低位依次处理各个层级。计算方式为:上一级的商除以本级 base 的余数作为本级的编码值,第一层级用 |N| 作为初始商。
  • 最终输出:需要将编码转换为 的字符串,并进行回文检测:编码 转换为字母 ,编码 转换为字母 ,依次类推,编码 转换为字母 ;如果最终字符串是回文串,则在字符串后添加 (palindrome);如果不是回文串,则输出最长的回文子串,若最长回文子串存在多个则按照字典序最小的输出。
输入描述
  • 第一行包含一个整数 ()。
  • 第二行包含 个整数,表示进制序列 ()。
输出描述

输出一行字符串,表示转换后的包裹编码结果。

样例1

输入:

1
2
-21
5 7 3

输出:

1
bb
样例2

输入:

1
2
0
5 7 3

输出:

1
aaaa (palindrome)

题意概述

给一个整数 (可负)和一组进制 ,先做符号位编码,再做混合进制展开,最后映射到字母串并判断回文:

  1. 若 ,首位编码是 1;否则是 0。
  2. 其余位由 按 bases 依次取余得到。
  3. 数值 0 - 25 映射成 a - z。
  4. 若整串是回文,输出 原串 (palindrome);否则输出最长回文子串。
  5. 若最长回文子串有多个,取字典序最小。

思路

  1. 先按题意构造编码字符串。
  2. 用双指针判断整串是否回文。
  3. 若不是回文,用中心扩展法找最长回文子串。
  4. 在长度相同的候选中,补一个字典序比较,保证满足题目要求。

参考实现(C++)

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
string lpsLexicographicallySmallest(const string& s) {
int n = (int)s.size();
int st = 0, maxLen = 1;

auto better = [&](int candSt, int candLen) {
if (candLen != maxLen) return candLen > maxLen;
return s.substr(candSt, candLen) < s.substr(st, maxLen);
};

auto expand = [&](int l, int r) {
while (l >= 0 && r < n && s[l] == s[r]) {
--l;
++r;
}
int candSt = l + 1;
int candLen = r - l - 1;
if (better(candSt, candLen)) {
st = candSt;
maxLen = candLen;
}
};

for (int i = 0; i < n; ++i) {
expand(i, i); // 奇数长度
expand(i, i + 1); // 偶数长度
}
return s.substr(st, maxLen);
}

bool isPal(const string& s) {
int l = 0, r = (int)s.size() - 1;
while (l < r) {
if (s[l++] != s[r--]) return false;
}
return true;
}

void solve() {
int n;
cin >> n;

string str;
str.push_back(n < 0 ? 'b' : 'a');

int cur = abs(n), base;
while (cin >> base) {
str.push_back(char('a' + cur % base));
cur /= base;
}

if (isPal(str)) {
cout << str << " (palindrome)";
} else {
cout << lpsLexicographicallySmallest(str);
}
}

2. 大模型性能优化

题目描述

给定一个由 个模块组成的模型,第 个模块的初始耗时为 ,耗时下限为 (保证 )。各个模块串行执行,模型总耗时为所有模块耗时之和。现有 天时间,每天可以选择一个模块进行一次优化(同一模块可以优化多次),每次优化后该模块的耗时变为 ,其中 为当前耗时;若当前耗时已经等于 ,则不能继续优化。请合理安排优化顺序,使得 天后所有模块的总耗时最小。

输入描述
  • 第一行包含两个整数 (),分别表示模块数量和优化天数。
  • 第二行包含 个整数,表示每个模块的初始耗时 ()。
  • 第三行包含 个整数,表示每个模块的耗时下限 ()。
输出描述

输出一个整数,表示 m 天后所有模块的最小总耗时。

样例1

输入:

1
2
3
2 0
50 100
10 10

输出:

1
150

题意概述

有 个模块,第 个模块当前耗时 ,下限 。每天可以选一个模块优化一次:

共 天,问总耗时最小值。

思路

这是经典「每次选当前收益最大」的贪心:

  1. 某模块当前收益为 。
  2. 每天取收益最大的模块做一次优化。
  3. 更新该模块后,再把新收益放回堆。

用大根堆维护 收益下标 即可,复杂度为 。

参考实现(C++)

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
using pii = pair<int, int>;

void solve() {
int n, m;
cin >> n >> m;

vector<int> cur(n), mn(n);
for (int& x : cur) cin >> x;
for (int& x : mn) cin >> x;

auto getNext = [](int now, int low) {
return max(low, (now + 1) / 2);
};
auto gain = [&](int now, int low) {
return now - getNext(now, low);
};

priority_queue<pii> pq;
for (int i = 0; i < n; ++i) {
int g = gain(cur[i], mn[i]);
if (g > 0) pq.push({g, i});
}

while (m-- > 0 && !pq.empty()) {
auto [g, i] = pq.top();
pq.pop();

cur[i] = getNext(cur[i], mn[i]);
int ng = gain(cur[i], mn[i]);
if (ng > 0) pq.push({ng, i});
}

cout << accumulate(cur.begin(), cur.end(), 0LL) << '\n';
}

3. 分布式任务调度

题目描述

有 N 个任务,需要把这些任务调度到服务器上运行。每个任务有 CPU 需求 c_i、内存需求 m_i、任务价值 v_i。服务器 CPU 规格为 C,内存规格为 M,一台服务器可以运行多个任务并获得它们的总价值,条件是这些任务的 CPU 需求之和不超过 C,且内存需求之和不超过 M。一个任务只能运行在一台服务器上。

我们想知道,当服务器数量为 1 到 N 的每一种情况,其运行任务的最大总价值是多少,以帮助决策需要购买多少台服务器。换句话说,对于 K=1,2,…,N,假设有 K 台服务器,分别输出可运行任务的最大总价值。

输入描述
  • 第一行包含三个整数 N,C,M(1 ≤ N ≤ 15, 1 ≤ C,M ≤ 10^6),分别表示任务数量、服务器 CPU 规格、服务器内存规格。
  • 接下来 N 行,每行包含三个整数 c_i,m_i,v_i(1 ≤ c_i,m_i,v_i ≤ 10^6),表示每个任务的 CPU 需求、内存需求和任务价值。
输出描述

输出 N 行,每行一个整数,第 i 行表示服务器数量 K=i 时可运行任务的最大总价值。

样例1

输入:

1
2
3
4
3 3 10
1 4 1
2 5 2
2 6 4

输出:

1
2
3
5
7
7

题意概述

个任务,每个任务有 。每台服务器有 CPU 上限 、内存上限 。对于 ,分别求有 台服务器时可获得的最大总价值。

思路

看到 ,直接想到状态压缩:

  1. 用二进制状态 表示任务子集。
  2. 预处理每个子集是否能放进一台服务器(ok[s]),以及其价值 val[s]。
  3. 定义 dp[k][s]:用 台服务器覆盖任务集合 的最大价值。
  4. 枚举 s 的子集 sub 做转移:

子集枚举模板:for (sub = s; sub; sub = (sub - 1) & s)。

参考实现(C++)

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
struct Task {
int c;
int m;
int v;
};

void solve() {
int N, C, M;
cin >> N >> C >> M;

vector<Task> tasks(N);
for (int i = 0; i < N; ++i) {
cin >> tasks[i].c >> tasks[i].m >> tasks[i].v;
}

int S = 1 << N;
vector<int> sumC(S, 0), sumM(S, 0), sumV(S, 0), val(S, 0);
vector<bool> ok(S, false);

for (int s = 1; s < S; ++s) {
int lb = s & -s;
int i = __builtin_ctz(lb);
int prev = s ^ lb;

sumC[s] = sumC[prev] + tasks[i].c;
sumM[s] = sumM[prev] + tasks[i].m;
sumV[s] = sumV[prev] + tasks[i].v;

if (sumC[s] <= C && sumM[s] <= M) {
ok[s] = true;
val[s] = sumV[s];
}
}

vector<vector<int>> dp(N + 1, vector<int>(S, 0));

for (int k = 1; k <= N; ++k) {
for (int s = 0; s < S; ++s) {
dp[k][s] = dp[k - 1][s];
for (int sub = s; sub; sub = (sub - 1) & s) {
if (ok[sub]) {
dp[k][s] = max(dp[k][s], dp[k - 1][s ^ sub] + val[sub]);
}
}
}
}

for (int k = 1; k <= N; ++k) {
cout << dp[k][S - 1] << '\n';
}
}

小结

这三题分别对应了三类很常见的机试模型:

  1. 按规则模拟 + 字符串处理。
  2. 局部最优可证全局最优的贪心(配合堆)。
  3. 数据范围小、状态很多时的状态压缩 DP。

写机试时,先抓数据范围,再定模型,最后把边界处理干净,通常就能稳住。

  • Title: 实习日记:华为暑期实习(研发)- 4月8日机试题解
  • Author: Ginkgo
  • Created at : 2026-04-10 14:20:00
  • Updated at : 2026-04-18 19:28:10
  • Link: https://g1nkgo7.github.io/2026/04/10/实习日记-华为暑期实习(研发岗)4月8日机试题解/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
实习日记:华为暑期实习(研发)- 4月8日机试题解