2026-10-18 秋招XX服务端研发笔试复盘

题目一：最多换乘一次的公交最小费用

题目大意

给定起点 S、终点 T 和 n 条公交线路。每条线路的费用固定，只能顺着站点顺序乘坐，不能反向。可以直达，也可以在公共站点换乘一次，最多坐两条线路。求从 S 到 T 的最小费用，无法到达输出 -1。

我的思路

最多坐两条线路，就把路径在换乘站拆开。我用了两个哈希表：

ump[0][x]：从 S 出发，坐一条线路到 x 的最低费用；
ump[1][x]：从 x 出发，坐一条线路到 T 的最低费用。

每条线路按站点顺序读入。遇到 S 之后，把后面的站点更新进第一个表；遇到 T 时，回头把这条线路此前经过的站点更新进第二个表。如果此前已经遇到 S，这条线路也能直达，单独更新直达费用。

最后枚举换乘站 x，两边都能走通，就用 ump[0][x] + ump[1][x] 更新答案，再和直达费用比较。

代码

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

const int maxm = 1e4 + 7;
const int maxn = 1e3 + 7;
const int oo = 1e9 + 7;

int S, T, n;
int c[maxn], m[maxn];
vector<int> id[maxn];
unordered_map<int ,int> ump[2];


int main() {
    scanf("%d%d%d", &S, &T, &n);
    int ans = oo;
    for(int i = 1; i <= n; i++) {
        int hass = 0;
        scanf("%d%d", &c[i], &m[i]);
        for(int j = 1; j <= m[i]; j++) {
            int tmp;
            scanf("%d", &tmp);

            if(hass) {
                if(ump[0].find(tmp) == ump[0].end()) {
                    ump[0][tmp] = c[i];
                }
                else {
                    ump[0][tmp] = min(ump[0][tmp], c[i]);
                }
            }

            if(tmp == S) {
                hass = 1;
            }
            else if(tmp == T) {
                for(int k = 0; k < j - 1; k++) {
                    if(ump[1].find(id[i][k]) == ump[1].end()) {
                        ump[1][id[i][k]] = c[i];
                    }
                    else {
                        ump[1][id[i][k]] = min(ump[1][id[i][k]], c[i]);
                    }
                }
                if(hass) {
                    ans = min(ans, c[i]);
                }
            }

            id[i].emplace_back(tmp);

        }
    }
    // printf("%d\n", ans);
    for(int i = 1; i <= 10000; i++) {
        if(ump[0][i] && ump[1][i]) {
            ans = min(ans, ump[0][i] + ump[1][i]);
        }
    }

    printf("%d\n", (ans == oo) ? -1 : ans);
    return 0;
}
// 64 位输出请用 printf("%lld")

复盘：正反两次扫描

这里可以少绕一点。原来一边读入一边处理，遇到 T 还要回头遍历，几件事挤在一起。

可以先读完整条线路，再正向、反向各扫一次。

正向扫：遇到 S 之后，更新 from[x]，表示从 S 坐一条线路到 x 的最低费用；
反向扫：遇到 T 之后，更新 to[x]，表示从 x 坐一条线路到 T 的最低费用。

最后比较 from[T] 和所有 from[x] + to[x]。直达已经包含在 from[T] 里，不用再另外维护一个答案。两个方向的处理完全对称，也不用在遇到 T 时回头枚举前面的站点。

这一题主要是把处理过程拆清楚。两张费用表的思路没变，不需要为了改写再换一套算法。

题目二：被至少 K 个区间覆盖的整数个数

题目大意

给定数轴上的 n 个闭区间 [l_i, r_i] 和一个整数 k，统计有多少个正整数位置被至少 k 个区间覆盖。

我的思路

我用了离散化加差分。这里要数的是整数点，不能直接拿离散化后的下标差当答案，所以除了区间端点，还把每个端点左右的 x-1、x、x+1 加进了坐标集合，正整数范围之外的点不加。

排好序以后，inc 把原坐标映射到离散化下标，de 再把下标映射回原坐标。每个区间在左端点加一，右端点之后减一，做前缀和得到覆盖数。

扫描时用 be 记当前满足条件的连续段起点。覆盖数低于 k 时，这一段结束，用原坐标算出整数点个数并累加；最后再处理还没结束的那一段。

整体时间复杂度是 $O(n \log n)$ ，主要花在坐标排序上。

代码

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

const int maxn = 1e5 + 7;
int n, k;
int l[maxn], r[maxn];
int a[maxn * 6], s[maxn * 6], b[maxn * 2];

vector<int> nums;
unordered_map<int, int> inc, de;

int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        int x[2];
        cin >> x[0] >> x[1];
        // for(int j = 0; j <= 1; j++) {
        //     if(inc.find(x[j]) == inc.end()) {
        //         inc[x[j]] = 1;
        //         nums.emplace_back(x[j]);
        //     }
        // }
        for(int j = max(1, x[0] - 1); j <= x[0] + 1; j++) {
            if(inc.find(j) == inc.end()) {
                inc[j] = 1;
                nums.emplace_back(j);
            }
        }
        for(int j = max(1, x[1] - 1); j <= x[1] + 1; j++) {
            if(inc.find(j) == inc.end()) {
                inc[j] = 1;
                nums.emplace_back(j);
            }
        }
        l[i] = x[0], r[i] = x[1];
    }
    sort(nums.begin(), nums.end());
    for(int i = 0; i < nums.size(); i++) {
        inc[nums[i]] = i + 1;
        de[i + 1] = nums[i];
    }

    for(int i = 1; i <= n; i++) {
        l[i] = inc[l[i]], r[i] = inc[r[i]];
        a[l[i]]++;
        a[r[i] + 1]--;
    }
    int ans = 0;
    int be = 0, ed;
    for(int i = 1; i <= nums.size(); i++) {
        s[i] = s[i - 1] + a[i];
        if(s[i] >= k) {
            if(be) {

            }
            else {
                be = de[i];
            }
            // ans += (de[i + 1] - de[i]);
        }
        else {
            if(be) {
                ans += de[i - 1] - be + 1;
                be = 0;
            }
        }
        // cout << s[i];
    }
    // cout << endl;
    if(be) {
        int N = nums.size();
        ans += de[N] - be + 1;
    }
    cout << ans << endl;


    return 0;
}
// 64 位输出请用 printf("%lld")

复盘：有序差分事件扫描

这题的辅助数组和下标转换比较多。更简单的写法是：直接用 map 存覆盖数发生变化的位置，不再手写离散化。

整数闭区间 [l, r] 可以看成 [l, r+1)：在 l 处加一，在 r+1 处减一。这样相邻两个事件点之间的覆盖数不变，长度也正好对应这一段的整数点个数。

扫描到坐标 x 时，先用变化前的覆盖数判断 [last, x) 是否应该计入答案，再处理 x 处的变化。如果覆盖数已经达到 k，这一段就贡献 x - last。

时间复杂度仍是 $O(n \log n)$ 。省下的是实现和调试的麻烦，不是换了更低复杂度的算法。

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

int main() {
    int n, k;
    cin >> n >> k;

    map<long long, int> diff;

    for (int i = 0; i < n; i++) {
        long long l, r;
        cin >> l >> r;
        diff[l]++;
        diff[r + 1]--;
    }

    long long ans = 0, last = 0;
    int cnt = 0;

    for (auto [x, d] : diff) {
        if (cnt >= k) {
            ans += x - last;
        }
        cnt += d;
        last = x;
    }

    cout << ans << '\n';
}

题目三：RGB 灯带的最少删除次数

题目大意

给两条 RGB 灯带，用只含 R、G、B 的字符串表示。每次可以从任意一条灯带中删除一个灯，剩余灯保持原来的相对顺序。要求最终两条灯带完全相同，而且相邻的灯颜色不同，求最少删除次数。

下面按允许最终保留空串、求最少删除次数来讨论。

我的思路

我直接把状态定义成最少删除次数。f[i][j][k] 表示处理 S 的前 i 个字符和 T 的前 j 个字符，得到相同序列、最后一个保留颜色为 k 时的最少删除次数。

转移按当前两个字符是否相同来分：

颜色相同，可以一起保留，但前一个保留的颜色必须不同；如果当前状态保留的是其他颜色，就把这两个字符一起删掉；
颜色不同，可以删掉其中一个，或者两个都删掉，再从对应的状态转移。

代码里用 x[4][4] 和 xx[4][4] 查另外的颜色。边界状态把其中一条前缀全删掉，代价就是前缀长度；这些边界中的颜色编号是转移占位，不表示空串里真的有这个颜色的灯。

颜色只有三种，时间和空间复杂度都是 $O(nm)$ 。

代码

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

const int maxn = 2e3 +7;
const int oo = 1e9 + 7;
int n, m;
int a[maxn], b[maxn];
int f[maxn][maxn][4];
int x[4][4];
int xx[4][4];

int tr(char c) {
    if(c == 'R') return 1;
    if(c == 'G') return 2;
    if(c == 'B') return 3;
    return -1;
}

int main() {
    x[1][0] = 2, x[1][1] = 3;
    x[2][0] = 1, x[2][1] = 3;
    x[3][0] = 1, x[3][1] = 2;
    xx[1][2] = 3, xx[2][1] = 3;
    xx[1][3] = 2, xx[3][1] = 2;
    xx[3][2] = 1, xx[2][3] = 1;
    string S, T;
    cin >> S;
    cin >> T;
    n = S.size();
    m = T.size();
    for(int i = 1; i <= n; i++) {
        a[i] = tr(S[i - 1]);
    }
    for(int i = 1; i <= m; i++) {
        b[i] = tr(T[i - 1]);
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            for(int k = 1; k <= 3; k++) {
                f[i][j][k] = oo;
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int k = 1; k <= 3; k++) {
            f[i][0][k] = i;
        }
    }
    for(int i = 1; i <= m; i++) {
        for(int k = 1; k <= 3; k++) {
            f[0][i][k] = i;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(a[i] == b[j]) {
                for(int k = 1; k <= 3; k++) {
                    if(k == a[i]) {
                        for(int h = 0; h <= 1; h++) {
                            f[i][j][k] = min(f[i][j][k] , f[i - 1][j - 1][x[k][h]]);
                        }
                    }
                    else {
                        f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k] + 2);
                    }
                }
                // f[i][j][a[i]] == 
            }
            else {
                f[i][j][a[i]] = min(f[i][j][a[i]], f[i][j - 1][a[i]] + 1);
                f[i][j][b[j]] = min(f[i][j][b[j]], f[i - 1][j][b[j]] + 1);
                int tmp = xx[a[i]][b[j]];
                f[i][j][tmp] = min(f[i][j][tmp], f[i - 1][j - 1][tmp] + 2);
                
            }
        }
    }
    int ans = oo;

    // for(int i = 0; i <= n; i++) {
    //     for(int j = 0; j <= m; j++) {
    //         cout << " (";
    //         cout << f[i][j][1] << ", " << f[i][j][2] << ", " << f[i][j][3];
    //         cout << ") ";
    //     }
    //     cout << endl;
    // }

    for(int i = 1; i <= 3; i++) {
        ans = min(ans, f[n][m][i]);
        // cout << f[n][m][i] << endl;
    }
    cout << ans << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

复盘：换成求最多保留多少个灯

也可以反过来想：不枚举删掉哪些灯，而是找最终能保留的最长序列。它必须同时是两条灯带的子序列，而且相邻颜色不同，也就是带这个限制的最长公共子序列。

设 dp[i][j][c] 表示从 S 前 i 个字符和 T 前 j 个字符中，选出的以颜色 c 结尾的最长合法公共子序列长度。转移就分成三种：

不选 S 的当前字符，从 dp[i-1][j][c] 转移；
不选 T 的当前字符，从 dp[i][j-1][c] 转移；
两个字符相同，可以一起选，但前一个颜色必须和当前颜色不同。

如果最长能保留 L 个灯，两条灯带一共就能保留 2L 个，最少删除次数是 n + m - 2L。

时间、空间复杂度仍是 $O(nm)$ ，但不需要 INF 和颜色映射表，转移也少了很多删除分支。

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

int dp[2005][2005][3];

int color(char c) {
    if (c == 'R') return 0;
    if (c == 'G') return 1;
    return 2;
}

int main() {
    string S, T;
    cin >> S >> T;

    int n = S.size(), m = T.size();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {

            for (int c = 0; c < 3; c++) {
                dp[i][j][c] = max(
                    dp[i - 1][j][c],
                    dp[i][j - 1][c]
                );
            }

            if (S[i - 1] == T[j - 1]) {
                int c = color(S[i - 1]);

                for (int k = 0; k < 3; k++) {
                    if (k != c) {
                        dp[i][j][c] = max(
                            dp[i][j][c],
                            dp[i - 1][j - 1][k] + 1
                        );
                    }
                }
            }
        }
    }

    int L = *max_element(dp[n][m], dp[n][m] + 3);
    cout << n + m - 2 * L << '\n';
}

如果要求至少保留一个灯，需要额外处理不存在合法非空公共子序列的情况。

2026-10-18 秋招XX服务端研发笔试复盘

2026-10-18 秋招XX服务端研发笔试复盘

题目一：最多换乘一次的公交最小费用

题目大意

我的思路

代码

复盘：正反两次扫描

题目二：被至少 K 个区间覆盖的整数个数

题目大意

我的思路

代码

复盘：有序差分事件扫描

题目三：RGB 灯带的最少删除次数

题目大意

我的思路

代码

复盘：换成求最多保留多少个灯

Random Posts