百度后端笔试 2023-04-10

T1 小红的子数组拆分

题意

小红拿到了一个长度为n的数组，她希望把该数组拆分成k个非空子序列(每个元素必须出现在某个子序列中，且恰好出现一次），使得这k个子序列的平均数之和尽可能小。你能帮帮她吗？

注，子序列可以不连续。例如数组为[3,2,1,3]，k=2时，子序列可以拆分为[3,1]和[2,31]。

1 <= k, n <= 1e5, -10^9 <= ai <= 10^9

思路

对于一个数字 x，假设分配到了长度为 y 的数组中，那么它对最终答案的贡献是 x / y。

对 x 分正负讨论：

• 正数，使它尽可能的分配到更长的子数组中。
• 负数，使它尽可能的分配到长度为 1 的子数组中。

也就是说数字越小，分配到的子数组长度应该尽可能的小，于是有了以下做法：

对数组排序，然后前 k - 1 个数字单独分组，最后 n - k + 1 个 数字分成一组。

时间复杂度 O(nlogn)。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    ll res = 0;
    for (int i = 0; i < k - 1; i++) {
        res += a[i];
    }
    ll sum = 0;
    for (int i = k - 1; i < n; i++) {
        sum += a[i];
    }
    double ans = res + 1.0 * sum / (n - k + 1);
    printf("%.10f\n", ans);
}

T2 red 回文串

题意

给定一个整数x，请你构造一个仅由'r'、‘e'、’d’三种字符组成的字符串，其中回文子串的数量恰好为x。字符串的长度不得超过10^5。

1 <= x <= 10^9

思路

这个题目老朋友了，由相同字符构成的长度为 n 的字符串共有 (1 + n) * n / 2 个回文串，我们先找到最大的 n 使得 (1 + n) * n / 2 <= x，用 n 个 r 去填充，然后剩下按照 "red" 去补齐即可。

时间复杂度 O(sqrt(n))。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ll x;
    cin >> x;
    ll n = 1, sum = 0;
    string s = "";
    while (sum + n <= x) {
        sum += n;
        s += "r";
        n++;
    }
    int c = 0;
    for (int i = sum + 1; i <= x; i++) {
        if (c == 0) {
            s += 'e';
        } else if (c == 1) {
            s += 'd';
        } else {
            s += 'r';
        }
        c = (c + 1) % 3;
    }
    cout << s << endl;
    return 0;
}

T3 小红的子树操作

题意

小红拿到了一棵有根树，i 号节点的权值为 ai 。已知1号节点为根节点。

小红有q次操作，每次操作会选择一个节点x，使得x为根的子树上，所有节点的权值乘以y。

小红想知道，在q次操作结束以后，对于节点 i，以节点 i 为根的子树的所有点权值乘积末尾有多少个0？

1 <= n, q <= 10^5

1 <= ai, y <= 10^9

思路

这个题目也是老朋友了。

首先，乘积末尾 0 的个数，只跟乘数分解质因数后 2 和 5 的指数有关，这两个指数的最小值即为末尾 0 的个数。

然后，对以 x 为根的子树操作，只需要先给 x 打上标记，q 次操作全部打上标记后，dfs 的过程中将标记传递到子树上的每个结点，累计求和。

最后回溯的时候，再求一次和，表示子树所有数的乘积。

时间复杂度 O(n+qlogy)。

// 小红的子树操作
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    int n, q;
    cin >> n;
    vector<ll> a(n), c2(n), c5(n);
    vector<vector<int>> g(n);

    // 计算 x 分解质因数后 base 的指数
    auto get = [&](ll x, int base) {
        ll cnt = 0;
        while (x % base == 0) {
            cnt++;
            x /= base;
        }
        return cnt;
    };

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; i++) {
        int x, y; cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        c2[x - 1] += get(y, 2);
        c5[x - 1] += get(y, 5);
    }
    
    function<void(int, int)> dfs = [&](int x, int f) {
        // 递归过程中，给 x 的子节点 y 累加标记
        for (auto &y : g[x]) {
            if (y == f) continue;
            c2[y] += c2[x];
            c5[y] += c5[x];
            dfs(y, x);
        }

        // 回溯过程中，求以 x 为根的子树中所有节点的标记之和。
        for (auto &y : g[x]) {
            if (y == f) continue;
            c2[x] += c2[y];
            c5[x] += c5[y];
        }
        
        // 这里对于 x 原本的权值要单独算，这一部分不能递归下去
        c2[x] += get(a[x], 2);
        c5[x] += get(a[x], 5);
    };

    dfs(0, -1);
    for (int i = 0; i < n; i++) {
        cout << min(c2[i], c5[i]) << " \n"[i == n - 1];
    }
    return 0;
}