2023.8.10 Zoom 秋招 C++ 开发笔试题

第一题

背景是树，本质是图的题目，根据条件建立图以后，用 DFS 或者 BFS 遍历即可

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    int blue;
    int red;
    Node(int v, int b, int r) : val(v), blue(b), red(r) {}
};

int main() {
    int n, a, b, r;
    string s;
    cin >> n >> s;
    vector<vector<int>> graph(n + 1);
    for (int i = 1; i < n; ++i) {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    long ans = 0;
    unordered_set<int> visit;
    queue<Node> q;
    b = s[0] == 'B';
    q.emplace(1, b, 1 - b);
    visit.insert(1);
    while (not q.empty()) {
        auto t = q.front();
        q.pop();
        ans += abs(t.blue - t.red);
        for (int i : graph[t.val]) {
            if (not visit.count(i)) {
                b = s[i - 1] == 'B' ? 1 : 0;
                r = 1 - b;
                q.emplace(i, t.blue + b, t.red + r);
            } else
                visit.insert(t.val);
        }
    }
    cout << ans;
}

第二题

并查集，提示数组越界，只过了80%，有点急事只能提前交卷了

#include <bits/stdc++.h>
using namespace std;

vector<int> ufs(10005);
void init() {
    iota(ufs.begin(), ufs.end(), 0);
}
int findRoot(int x) {
    return ufs[x] == x ? x : ufs[x] = findRoot(ufs[x]);
}
void unionSets(int a, int b) {
    ufs[findRoot(a)] = findRoot(b);
}

int main() {
    init();
    int q, n, c, m = 0;
    string s, name;
    unordered_map<string, vector<int>> user;
    unordered_map<string, int> stock;
    cin >> q;
    while (q--) {
        cin >> c;
        if (c == 1) {
            cin >> name >> n;
            for (int i = 0; i < n; ++i) {
                cin >> s;
                if (not stock.count(s))
                    stock[s] = m++;
                user[name].push_back(stock[s]);
                if (i > 0)
                    unionSets(stock[s], user[name][0]);
            }
        } else {
            cin >> name;
            if (not user.count(name)) {
                cout << "error" << endl;
                continue;
            } else {
                int root = findRoot(user[name][0]);
                int num = 0;
                for (int i = 0; i < m; ++i) {
                    if (findRoot(i) == root)
                        ++num;
                }
                cout << num - user[name].size() << endl;
            }
        }
    }
}