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 放弃