华为机试面试真题
- 2026-11-21 03:39:01
题目名称
1、水晶的魔力之和
题目背景与描述
在古老星界的边缘,藏着一座由魔法水晶排成的长阵。每一颗水晶都蕴含着或正或负的魔力,它们连成一条永不间断的光之轨迹。传说中,只有连续一段水晶的魔力之和,恰好等于星轨密钥
你是被选中的星轨巫师,现在需要:
找出一共有多少道这样的稳定封印;
在所有能形成封印的连续水晶中,找到最短的那一段,它由多少颗水晶构成?
若不存在任何能形成封印的水晶段,则次数记为 0,最短长度记为 -1。
数据范围
1≤n≤2×1051 ≤ n ≤ 2 × 10 5 109≤ 每颗水晶的魔力值−− ≤ 10 9 − 2 × 10 14 ≤ k ≤ 2 × 10 14 连续一段水晶 指长度不小于 1 的连续子段
触发封印的次数最大可达
n(n+1)/2=2×1010,请使用 64 位整数存储与输出n ( n + 1 ) / 2 = 2 × 10 10
解答要求
时间限制:C/C++ 2000ms,其他语言 4000ms
内存限制:C/C++ 512MB,其他语言 1024MB
输入描述
第一行:整数
输出描述
一行两个整数:触发封印的次数、最短封印长度(若无合法封印,次数为 0,最短长度输出 -1)
样例 1
输入:
text
5 31 -1 5 -2 3输出:
text
3 1解释: 第 1-4 颗水晶:
简化一下题目

对于这个题目解决的办法是






#include<iostream>// 引入输入输出流库,用于 cin 和 cout#include<vector>// 引入动态数组 vector 容器库#include<climits>// 引入包含 INT_MAX 等常量限制的库using namespace std; // 使用标准命名空间,省去 std:: 前缀intmain(){ // 程序主函数入口ios::sync_with_stdio(false); // 关闭 C 和 C++ 标准流的同步,加快 cin/cout 速度cin.tie(nullptr); // 解除 cin 和 cout 的绑定,进一步提高输入输出效率int n; // 声明整型变量 n,用于存储数组的长度long long k; // 声明长整型变量 k,用于存储目标子数组的和(因为累加可能超出 int 范围)if (!(cin >> n >> k)) return 0; // 尝试读取 n 和 k,如果读取失败(如文件结束)则程序直接退出vector<longlong> a(n); // 创建一个大小为 n 的长整型 vector 数组 afor (int i = 0; i < n; ++i) cin >> a[i]; // 循环 n 次,将输入的数字逐个存入数组 a 中long long total_count = 0; // 初始化满足条件的子数组总个数为 0(使用 long long 防止溢出)int min_len = INT_MAX; // 初始化最短子数组长度为整型最大值(方便后续比较取较小值)// 暴力枚举所有连续子数组for (int i = 0; i < n; ++i) { // 外层循环:枚举子数组的起始位置 ilong long sum = 0; // 每次更换起始位置时,将当前子数组的累加和清零for (int j = i; j < n; ++j) { // 内层循环:枚举子数组的结束位置 j(从 i 开始向后延伸)sum += a[j]; // 将当前元素 a[j] 累加到 sum 中if (sum == k) { // 如果当前累加和恰好等于目标值 k++total_count; // 满足条件的子数组总个数加 1min_len = min(min_len, j - i + 1); // 计算当前子数组长度 (j-i+1),并与历史最短长度比较,保留较小值}}}if (total_count == 0) // 如果遍历完所有子数组,都没有找到符合条件的情况cout << "0 -1\n"; // 按照题目要求,输出 "0 -1" 并换行else // 如果存在符合条件的子数组cout << total_count << " " << min_len << "\n"; // 输出总个数和最短长度,中间用空格隔开,最后换行return 0; // 主函数正常结束,返回 0}
C++暴力实现该后会出现超时,因此基于哈希表进行优化
#include<iostream>#include<vector>#include<unordered_map>#include<climits>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;long long k;if (!(cin >> n >> k)) return 0;vector<longlong> a(n);for (int i = 0; i < n; ++i) cin >> a[i];// 记录前缀和值 -> 出现过的所有下标(用 vector 存,方便遍历求最短长度)unordered_map<long long, vector<int>> mp;mp.reserve(n * 2); // 预分配,减少 rehashmp.max_load_factor(0.7);mp[0].push_back(0); // 空前缀,和为 0,下标 0(这里 pre 的下标 0 表示“没有元素”)long long total_count = 0;int min_len = INT_MAX;long long pre = 0;for (int i = 1; i <= n; ++i) {pre += a[i - 1]; // pre 表示前 i 个元素的和long long target = pre - k;auto it = mp.find(target);if (it != mp.end()) {// 遍历所有满足 pre[l] = pre[i] - k 的左端点 lfor (int l : it->second) {++total_count;min_len = min(min_len, i - l); // 子数组长度 = i - l}}// 把当前前缀和加入表mp[pre].push_back(i);}if (total_count == 0)cout << "0 -1\n";elsecout << total_count << " " << min_len << "\n";return 0;}
前缀和加哈希表的计算复杂度为O(n)
下面看一看第二个问题
【华为校园招聘 软件】 2、元素法师的最终试炼
迷宫规则详解:
迷宫由
法师只能向右或向下移动,从左上角 (0,0) 出发,抵达终点——右下角的封印法阵
规则1:
沿途收集的元素能量必须恰好等于 T 点。(太少无法形成封印,太多则会引发能量反噬)
规则2:
阳炎元素(奇数能量值,如1,3,5,7,9):炽热狂暴的红色元素。
寒冰元素(偶数能量值,如2,4,6,8):冰冷沉寂的蓝色元素。
混沌元素(能量值为0):温和中立的灰色元素。
连续收集同种元素会致命:
连续激活两个阳炎元素(奇数),炽热的能量会将你焚烧。
连续收集两个寒冰元素(偶数非零),极寒的能量会将你冻结。
特别地,混沌元素(0)不属于阳炎也不属于寒冰,它没有任何限制。混沌元素可以与任何元素(包括另一个混沌元素)相邻,连续经过任意多个混沌元素都是安全的。
问题:
年轻的法师,在这危机四伏的迷宫中,你有多少种方法能够安全抵达封印法阵(即迷宫终点右下角),并积累恰好
解答要求:
输入: 第一行三个整数
(n , m , T );接下来1 ≤ n , m ≤ 15 , 0 ≤ T ≤ 100 行,每行n 个0-9的整数,表示迷宫各房间的元素能量值。m 输出: 一个整数,表示满足所有生存条件的路径数量。

import sys # 导入 sys 模块,用于读取标准输入def solve():# 从标准输入读取全部内容并按空白字符切分,返回字符串列表input_data = sys.stdin.read().split()# 如果输入为空,直接返回if not input_data:return# 依次解析 n(行数)、m(列数)、T(目标能量值)n = int(input_data[0])m = int(input_data[1])T = int(input_data[2])# 初始化迷宫二维列表grid = []idx = 3 # 从输入数据列表的第 3 个下标开始读取迷宫元素for _ in range(n): # 逐行读取row = [] # 当前行for _ in range(m): # 逐列读取row.append(int(input_data[idx])) # 转为整数并加入当前行idx += 1 # 下标后移grid.append(row) # 将当前行加入迷宫# dp[i][j][k][s] 表示:# 走到坐标 (i,j) 时,累计能量为 k,且上一个元素的类型为 s 的路径数量# s 的含义:0 -> 混沌元素(0) 或无上一步(起点);1 -> 阳炎元素(奇数);2 -> 寒冰元素(偶数非零)# 使用四维列表,维度依次为 n、m、T+1、3dp = [[[[0] * 3 for _ in range(T + 1)] for _ in range(m)] for _ in range(n)]# 辅助函数:根据元素数值判断其类型def get_type(val):if val == 0: # 混沌元素return 0elif val % 2 == 1: # 奇数 -> 阳炎return 1else: # 偶数且非零 -> 寒冰return 2# 初始化起点 (0,0)start_val = grid[0][0] # 起点元素值if start_val <= T: # 如果起点能量已超过 T,则无解,不初始化start_type = get_type(start_val) # 起点元素类型dp[0][0][start_val][start_type] = 1 # 起点路径数为 1# 遍历整个迷宫for i in range(n): # 枚举行for j in range(m): # 枚举列if i == 0 and j == 0: # 起点已在初始化中处理,跳过continueval = grid[i][j] # 当前格子的元素值cur_type = get_type(val) # 当前格子的元素类型# 从上方 (i-1, j) 转移过来if i > 0:for k in range(T - val + 1): # 枚举上一个累计能量 k,保证 k + val <= Tfor prev_type in range(3): # 枚举上一步的元素类型if dp[i - 1][j][k][prev_type] > 0: # 如果该状态可达# 根据当前类型和上一步类型判断是否合法if cur_type == 0: # 当前是混沌元素,无任何限制dp[i][j][k + val][0] += dp[i - 1][j][k][prev_type]elif cur_type == 1 and prev_type != 1: # 阳炎,且上一步不是阳炎dp[i][j][k + val][1] += dp[i - 1][j][k][prev_type]elif cur_type == 2 and prev_type != 2: # 寒冰,且上一步不是寒冰dp[i][j][k + val][2] += dp[i - 1][j][k][prev_type]# 从左方 (i, j-1) 转移过来if j > 0:for k in range(T - val + 1): # 枚举上一个累计能量 kfor prev_type in range(3): # 枚举上一步的元素类型if dp[i][j - 1][k][prev_type] > 0: # 如果该状态可达if cur_type == 0: # 当前是混沌元素,无限制dp[i][j][k + val][0] += dp[i][j - 1][k][prev_type]elif cur_type == 1 and prev_type != 1: # 当前阳炎,上一步非阳炎dp[i][j][k + val][1] += dp[i][j - 1][k][prev_type]elif cur_type == 2 and prev_type != 2: # 当前寒冰,上一步非寒冰dp[i][j][k + val][2] += dp[i][j - 1][k][prev_type]# 最终答案:到达终点 (n-1, m-1) 且能量恰好为 T 的所有状态之和ans = sum(dp[n - 1][m - 1][T])print(ans) # 输出结果if __name__ == "__main__":solve() # 调用主函数
#include<iostream>// 用于输入输出#include<vector>// 用于动态数组using namespace std;// 辅助函数:根据元素值判断类型// 返回 0 表示混沌元素(0),1 表示阳炎(奇数),2 表示寒冰(偶数非零)intgetType(int val){if (val == 0) return 0;if (val % 2 == 1) return 1;return 2;}intmain(){ios::sync_with_stdio(false); // 关闭同步,加速输入输出cin.tie(nullptr); // 解除 cin 与 cout 的绑定,进一步加速int n, m, T;cin >> n >> m >> T; // 读取行数、列数、目标能量值// 读取迷宫数据vector<vector<int>> grid(n, vector<int>(m));for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {cin >> grid[i][j];}}// dp[i][j][k][s]:到达 (i,j) 时累计能量为 k,且上一元素类型为 s 的路径数// s:0 -> 混沌/无,1 -> 阳炎,2 -> 寒冰// 使用四维 vector 动态分配,维度依次为 n、m、T+1、3vector<vector<vector<vector<long long>>>> dp(n, vector<vector<vector<long long>>>(m, vector<vector<long long>>(T + 1, vector<long long>(3, 0))));// 初始化起点int startVal = grid[0][0];if (startVal <= T) { // 起点能量不能超过 Tint startType = getType(startVal);dp[0][0][startVal][startType] = 1;}// 遍历整个迷宫for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (i == 0 && j == 0) continue; // 起点已处理int val = grid[i][j]; // 当前格子元素值int curType = getType(val); // 当前元素类型// 从上方 (i-1, j) 转移if (i > 0) {for (int k = 0; k <= T - val; ++k) { // 保证 k + val <= Tfor (int prevType = 0; prevType < 3; ++prevType) {long long ways = dp[i - 1][j][k][prevType];if (ways == 0) continue; // 不可达则跳过// 根据当前类型和上一类型判断合法性if (curType == 0) {dp[i][j][k + val][0] += ways;} else if (curType == 1 && prevType != 1) {dp[i][j][k + val][1] += ways;} else if (curType == 2 && prevType != 2) {dp[i][j][k + val][2] += ways;}}}}// 从左方 (i, j-1) 转移if (j > 0) {for (int k = 0; k <= T - val; ++k) { // 保证 k + val <= Tfor (int prevType = 0; prevType < 3; ++prevType) {long long ways = dp[i][j - 1][k][prevType];if (ways == 0) continue; // 不可达则跳过if (curType == 0) {dp[i][j][k + val][0] += ways;} else if (curType == 1 && prevType != 1) {dp[i][j][k + val][1] += ways;} else if (curType == 2 && prevType != 2) {dp[i][j][k + val][2] += ways;}}}}}}// 最终答案:到达终点且能量恰好为 T 的所有状态之和long long ans = 0;for (int s = 0; s < 3; ++s) {ans += dp[n - 1][m - 1][T][s];}cout << ans << "\n"; // 输出结果return 0;}
#include<iostream>#include<vector>#include<cstring>using namespace std;// 获取元素类型: 0=混沌(0), 1=阳炎(奇数), 2=寒冰(偶数非0)intgetType(int val){if (val == 0) return 0;if (val % 2 != 0) return 1;return 2;}intmain(){int n, m, T;if (!(cin >> n >> m >> T)) return 0;vector<vector<int>> a(n, vector<int>(m));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> a[i][j];}}// dp[i][j][v][p]: 到达(i,j)总和为v且上一步类型为p的方案数// 由于 T 可能为 0,维度要开 T+1vector<vector<vector<vector<long long>>>> dp(n, vector<vector<vector<long long>>>(m, vector<vector<long long>>(T + 1, vector<long long>(3, 0))));// 初始化起点int start_val = a[0][0];if (start_val <= T) {dp[0][0][start_val][getType(start_val)] = 1;}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (i == 0 && j == 0) continue;int val = a[i][j];int cur_type = getType(val);// 遍历所有可能的来源方向(上、左)int dirs[2][2] = {{-1, 0}, {0, -1}};for (int d = 0; d < 2; d++) {int ni = i + dirs[d][0];int nj = j + dirs[d][1];if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;// 遍历来源的所有可能状态for (int v = 0; v <= T; v++) {for (int p = 0; p < 3; p++) {if (dp[ni][nj][v][p] == 0) continue;// 检查连续收集同种元素是否合法if (cur_type == 1 && p == 1) continue; // 连续阳炎if (cur_type == 2 && p == 2) continue; // 连续寒冰int new_v = v + val;if (new_v <= T) {dp[i][j][new_v][cur_type] += dp[ni][nj][v][p];}}}}}}// 统计终点 (n-1, m-1) 且总和恰好为 T 的所有状态long long ans = 0;for (int p = 0; p < 3; p++) {ans += dp[n - 1][m - 1][T][p];}cout << ans << endl;return 0;}