华为2023春招笔试

（Author：DH）

1. 第一题

服务器有三种运行状态：空载、单任务、多任务，每个时间片的能耗分别为1、3、4；

每个任务由起始时间片和结束时间片定义时间；

如果一个时间片只有一个任务需要执行，则服务器处于单任务状态；

如果一个时间片有多个任务需要执行，则服务器处于多任务状态；

给定一个任务列表，请计算出从第一个任务开始，到所有任务结束，服务器的总能耗。

输入

一个只包含整数的二维数组

1
2
3
4
num
start0 end0
start1 end1
...

任务执行时间包含起始和结束时间片，即任务执行时间是左闭右闭的；

结束时间片一定大于等于起始时间片；

时间片范围:[0,1000000]；

任务数范围:[1,10000]；

输出

一个整数，代表服务器的总能耗。

样例输入

1
2
3
2
2 5
8 9

样例输出

1
20

解释

1
2
3
4
5
[0,1]没有任务需要执行，能耗为0
[2,5]处于单任务状态，能耗为3*4=12
[6,7]处于空载状态，能耗为1*2=2
[8,9]处于单任务状态，能耗为3*2=6
共计能耗为12+2+6=20

题解

暴力解法：我们可以暴力将区间起点和终点之间的位置遍历并+1，最后从头遍历即可得到答案

优化1：差分数组 ：差分数组可以利用O(1)的时间完成区间的值的增加，最后遍历一下整个区间即可得到结果。该算法复杂度在O(m) m = 1e6

优化2：差分数组仅在区间起始和末尾位置+1时值发生变化，因此我们其实可以不用遍历整个差分数组，只遍历更改区间的位置即可。该算法复杂度在O(nlogn) n = 1e4

2. 第二题

给定一棵树，这个树有n个节点，节点编号从0开始依次递增，0固定为根节点。在这棵树上有一个小猴子，初始时该猴子位于根节点（0号）上，小猴子一次可以沿着树上的边从一个节点挪到另一个节点，但这棵树上有一些节点设置有障碍物，如果某个节点上设置了障碍物，小猴子就不能通过连接该节点的边挪动到该节点上。问小猴子是否能跑到树的叶子节点（叶子节点定义为只有一条边连接的节点），如果可以，请输出小猴子跑到叶子节点的最短路径（通过的边最少），否则输出字符串NULL。

输入

第一行给出数字n，代表这个树有n个节点，节点编号从0开始依次递增，0固定为根节点，1<=n<=10000

第二行给出数字edge，表示接下来有edge行，每行是一条边

接下来的edge行是边：x y，表示x和y的节点有一条边连接

边信息结束后接下来一行给出数字block，表示接下来有block行，每行是一个障碍物

接下来的block行是障碍物：x，表示节点x上存在障碍物

输出

如果小猴子能跑到树的叶子节点，请输出小猴子跑到叶子节点的最短路径（通过的边最少），比如小猴子从0结果1到达2（叶子节点），那么输出"0->1->2"；否则输出"NULL"。注意如果存在多条最短路径，请按照节点序号排序输出，比如0->1和0->3两条路径，第一个节点0一样，则比较第二个节点1和3，1比3小，因此输出0->1这条路径。再如0->5->2->3和0->5->1->4，则输出0->5->1->4。

样例输入1

1
2
3
4
5
6
7
8
4
3
0 1
0 2
0 3
2
2
3

样例输出1

1
0->1

样例输入2

1
2
3
4
5
6
7
8
9
10
7
6
0 1
0 3
1 2
3 4
1 5
5 6
1
4

样例输出2

1
0->1->2

题解

本题BFS和DFS皆可，最优解应为BFS，因为DFS可能会访问一些无用的路径。在做BFS时可将邻接节点排序，以保证字典序最小。

3. 第三题

某商业楼中央空调管道老化导致漏水，为防止天花板长期积水而凹陷损坏，需要统一翻修前对凹陷部分开出水口进行引流。

现假设管道漏水位置呈从左至右直线排布，两侧为排水口，各点漏水量与引起的天花板凹陷深度成正比。

漏水受重力影响，会往天花板较深的凹陷处汇聚形成积水，为便于理解，如图。其中，

灰色格子表示由排水口流出；红色箭头为引流点，浅蓝与绿色格子用于区分各引流点所包含的漏水点，黑色横线表示各处积水的积水线。蓝色数字表示漏水点编号。黑色数字表示凹陷量。

现制定如下引流措施：

排水口规则：

（a）管道两侧默认为排水口，即凹陷量无限大，向两侧汇聚的漏水默认排除。如图中漏水点0、11.

引流点规则

（b）若某漏水点两侧相邻漏水点凹陷深度均小于此漏水点，为防止此漏水点积水，需作为引流点。如图中漏水点1、4、10.

（c）若某凹陷处最深为连续相同凹陷点，则为一个引流点。如图中漏水点7、8.

漏水点引流规则：

（d）若某漏水点两侧相邻漏水点存在一处凹陷深度大于此漏水点，则向凹陷更深处引流。如图中漏水点2、6.

（e）若某漏水点两侧相邻漏水点凹陷深度均大于或等于此漏水点，且两侧引流点凹陷深度不同，则向深的引流点引流。如图中漏水点3.

（f）若某漏水点两侧相邻漏水点凹陷深度均大于或等于此漏水点，且两侧引流点凹陷深度相同，则向左侧引流。如图中漏水点3.

计算形成的积水线下，各引流点的引流量（即所包含的各漏水点的积水量之和）

输入

“从左至右”各漏水点的漏水量，即凹陷量。以“空格”区分各点漏水量。

输出

“从左至右”各引流点的引流量，以“空格”区分各点引流量。

样例输入

1
1 5 3 4 6 5 1

样例输出

1
4 14
**参考代码** 
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
#include<iostream>
#include<set>
using namespace std;
set<int> st;
long long diff[1000500];
void add(int x, int y, int size){
    diff[x] += size;
    diff[y + 1] -= size;
}
int main(){
	int n;
	int x, y;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> x >> y;
		add(x, y, 1);
		st.insert(x);
		st.insert(y + 1);
	}
	int pre = 0;
	int now = 0;
	int value = 0;
	int long ans = 0;
	for(auto & num : st){
		ans += value * (num - pre);
		now = now + diff[num];
		if(now == 0)
			value = 1;
		else if(now == 1)
			value = 3;
		else if(now >= 1)
			value = 4;
		pre = num;
	}
	cout << ans;
}

参考代码

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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> e[10050];
bool f[10050];
vector<int> ans;
vector<int> path; 
int res = 0x3f3f3f3f;
bool judge(){
	for(int i = 0; i < res; i++){
		if(path[i] < ans[i]){
			return true;
		}else if(path[i] > ans[i]){
			return false;
		}
	}
	return false;
}
void dfs(int x, int p){
	if(f[x]){
		return;
	}
	bool vis = false;
	for(int i = 0; i < e[x].size(); i++){
		if(e[x][i] == p){
			continue;
		} 
		vis = true;
		path.push_back(e[x][i]);
		dfs(e[x][i], x);
		path.pop_back();
	} 
	if(!vis){
		if(path.size() < res){
			res = path.size();
			ans = path;
		}else if(path.size() == res){
			if(judge())
				ans = path;
		}
	}
}
int main(){
	int n, m, block;
	cin >> n >> m;
	int x, y;
	for(int i = 0; i < m; i++){
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	cin >> block;
	while(block--){
		cin >> x;
		f[x] = true;
	}
	path.push_back(0);
	dfs(0, -1);
	if(res == 0x3f3f3f3f){
		cout << "NULL" ;
	}else{
		cout << 0;
		for(int i = 1; i < ans.size(); i++){
			cout << "->" << ans[i]; 
		}
	}
	
}

参考代码

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
#include<iostream>
#include<vector>
using namespace std;
vector<int> pai;
int arr[100050];
int m[100050];
bool f[100050];
int b[100050];
int main(){
	int n = 0;
	while(cin >> arr[n]){
		n++;
	}
	pai.push_back(0);
	for(int i = 1; i < n - 1; i++){
		if(arr[i - 1] < arr[i] && arr[i + 1] < arr[i]){
			pai.push_back(i);
			b[i] = i;
			f[i] = true;
		}else if(arr[i - 1] < arr[i] && arr[i] == arr[i + 1]){
			int t = i;
			while(i < n - 1 && arr[i] == arr[i + 1]){
				i++;
			}
			if(arr[i] > arr[i + 1]){
				pai.push_back(i);
				f[i] = true;
				while(t < i){
					b[t] = i;
					f[t] = true;
					t++;
				}
			}
		}
	}
	pai.push_back(n - 1);
	vector<int> ans(pai.size(), 0);
	m[n - 1] = arr[n - 1];
	for(int i = n - 2; i >= 1; i--){
		m[i] = min(arr[i], m[i + 1]);
	}
	for(int i = 1; i < n - 1; i++){
		int l = lower_bound(pai.begin(), pai.end(), i) - pai.begin() - 1;
		int r = l + 1;
		if(f[i]){
			ans[r] += (arr[i] - m[i]);
		}else if(arr[pai[l]] > arr[i] && arr[pai[r]] <= arr[i]){
			ans[l] += (arr[i] - m[i]);
		}else if(arr[pai[l]] <= arr[i] && arr[pai[r]] > arr[i]){
			ans[r] += (arr[i] - m[i]);
		}else if(arr[pai[l]] >= arr[i] && arr[pai[r]] >= arr[i]){
			if(arr[pai[l]] >= arr[pai[r]]){
				ans[l] += (arr[i] - m[i]);
			}else{
				ans[r] += (arr[i] - m[i]);
			}
		}
	}
	for(int i = 1; i < ans.size() - 1; i++){
		cout << ans[i] << " ";
	}
}
笔试
#笔试
华为2023春招笔试
https://tech.jasonczc.cn/2023/job/huawei-2023-4-20/
作者
CZY
发布于
2023年4月19日
许可协议