4月19日华为实习笔试
T1 100%
对区间排序然后分类讨论
#include <bits/stdc++.h> #include <iostream> using namespace std; static bool cmp(pair<int, int>& a, pair<int, int>& b) { bool res; if(a.first != b.first) res = a.first < b.first; else res = a.second < b.second; return res; } int main() { int n; cin >> n; vector<pair<int, int>> v(n); for(int i = 0; i < n; i++) cin >> v[i].first >> v[i].second; sort(v.begin(), v.end(), cmp); int res = 0; int l = v[0].first - 1, r = v[0].first - 1, mid = v[0].first - 1; for(auto& p : v) { int lp = p.first, rp = p.second; if(lp > r) { res += lp - r - 1; res += 3 * (rp - lp + 1); l = lp; r = rp; mid = lp - 1; } else if(rp > r) { if(mid < lp) { res += r - lp + 1; mid = r; } else { res += r - mid; mid = r; } res += 3 * (rp - r); r = rp; } else { if(mid < lp) { res += rp - lp + 1; mid = rp; } else if(mid <= rp) { res += rp - mid; mid = rp; } } } cout << res << endl; }
T2 100%
BFS
#include <bits/stdc++.h> #include <iostream> using namespace std; // int dfs(int node, map<int, vector<int>>& mp, vector<int>& isleave, vector<int>& blocknode, vector<int>& father) { // if(isleave[node] == 1 && node > 0) { // return node; // } // for(auto& p : mp[node]) { // if(father[node] == p || blocknode[p]) continue; // father[p] = node; // int t = dfs(node, mp, isleave, blocknode, father); // if(t > 0) return t; // } // return -1; // } int main() { int n; cin >> n; int edge; vector<int> father(n, 0); cin >> edge; // int mat[n][n]; map<int, vector<int>>mp; int x, y; vector<int> isleave(n, 0), visit(n, 0); for(int i = 0; i < edge; i++) { cin >> x >> y; // mat[x][y] = 1; // mat[y][x] = 1; mp[x].emplace_back(y); mp[y].emplace_back(x); isleave[x]++; isleave[y]++; } int block, t; vector<int>blocknode(n, 0); cin >> block; for(int i = 0; i < block; i++) { cin >> t; blocknode[t] = 1; } if(blocknode[0]) { cout << "NULL" << endl; return 0; } if(n == 1) { if(blocknode[0]) { cout << "NULL" << endl; } else cout << 0 << endl; return 0; } // int res = dfs(0, mp, isleave, blocknode, father); deque<int> q; q.push_back(0); int res = -1; while(!q.empty()) { int node = q.front(); q.pop_front(); if(isleave[node] == 1 && node > 0) { res = node; break; } for(auto& p : mp[node]) { if(father[node] == p || blocknode[p]) continue; father[p] = node; q.push_back(p); // cout << p << endl; } } if(res == -1) { cout << "NULL" << endl; return 0; } vector<int> path; path.emplace_back(res); while(father[res] != 0) { path.emplace_back(father[res]); res = father[res]; } cout << 0; // for(auto& p : path) cout << p << endl; for(int i = path.size() - 1; i >= 0; i--) { cout << "->" << path[i]; } }
T3 放弃