腾讯笔试 2023-09-15

T1

一堆数链，这些数链里面的数字都杂乱无章，你需要整理一下这些数字，把它们从小到大排成一个数链。

解法：放到一个 vector 里面，排序，翻转，头插一波带走。

T2

长度为 n 的数字，每次选择其中一个数字：

1. 如果是奇数，那么奇数乘以 2
2. 如果是偶数，那么偶数乘以 2 再加 1

如果进行 k 次操作，那么操作之后数组元素之和最小是多少？

解法：用最小堆维护这些元素，每次选择最小的去操作即可。

T3

n 个赛车，第 i 个赛车的位置为，速度为 ，匀速向前行驶，满足。问 t 秒后，有多少车的排名上升了？

如果两辆车的位置相同，则认为排名相同。一辆车的排名为在它前面的车辆个数加一。

解法：首先标记每个赛车当前的排名，然后再计算出 t 秒后该车的位置。排序后，用当前排名与之前的排名做比较即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, t;
    cin >> n >> t;
    vector<int> p(n), v(n), p2(n), idx(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        idx[i] = n - i - 1; // 将排名规定为 0~n-1
    }
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    // 三个数组翻转，前面的 p 值更大，排名数字更小
    reverse(p.begin(), p.end());
    reverse(v.begin(), v.end());
    reverse(idx.begin(), idx.end());
    for (int i = 0; i < n; i++) {
        p2[i] = p[i] + v[i] * t;
    }
    // 对 idx 排序，依据为对应下标 p2 的值
    sort(idx.begin(), idx.end(), [&](int x, int y) {
        return p2[x] > p2[y];
    });
    int res = 0;
    int cur = 1;
    for (int i = 0; i < n; i++) {
        if (i > 0 && p2[idx[i]] == p2[idx[i - 1]]) {
            cur = cur;
        } else {
            cur = i + 1;
        }
        if (cur < idx[i] + 1) {
            res++;
        }
    }
    cout << res << endl;
}

T4

对于一个字符串，如果把字符串的第一个字符放到最后，得到的新串就是原来字符串的旋转串。

一个字符串的旋转串的旋转串也是这个字符串的旋转串。即这种关系具有传递性。即 abc 的旋转串有 bca，cab，abc 等。

如果存在一个字符串，既是 x 的旋转串，也是 y 的旋转串，那么我们称 x 和 y 匹配。问 每一组输入中是否有两个字符串匹配。

输入总共有 T 组（T 小于等于 50），每组最多 5000 个长度不超过 50 的字符串。

解法：最小表示法 + 哈希。

字符串的最小表示法就是，在所有通过旋转操作可以转换得到的字符串中，字典序最小的那一个。

通过 O(n) 的时间计算每个字符串的最小表示法，然后使用哈希判断是否有重复的即可。

复杂度 O(Tnm)，其中 m 为字符串的长度。

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


string min_express(string s) {
    int n = s.size();
    int i = 0, j = 1, k = 0;
    while (k < n && i < n && j < n) {
        if (s[(i + k) % n] == s[(j + k) % n]) k++;
        else {
            s[(i + k) % n] > s[(j + k) % n] ? i += k + 1 : j += k + 1;
            if (i == j) i++;
            k = 0;
        }
    }
    i = min(i, j);
    return s.substr(i) + s.substr(0, i);
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        unordered_set<string> st;
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            st.insert(min_express(s));
        }
        if (st.size() == n) cout << "NO" << "\n";
        else cout << "YES" << "\n";
    }
}

T5

有 n 个点在一维数轴上，第 i 个点的坐标为 xi，颜色为 ci。ci 为 0 表示红色，为 1 表示蓝色。

每次你可以选择：

1. 选择一个红点，将它向左或者向右移动，即 x 变成 x-1 或者 x+1。
2. 选择一个蓝点，将它变成红点。

最多可以进行 k 次操作 2，问最少要进行多少次操作 1 可以使得任意两个红点之间不存在蓝点。

数据范围：

解法：蓝色最终只能分布在两边，枚举右边蓝色中坐标最小的那个位置为 i，找到最大的 j 满足：第 j + 1 到 i - 1 个点中最多只能有 k 个蓝色，这些都必须使用操作 2 将它们变成红色。

此时，如果 i != j，并且 x[j] + 1 < x[i]，那么就可以把左右两边的红色挪到中间的空位上。左边的统一挪到 x[j] + 1，右边的挪到 x[i] - 1。

维护双指针，并且维护左边和右边红点的坐标之和和个数，方便计算代价。

注意全局没有蓝点的情况，以及可以把所有的红点挪到最后一个蓝点右边的情况。我们可以在末尾加一个虚拟蓝点，做统一处理。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> x(n + 1), c(n + 1);
    for (int i = 0; i < n; i++) cin >> x[i];
    for (int j = 0; j < n; j++) cin >> c[j];
    // 左右两边红点的坐标之和和个数
    ll Lsum = 0, Lcnt = 0, Rsum = 0, Rcnt = 0;
    for (int i = 0; i < n; i++) {
        if (c[i] == 0) {
            Rsum += x[i];
            Rcnt++;
        }
    }
    // Bcnt 表示双指针区间内蓝点的个数，如果大于 k 就持续往右移动 j
    int Bcnt = 0;
    ll res = 1e18;
    // 添加虚拟蓝点
    x[n] = 2e9;
    c[n] = 1;
    n++;
    for (int i = 0, j = -1; i < n; i++) {
        if (c[i] == 0) {
            Rsum -= x[i];
            Rcnt--;
        } else {
            while (j < i && Bcnt > k) {
                if (c[j + 1] == 0) {
                    Lsum += x[j + 1];
                    Lcnt++;
                } else {
                    Bcnt--;
                }
                j++;
            }
            if (i != j && x[i] > x[j] + 1) {
                res = min(res, Lcnt * (x[j] + 1) - Lsum + Rsum - Rcnt * (x[i] - 1));
            }
            Bcnt++;
        }
    }
    
    cout << res << endl;
    return 0;
}

总体难度不简单，易错点和坑点很多，很值得复盘的一套题目。赛中大概花了 50min AK，因为没有罚时所以写的时候很随意，胡乱 WA 了很多发。