华为4.10机试
4.15补充说明
看到有不少牛友收藏，在此分享一点点小经验吧
华为每场机试都共3道题，100,200,300，时长2h，题目的难度和分值往往不成正比，做题顺序可能对最终结果有很大影响；每道题都可以用不同种语言按；提交可以看到过了多少测试点，每道题得分是过的比例乘题目分值（不会显示得几分，但可以自己算）；允许使用本地编译器；有摄像头录制，旁人误入可能会被判作弊。及格线150，貌似有复活赛？牛友们可以在评论区说说看
做了不少华为机试的题目，给我的感受是题目很长，一上来就给你个下马威，一定一定要耐心阅读。用C++的话需要对STL熟练掌握，否则做模拟题很耽误事，会在容器和函数的使用细节上纠结导致时间浪费。by the way，感觉华为似乎不是很喜欢考DP……
-----------------------------------------------------------
做了一个多小时后，第一题68%，第二题32%，第三题0，差点不及格（150），最终在不断的debug下，100% 100% 15%，浅浅记录一下吧
第一题是一道大模拟，考察STL熟练度（c++是这样子的），还有阅读理解，这里要注意“订单”唯一性，我选择用时间戳+用户+因子的字符串作为key
第二题可以用并查集，我是用bfs，假如遍历到一个有其相似图片的图片就搜索出整个集合，要注意别忽略了“自成一派”的图片也存进所有集合情况
1. 云服务计费
编写一个程序为某云服务计算客户话单，输入为某云服务的计费日志和各种计费因子的计费单价的列表，计费日志内容包含时间戳、客户标识、计费因子、计费时长4个字段。日志中如果同一客户同一计费因子在相同时间戳上报多次话单只能计费一次，选先上报的日志计费。计算每个客户的话单总费用。
解答要求
时间限制: C/C++ 1000ms,其他语言: 2000ms内存限制: C/C++ 256MB,其他语言: 512MB
输入
第1行表示计费日志的条数n，是一个正整数，范围是1<=n<=1000
第2到n+1行表示云服务的计费日志，共4列，第1列表示时间戳(是一个数字字符串，长度为10) 、第2列表示客户标识(是一个字符串，长度为1-16)，第3列表示计费因子 (是一个字符串，长度为1-16，计费因子查不到时认为计费因子单价是0），第四列表示计费时长时长（范围为0-100，当计费时长不在范围内要认为是计费日志有问题，当成计费为0处理)，这4个字段使用逗号分隔
第n+2行表示计费因子的数量m，m是一个正整数，范围是1<=m<=100
第n+3到n+3+m行表示各种计费因子的计费单价的列表，该表有2列,第1列表示计费因子 (是一个字符串，长度为1-16)，第2列表示单价(是一个正整数，范围为1~100)，这2个字段使用逗号分
输出
每个客户的话单总费用,共2列，第1列表示客户名，第2列表示话单费用，2列用逗号分割，输出按客户标识字典序升序排序
样例
输入
5 1627845600,client1,factorA,10 1627845605,client2,factorB,15 1627845610,client1,factorA,5 1627845610,client1,factorB,8 1627845620,client2,factorB,20 2 factorA,5 factorB,7
输出
client1,131 client2,245
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
string s[N]; // 存储输入的n个字符串
unordered_map<string, int> value; // 不同节点对应的单价
unordered_map<string, int> info; // 时间戳+名字+节点（这边可以用set）
unordered_map<string, int> cost; // 不同用户对应的消费
vector<string> nameall; // 所有用户的名字
int main()
{
int n, m;
cin >> n;
for (int i = 0; i < n; i++)
cin >> s[i];
cin >> m;
for (int i = 0; i < m; i++)
{
string str, str1, str2;
cin >> str;
int len = str.length();
// 存储不同节点对应的单价
for (int j = 0; j < len; j++)
{
if (str[j] == ',')
{
str1 = str.substr(0, j); // 节点
str2 = str.substr(j + 1, len - j); // 单价
// cout<<str1<<" "<<str2<<endl;
int t = stoi(str2);
value[str1] = t;
}
}
}
for (int i = 0; i < n; i++)
{
int len = s[i].length();
int cnt = 0; // 逗号的个数
int d1, d2, d3; // 第1、2、3个逗号的下标
for (int j = 0; j < len; j++)
{
if (s[i][j] == ',')
{
if (cnt == 0)
d1 = j;
else if (cnt == 1)
d2 = j;
else if (cnt == 2)
d3 = j;
cnt++;
}
}
// cout<<"d1="<<d1<<"d2="<<d2<<"d3="<<d3<<endl;
string name = s[i].substr(d1 + 1, d2 - d1 - 1);
bool sign = false;
for (auto t : nameall)
{
if (t == name)
sign = true;
}
if (!sign)
nameall.push_back(name);
string ti = s[i].substr(0, d1);
string factor = s[i].substr(d2 + 1, d3 - d2 - 1);
string hhour = s[i].substr(d3 + 1, len - d3 - 1);
int hour = stoi(hhour);
if (hour < 0 || hour > 100)
hour = 0; // 题目要求不在范围按0算
string inf = ti + name + factor;
if (info[inf] == 0) // 题目要求，如果有同一时间同一用户同一节点重复信息，只算第一个
{
cost[name] = cost[name] + value[factor] * hour;
info[inf] = 1;
}
// cout<<"name="<<name<<"facotr="<<factor<<"hour="<<hour<<endl;
}
sort(nameall.begin(), nameall.end());
for (auto name : nameall)
{
cout << name << "," << cost[name] << endl;
}
return 0;
}
2. 相似图片分类
小明想要处理一批图片，将相似的图片分类。他首先对图片的特征采样，得到图片之间的相似度，然后按照以下规则判断图片是否可以归为一类:
1)相似度>0表示两张图片相似，
2)如果A和B相似，B和C相似，但A和C不相似。那么认为A和C间接相似，可以把ABC归为一类，但不计算AC的相似度
3)如果A和所有其他图片都不相似，则A自己归为一类，相似度为0.给定一个大小为NxN的矩阵M存储任意两张图片的相似度，M[i][j]即为第i个图片和第j个图片的相似度，请按照"从大到小”的顺序返回每个相似类中所有图片的相似度之和。
输入
第一行一个数N，代表矩阵M中有N个图片，下面跟着N行，每行有N列数据，空格分隔(为了显示整弃，空格可能为多个) 代表N个图片之间的相似度。
约束：1.0<N<=900 0<=M[i][j]<=100,输入保证M[i][i] =0,M[i][j]=M[j][i]
输出
每个相似类的相似度之和。格式为:一行数字，分隔符为1个空格。
样例
输入
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
输出
65 25
考试代码忘记保存了，下面是考完后复盘再写的。
#include<bits/stdc++.h>
using namespace std;
const int N = 910;
int idx = 0; // 目前算到第几个集合
int g[N][N]; // 存图
vector<int>v[N]; // 邻接矩阵
vector<int>res; // 每个集合对应的相似值之和
vector<int>jihe[N]; // 每个集合的点
bool st[N]; // 是否结束访问
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> g[i][j];
if (g[i][j])
v[i].push_back(j);
}
}
for (int i = 0; i < n; i++)
{
// 如果邻接矩阵为空说明没有相似的图，自成一派
if (v[i].size() == 0)
{
//cout<<"i="<<i<<",idx="<<idx<<endl;
st[i]=true;
jihe[idx++].push_back(i); // 一开始没加进去，只能过32%数据点
continue;
}
if (st[i])
continue;
//cout<<"i="<<i<<",idx="<<idx<<endl;
queue<int> q;
q.push(i);
st[i]=true;
jihe[idx].push_back(i);
// bfs展开
while (q.size())
{
int t = q.front();
q.pop();
st[t] = true;
for (auto x : v[t])
{
if (!st[x])
{
q.push(x);
jihe[idx].push_back(x);
}
}
}
idx++;
}
// 计算每一个集合的相似值之和
for (int i = 0; i < idx; i++)
{
int t = 0, len = jihe[i].size();
for (int j = 0; j < len; j++)
{
for (int k = j + 1; k < len; k++)
{
int x = jihe[i][j], y = jihe[i][k];
t += g[x][y];
}
}
res.push_back(t);
}
/*debug检查每个集合是否正确
for (int i = 0; i < idx; i++)
{
cout << "jihe[" << i << "]:";
for (auto x : jihe[i])
cout << x;
cout << endl;
}
cout << "idx=" << idx << endl;
*/
// 降序且输出
sort(res.begin(), res.end(), cmp);
int len = res.size();
for (int i = 0; i < len - 1; i++)
cout << res[i] << " ";
cout << res[len - 1];
return 0;
}
3. 网络保卫战
公有云的某个region内，N个网络节点组网情况可以使用一个n* n的矩阵matrix表示，在这个组网图中，matrix[i][j] = p 时，表示用户在编号为 i的节点访问编号为j的节点时，必须在 i节点上具有>=p 的权限等级(p=0时表示无法通过第i节点访问j节点)，如果用户成功访问了j节点，那么它在j节点上的权限等级调整为 P。
exposed 为一个整数数组，表示暴露在公网上的网络节点的编号列表。某天扫描发现这批暴需在公网的节点存在被外部恶意攻击风险且该攻击会影响到可访问的其他节点，并可以持续传递进行攻击，被恶意攻击的节点从公网访问时，攻击者获得了ROOT 权限(权限等级为10，即最大值)。
小李是一名网络安全工程师，为了在有限的时间内尽可能的减少故障带来的损失，需要立即将某个节点从公网"下线"。
假设攻击结束时，被攻击过的节点数量为R，请帮小李计算出将哪个节点下线能使R尽可能小，如果答案有多个节点，返回索引最小的那个节点。
请注意：从公网“下线”的节点，不会受到来自公网的攻击，但仍然可能被“可访问”的其他节点传递攻击。
解答要求
时间限制: C/C++ 5000ms,其他语言: 10000ms内存限制: C/C++ 128MB，其他语言: 256MB
输入
输入的第一行是网络节点数量N后续的N行，每行N个数字v，以空格分割，形成一个N*N的矩阵，表示网络节点组网的矩阵。最后一行，输入 exposed 数组，表示暴露在公网上的网络节点的编号列表，数组元素不会重复。输入范围说明： 2<=n<=24 0<=v<=10 0<=exposed[i]<=n-1
输出
输出在 exposed 数组中，计划"下线”的那个节点的编号。
样例1
输入
4 1 0 0 0 0 1 2 0 0 1 1 4 0 0 3 1 1 3
输出
3
这题的话考场上来不及做，直接测试各种结果，最后过了15%，后续找时间再做……
更新
#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int a[N][N];
bool st[N];
int n;
int dfs(int id,int v)
{
int res=0;
for(int i=0;i<n;i++)
{
if(i!=id&&a[id][i]&&a[id][i]<=v&&!st[i])
{
st[i]=true;
res+=dfs(i,a[id][i]);
st[i]=false;
}
}
return res+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;
int node;
int m;
cin>>m;
while(m--)
{
cin>>x;
for(int i=0;i<n;i++)
{
if(i==x)continue;
st[x]=true;
int t=dfs(x,10);
if(t>res)
{
res=t;
node=x;
}
st[x]=false;
}
}
cout<<node;
return 0;
}
#华为机试##华为##笔试##暑期实习#
华为工作强度 756人发布
查看49道真题和解析
