大厂笔试经验贴——CPP改写

2026.4.26 pdd
下面是四道题的 C++ 改写代码，保持原有算法逻辑，使用 C++ 标准库实现。

第一题：二维费用背包

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 1e9;

int main() {
    int n, m, t;
    cin >> n >> m >> t;
    vector<tuple<int, int, int, int>> tasks(n);
    for (int i = 0; i < n; ++i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        tasks[i] = {a, b, c, d};
    }

    // f[j][k] = 使用恰好j个token完成恰好k个任务的最小时间
    vector<vector<int>> f(m + 1, vector<int>(n + 1, INF));
    f[0][0] = 0;

    for (auto [a, b, c, d] : tasks) {
        for (int j = m; j >= 0; --j) {
            for (int k = n; k >= 1; --k) {
                if (j >= a) f[j][k] = min(f[j][k], f[j - a][k - 1] + b);
                if (j >= c) f[j][k] = min(f[j][k], f[j - c][k - 1] + d);
            }
        }
    }

    int ans = 0;
    for (int k = n; k >= 0; --k) {
        for (int j = 0; j <= m; ++j) {
            if (f[j][k] <= t) {
                ans = k;
                break;
            }
        }
        if (ans) break;
    }
    cout << ans << endl;
    return 0;
}

第二题：贪心 + 二分查找（使用 multiset）

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<pair<int, int>> contents(n); // (r, l)
        for (int i = 0; i < n; ++i) {
            int l, r;
            cin >> l >> r;
            contents[i] = {r, l};
        }
        vector<int> slots(m);
        for (int i = 0; i < m; ++i) cin >> slots[i];

        // 将推荐位排序并放入 multiset（允许重复）
        multiset<int> slotSet(slots.begin(), slots.end());
        // 按右端点升序排序
        sort(contents.begin(), contents.end());

        int ans = 0;
        for (auto [r, l] : contents) {
            auto it = slotSet.lower_bound(l);
            if (it != slotSet.end() && *it <= r) {
                ++ans;
                slotSet.erase(it);
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

第三题：BFS 坐标重建

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int total = n * m;
    int k;
    cin >> k;

    // 方向映射
    // from_a: 从 a 看 b 的偏移
    // from_b: 从 b 看 a 的偏移
    vector<vector<tuple<int, int, int>>> adj(total + 1);
    int first = 0;

    for (int i = 0; i < k; ++i) {
        int a, b;
        string d;
        cin >> a >> b >> d;
        if (first == 0) first = a;
        int dr1, dc1, dr2, dc2;
        if (d == "U") {
            dr1 = 1; dc1 = 0;
            dr2 = -1; dc2 = 0;
        } else if (d == "B") {
            dr1 = -1; dc1 = 0;
            dr2 = 1; dc2 = 0;
        } else if (d == "L") {
            dr1 = 0; dc1 = 1;
            dr2 = 0; dc2 = -1;
        } else { // "R"
            dr1 = 0; dc1 = -1;
            dr2 = 0; dc2 = 1;
        }
        adj[a].emplace_back(b, dr1, dc1);
        adj[b].emplace_back(a, dr2, dc2);
    }

    vector<int> row(total + 1, 0), col(total + 1, 0);
    vector<bool> vis(total + 1, false);
    queue<int> q;
    vis[first] = true;
    q.push(first);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [v, dr, dc] : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                row[v] = row[u] + dr;
                col[v] = col[u] + dc;
                q.push(v);
            }
        }
    }

    // 归一化坐标
    int min_r = *min_element(row.begin() + 1, row.end());
    int min_c = *min_element(col.begin() + 1, col.end());
    vector<vector<int>> grid(n, vector<int>(m, 0));
    for (int i = 1; i <= total; ++i) {
        int r = row[i] - min_r;
        int c = col[i] - min_c;
        grid[r][c] = i;
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << grid[i][j] << (j == m-1 ? '\n' : ' ');
        }
    }
    return 0;
}

第四题：二分答案 + 树上贪心

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int check(int D, int n, const vector<vector<int>>& children) {
    int cnt = 0;
    vector<int> max_dist(n + 1, 0);
    // 后序遍历顺序：先获取前序顺序再反转
    vector<int> order;
    vector<int> stack = {1};
    while (!stack.empty()) {
        int u = stack.back();
        stack.pop_back();
        order.push_back(u);
        for (int v : children[u]) {
            stack.push_back(v);
        }
    }
    reverse(order.begin(), order.end());

    for (int u : order) {
        int md = 0;
        for (int v : children[u]) {
            if (max_dist[v] >= 0) {
                md = max(md, max_dist[v] + 1);
            }
        }
        if (md >= D) {
            cnt++;
            max_dist[u] = -1; // 被覆盖
        } else {
            max_dist[u] = md;
        }
    }
    // 根节点若未被覆盖，需要额外放置
    if (max_dist[1] >= 0) cnt++;
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<vector<int>> children(n + 1);
        if (n > 1) {
            for (int i = 2; i <= n; ++i) {
                int p;
                cin >> p;
                children[p].push_back(i);
            }
        }
        int lo = 0, hi = n - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (check(mid, n, children) <= k) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        cout << lo << '\n';
    }
    return 0;
}

以上代码均保持了原有算法的核心思想，并适配了 C++ 的语法和常用数据结构。