华为上机题汇总（十五）

注：编译环境为Visual Studio 2012，答案仅供参考。

目录

华为上机题汇总十五 目录第七十一题第七十二题第七十三题第七十四题第七十五题

第七十一题

71.渡口问题： 同类车辆先来先上，客车优于货车，客车上了4辆后才可以上货车，客车不足4辆可用货车补充。 客车为0，货车为1 输入：5 00101 输出：01324

#include <iostream> #include <queue> #include <vector> using namespace std; void Seq(queue<int> &cars, queue<int> &trucks, vector<int> &result){ int count = 0; while (!cars.empty() && !trucks.empty()) { if (count == 4) { result.push_back(trucks.front()); trucks.pop(); count = 0; } else { result.push_back(cars.front()); cars.pop(); count++; } } while (!cars.empty()) { result.push_back(cars.front()); cars.pop(); } while (!trucks.empty()) { result.push_back(trucks.front()); trucks.pop(); } } int main() { queue<int> cars, trucks; vector<int> result; int n; cin >> n; for (int i = 0; i < n; i++) { bool num; cin >> num; if (num) { trucks.push(i); } else { cars.push(i); } } Seq(cars,trucks,result); for (unsigned i = 0; i < result.size(); i++) { cout << result[i] << " "; } cout << endl; return 0; }

第七十二题

72.求两个整型数组的异集，即A+B-(A与B的交集)

#include <iostream> using namespace std; int cmp(const void *a, const void *b){ return *(int*)a - *(int*)b; } void intersection(int *a1, int l1, int *a2, int l2, int *output){ qsort(a1,l1,sizeof(int),cmp); qsort(a2,l2,sizeof(int),cmp); int b1 = 0, b2 = 0; while (b1 != l1 && b2 != l1) { if (a1[b1] < a2[b2]) { *output++ = a1[b1++]; } else if (a1[b1] > a2[b2]) { *output++ = a2[b2++]; } else { *output++ = a1[b1++]; b2++; } } while (b1 != l1) { *output++ = a1[b1++]; } while (b2 != l2) { *output++ = a2[b2++]; } }

第七十三题

73.输入包括多个行数，首先给出整数N（1<N<10000），接着给出N行文字，每一行文字至少包括一个字符，至多100个字符。如果给定文字中“t”（或“T”）的出现次数比“s”（或“S”）多，则可能为英文，否则可能为德文。输出包括一行，如果输入文字可能为英文，则输出English，否则输出Deutsch。

#include <iostream> #include <string> using namespace std; bool judge(const string &s){ int tCount = 0, sCount = 0; for (unsigned i = 0; i < s.size(); i++) { if (s[i] == 't' || s[i] == 'T') { tCount++; } else if (s[i] == 's' || s[i] == 'S') { sCount++; } } return tCount > sCount; } int main() { int n; cin >> n; cin.get(); while (n-- > 0) { string s; getline(cin,s); if (s.empty() || s.size() > 100) { cout << "Error" << endl; } else { cout << (judge(s) ? "English" : "Deutsch") << endl; } } }

第七十四题

74.飞机最少换乘次数问题 描述 设有n个城市，编号为0～n-1，m条单向航线的起点和终点由输入提供，寻找一条换乘次数最少的线路方案。 输入 第一行为三个整数n、m、v，表示城市数、单向航线数和起点城市。以下m行每行两个整数，表示一条边的起点、终点，保证不重复、不失败。2≤n≤20，1≤m≤190 输出 共n-1行，分别是从起点城市v到其他n-1个城市最少换乘次数，按照终点城市序号从小到大顺序输出，不能抵达时输出-1。 样例输入 3 2 0 0 1 1 2 样例输出 1 2

#include <iostream> #include <vector> using namespace std; bool canVisit(const vector<int> &v, int index){ for (unsigned i = 0; i < v.size(); i++) { if (index == v[i]) { return false; } } return true; } bool findWay(int current, const int end, int n, const vector<vector<int> > &map, vector<int> hasVisit, int &min){ if (current == end) { int size = hasVisit.size() - 1; if (size < min) { min = size; } return true; } bool flag = false; for (int i = 0; i < n; i++) { if (map[current][i] == 1 && canVisit(hasVisit,i)) { vector<int> tmp = hasVisit; tmp.push_back(i); flag |= findWay(i,end,n,map,tmp,min); } } return flag; } int main() { int n, m, start; cin >> n >> m >> start; vector<int> v(n,0); vector<vector<int> >map(n,v); while (m-- > 0) { int i1, i2; cin >> i1 >> i2; map[i1][i2] = 1; } for (unsigned i = 0; i < v.size(); i++) { if (i == start) { continue; } vector<int> hasVisit; hasVisit.push_back(start); int min = n; if (findWay(start,i,n,map,hasVisit,min)) { cout << min << endl; } else { cout << "-1" << endl; } } }

第七十五题

75连通OR不连通 描述 给定一个无向图，一共n个点，请编写一个程序实现两种操作： D x y 从原图中删除连接x，y节点的边。 Q x y 询问x，y节点是否连通

输入 第一行两个数n,m（5<=n<=40000,1<=m<=100000） 接下来m行，每行一对整数 x y （x,y<=n）,表示x,y之间有边相连。保证没有重复的边。 接下来一行一个整数 q（q<=100000） 以下q行每行一种操作，保证不会有非法删除。

输出 按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D

样例输入 3 3 1 2 1 3 2 3 5 Q 1 2 D 1 2 Q 1 2 D 3 2 Q 1 2 样例输出 C C D

#include <iostream> #include <vector> using namespace std; int main() { int n, m, q; cin >> n >> m; vector<int> v(n,0); vector<vector<int> >map(n,v); while (m-- > 0) { int i1, i2; cin >> i1 >> i2; map[i1-1][i2-1] = 1; map[i2-1][i1-1] = 1; } cin >> q; while (q-- >0) { char c; int i1, i2; cin >> c >> i1 >> i2; if (c == 'Q') { cout << (map[i1-1][i2-1] ? "C" : "D") << endl; } else if(c == 'D') { map[i1-1][i2-1] = 0; map[i2-1][i1-1] = 0; } } }