目錄
2021華為筆試第一道
緩存轉發資料包統計（100%）
解題思路：
參考代碼：
2021華為筆試第二題
查找知識圖譜中的執行個體知識（100%）
解題思路：
參考代碼：
2021華為筆試第三題
湖泊連通（100%）
解題思路：
參考代碼：
2021華為筆試第一道
緩存轉發資料包統計（100%）
題目描述
有k個節點的轉發隊列，每個節點轉發能力為m，緩存能力n(表示此節點可立即轉發m個包，剩餘的緩存，最多緩存n個包，再剩餘的丢棄，緩存的包在下一輪繼續轉發)。另外，此隊列中某些節點可能因故障需要直接跳過轉發，但不會有兩個連續故障的節點。現分兩輪操作，第一輪向此隊列發送a個資料包讓其轉發;第二輪，直接驅動讓緩存的資料包繼續轉發。
求兩輪最後可能收到的最少資料包總個數(如果第二輪緩存仍有資料包緩存包按丢棄處理) 1 <= k <= 40 1 <= m,n <= 1000 1 <= a <= 1000
例如:有兩個節點，節點1(轉發能力m:50，緩存能力n:60) 和節點2(m:30，n:25)，發送包數為120。
在沒有節點故障時:
輸入描述：第一行隊列長度k 第二行為k個節點轉發能力數組，以空格分隔。m,n以逗号分隔，例如10,20 11,21 12,22 第三行資料包個數a
2
50,60 30,25
120
輸出描述：
55
解釋:參見題目中的圖例，當第一個節點故障時，僅第二個節點轉發，此時收到的包最少。
解題思路：
雙層動态規劃。
1.首先是定義vector<vector<int>>cap(k+1, vector<int>(2))，儲存每個節點的轉發能力和緩存能力；(輸入節點為第0個節點)
2.定義vector<vector<int>>dp(k+1, vector<int>(2))，儲存每個節點第一次轉發的數量和第二次轉發的數量。(輸入節點第一次轉發數量為a，第二次轉發數量為0)
3.計算(dpfun())每個節點第一次轉發和第二次轉發的數量send1和send2：
第一次轉發的數量為從前一節點接收到的第一次轉發的數量和該節點轉發能力的最小值：
cur_cap[0]：為目前節點的轉發能力，cur_cap[1]：目前節點的緩存能力，也就是dp_fun()傳入的cap[i]。
pre[0]：上一節點第一次轉發的數量，pre[1]：上一節點第二次轉發的數量，也就是dp_fun()傳入的cap[i]。
send1 = min(pre[0], cur_cap[0]);
第二次轉發的數量需要分情況讨論，即第一次從上一節點轉發來的是否全部被轉走。不過最大轉發數量也就是轉發能力與緩存能力加上上一節點第二次轉發數量的最小值。
send2 = min(pre[1] + cur_cap[1], cur_cap[0]);
如果上一節點第一次轉發的數量大于目前節點的轉發能力(有緩存的情況)，則目前節點第二次轉發的數量為上一節點第二次轉發的數量加上目前節點第一次的緩存：
send2 = min(pre[1] + pre[0] - cur_cap[0], send2);
否則，目前節點第二次轉發的就是上一節點第二次轉發的數量：
send2 = min(pre[1], send2);
4.再分析節點存在故障的情況，因為不會有連續兩個節點故障，是以周遊所有節點，交叉轉發，然後每一個節點轉發情況取較小的一個。
vector<int> res1 = dpfun(dp[i - 1], cap[i]);//前一個節點沒有故障
vector<int> res2 = dpfun(dp[i - 2], cap[i]);//前一個節點故障
dp[i] = res1[0] + res1[1] <= res2[0] + res2[1] ? res1 : res2;
5.輸出最後一個節點，或倒數第二個節點轉發數量中的較小值即可。
res = min(dp[k][0] + dp[k][1], dp[k - 1][0] + dp[k - 1][1]);
參考代碼：
#include<bits/stdc++.h>
using namespace std;
//根據前一個節點發送的資料包 和目前節點的能力
//計算目前節點發送的資料包
//pre:前一節點(兩次)轉發的數量 cur_cap：目前節點(轉發能力，緩存能力)
vector<int> dpfun(vector<int> &pre, vector<int> &cur_cap) {
int send1 = min(pre[0], cur_cap[0]);//第一次發送的資料包量
int send2 = min(pre[1] + cur_cap[1], cur_cap[0]);//第二次發送的資料包數最大可能情況
//判斷第一次轉發來的資料包是否已被轉走
if (pre[0] - cur_cap[0] > 0)//來的資料包大于目前節點的轉發能力
send2 = min(pre[1] + pre[0] - cur_cap[0], send2);
else
send2 = min(pre[1], send2);
return vector<int> {send1, send2};
}
int main() {
int k, a;//節點數k 發送包數a
int res = 0;//兩輪最少能轉發的資料包
vector<vector<int>> cap;//cap(k, vector<int>(2)) 節點能力數組
cap.push_back(vector<int>{0, 0});//頭結點不需考慮能力
cin >> k;
int m1, n1;//m1轉發能力 n1緩存能力
char ch;
for (int i = 0; i < k; i++) {
cin >> m1 >> ch >> n1;
cap.push_back(vector<int>{m1, n1});
}
cin >> a;
vector<vector<int>> dp(k + 1, vector<int>(2));//第i個節點兩次發送的資料包數
dp[0][0] = a;//第0個節點第一次發送a個資料包
dp[0][1] = 0;//第0個節點第二次發送0個資料包
dp[1] = dpfun(dp[0], cap[1]);
res = min(dp[0][0] + dp[0][1], dp[1][0] + dp[1][1]);//如果隻有一個節點
if (k == 0)
cout << a << endl;
else {
for (int i = 2; i <= k; i++) {
vector<int> res1 = dpfun(dp[i - 1], cap[i]);//前一個節點沒有故障
vector<int> res2 = dpfun(dp[i - 2], cap[i]);//前一個節點故障
dp[i] = res1[0] + res1[1] <= res2[0] + res2[1] ? res1 : res2;
}
res = min(dp[k][0] + dp[k][1], dp[k - 1][0] + dp[k - 1][1]);
cout << res << endl;
}
return 0;
}
2021華為筆試第二題
查找知識圖譜中的執行個體知識（100%）
知識圖譜是一種結構化的語義網絡，用于描述實體世界中的概念及其執行個體的相關關系。可以把知識圖譜看成是一種有向圖，圖中的點是概念或執行個體，圖中的邊是概念及其執行個體的相關關系。
現定義一種簡單的知識圖譜
概念：包括父概念及其子概念，通過subClassOf關系關聯，父子概念可以有多個層級；執行個體:僅和概念之間通過instanceOf關系關聯: 關系:以三元組的形式表示，三元組是一個以空格為成員間分隔符的字元串。例如"student subClassOf person"表示student是person的子概念，"apple instanceOf fruit"表示apple是概念fruit的執行個體。給定一個知識圖譜，請編寫一個方法，可以根據一個概念查找其所有的執行個體。如果一個概念擁有子概念，那麼傳回的結果需要包含其所有子概念的執行個體;如果輸入的概念沒有執行個體，則傳回字元串"empty"(說明:輸出字元串文本不需要包含引号)。
給定的圖譜滿足以下限制: 1、有向圖中不存在環路 2、所有點和關系的定義對大小寫敏感
輸入描述：輸入第1行，表示圖譜中關系的數量n，取值範圍[1,10000] 從第2行到n+1行，表示圖譜中的關系，每一行是一個關系三元組第n+2行，表示待查找的元節點，是關系三元組中存在的點。每行字元的長度不超過100。
3
student subClassOf person
Tom inslenceOf student
Marry instanceOf person
person
輸出描述按字典序升序排列的字元串數組，其内容是概念及其子概念的所有執行個體。
Marry Tom
解釋:student是person的子概念，Tom是student的執行個體，Marry是person的 執行個體，Marry的字典序小于Tom，是以傳回Marry Tom。
解題思路1：
根據instanceOf查找它的父節點是否為target。
1.不管是 subClassOf還是instancOf，左邊的是子節點，右邊的是父節點。
2.定義哈希集合hash_set(instance)存儲instancOf的子節點(每一對的第一個輸入)。
3.定義哈希映射unordered_map(hash)存儲所有instanceOf和sunClassOf。
4.根據hash_set周遊其父節點是否能到達目标節點即可，若滿足則存入到set中，預設字典排序。若不滿足則一直向父關系尋找，直到該關系結束。
5.因為存儲滿足該執行個體的節點存在set中，是有序的。是以直接輸出，無需排序。
也就是用一個map存儲關系，用一個set存儲instance。然後周遊每一個instance，如果其父節點，或者一直向父關系周遊，如果能找到與目标概念相等，則該執行個體滿足要求，存在set裡。
參考代碼1：
#include <bits/stdc++.h>
using namespace std;
int main(int argc,char* argv[]){
int n;
cin>>n;
unordered_map<string,string> hash;//val是父節點
unordered_set<string> instance;//存儲instacnOf
string s1,s2,s3;
for(int i=0;i<n;++i){
cin>>s1>>s2>>s3;
if(s2=="instanceOf")
instance.insert(s1);
hash[s1]=s3;
}
string ss;
cin>>ss;
set<string> ret;
for(auto s:instance){
string s1=s;
while(hash.count(s1)){
if(hash[s1]==ss){
ret.insert(s);
break;
}
s1=hash[s1];
}
}
if(ret.size()==0){
cout<<"empty"<<endl;
}else{
int i=0;
for(auto s:ret){
if(i==0) cout<<s;
else cout<<" "<<s;
++i;
}
}
return 0;
}
解題思路2：
遞歸實作
1.定義兩個map，分别存儲instance，subClass。
map<string, vector<string>> subClass;//存儲subClassOf關系 可能會一對多
map<string, vector<string>> instance;//存儲instanceOf關系 可能會一對多
2.從子節點遞歸向上找
參考代碼2：
#include<bits/stdc++.h>
using namespace std;
void solve(map<string, vector<string>> &subClass, map<string, vector<string>> &instance, vector<string> &res, string &target) {
for (string str : instance[target])
res.push_back(str);
for (string str : subClass[target])
solve(subClass, instance, res, str);
return;
}
int main() {
int n;
cin >> n;
map<string, vector<string>> subClass;//存儲subClassOf關系 可能會一對多
map<string, vector<string>> instance;//存儲instanceOf關系 可能會一對多
for (int i = 0; i < n; i++) {
string head;
cin >> head;
string relation;
cin >> relation;
string tail;
cin >> tail;
if (relation == "subClassOf")
subClass[tail].push_back(head);
else
instance[tail].push_back(head);
}
string target;
cin >> target;
vector<string> res;
solve(subClass, instance, res, target);
sort(res.begin(), res.end());
if (res.empty())
cout << "empty";
else {
for (string str : res)
cout << str << " ";
}
cout << endl;
return 0;
}
2021華為筆試第三題
湖泊連通（100%）
題目描述
地圖上有多個湖泊，為增強湖泊的抗暴雨能力，需要在湖泊間挖出通道使得湖泊之間能夠連通(對角線視為不連通)。有的陸地是堅硬的石頭，挖通需要耗費的精力是普通陸地的2倍，即一個普通格子的長度為1，一個有堅硬石頭的格子的長度為2。地圖用二維矩陣表示，每個位置隻有三種可能，0為湖泊，1為普通陸地，2為堅硬的石頭，地圖最大為MN。需要傳回挖通所有湖泊的最短通道，如果通道不存在的話，傳回0 限制:M、N最大為20,湖泊個數不超過11。
輸入描述：第一行為M 第二行為N 第三行開始為M*N的地圖矩陣
5
4
0 1 1 0
0 1 0 0
0 1 0 0
0 1 0 1
1 1 1 1
輸出描述：傳回挖通所有湖泊的最短通道
1
解釋:地圖上共有2片湖泊，隻需要挖通1塊陸地，2片湖泊即可連通。
解題思路：
這道題是【斯坦納樹】的經典例題。斯坦納樹是這樣一類問題：帶邊權無向圖上有幾個（一般約10個）點是【關鍵點】，要求選擇一些邊使這些點在同一個聯通塊内，同時要求所選的邊的邊權和最小。
怎麼解決斯坦納樹問題？……其實，就是一種狀壓DP。
dp[i][j]表示以i号節點為根，目前狀态為j（j的二進制中已經與i連通的點對應位置為1）。
這個“以i為根”是哪來的呢？其實i可以是聯通塊中任意一個點，沒有額外限制，隻是引入這個i就可以DP了。
當根i不改變時（即合并兩個都包含i的聯通塊）狀态轉移方程是：
參考代碼：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;
typedef long long ll;
template <class T>
void read(T &x){
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
}
template <class T>
void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar('0' + x % 10);
}
const int INF = 0x3f3f3f3f;
int n, m, K, root, f[101][1111], a[101], ans[11][11];
bool inq[101];
typedef pair<int, int> par;
typedef pair<par, int> rec;
#define fi first
#define se second
#define mp make_pair
#define num(u) (u.fi * m + u.se)
rec pre[101][1111];
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
queue<par> que;
bool legal(par u){
return u.fi >= 0 && u.se >= 0 && u.fi < n && u.se < m;
}
void spfa(int now){
while(!que.empty()){
par u = que.front();
que.pop();
inq[num(u)] = 0;
for(int d = 0; d < 4; d++){
par v = mp(u.fi + dx[d], u.se + dy[d]);
int nu = num(u), nv = num(v);
if(legal(v) && f[nv][now] > f[nu][now] + a[nv]){
f[nv][now] = f[nu][now] + a[nv];
if(!inq[nv]) inq[nv] = 1, que.push(v);
pre[nv][now] = mp(u, now);
}
}
}
}
void dfs(par u, int now){
if(!pre[num(u)][now].se) return;
ans[u.fi][u.se] = 1;
int nu = num(u);
if(pre[nu][now].fi == u) dfs(u, now ^ pre[nu][now].se);
dfs(pre[nu][now].fi, pre[nu][now].se);
}
int main(){
read(n), read(m);
memset(f, 0x3f, sizeof(f));
for(int i = 0, tot = 0; i < n; i++)
for(int j = 0; j < m; j++){
read(a[tot]);
if(!a[tot]) f[tot][1 << (K++)] = 0, root = tot;
tot++;
}
for(int now = 1; now < (1 << K); now++){
for(int i = 0; i < n * m; i++){
for(int s = now & (now - 1); s; s = now & (s - 1))
if(f[i][now] > f[i][s] + f[i][now ^ s] - a[i]){
f[i][now] = f[i][s] + f[i][now ^ s] - a[i];
pre[i][now] = mp(mp(i / m, i % m), s);
}
if(f[i][now] < INF)
que.push(mp(i / m, i % m)), inq[i] = 1;
}
spfa(now);
}
write(f[root][(1 << K) - 1]), enter;
dfs(mp(root / m, root % m), (1 << K) - 1);
for(int i = 0, tot = 0; i < n; i++){
for(int j = 0; j < m; j++)
if(!a[tot++]) putchar('x');
else putchar(ans[i][j] ? 'o' : '_');
enter;
}
return 0;
}