携程后端笔试 2023-03-29

20min AK。

T1 签到，T2 需要动一动脑筋构造，不算太难，T3 可能需要想到枚举一个变量去算另外一个变量，T4 是树上DP的模板题，难度不大但没做过可能比较吃亏。

T1

游游拿到了一串数宇，她想知道这串数字一共有多少个圆圈？

提示：数宇0、6、9这三种数字各有一个圆圈，数字8有两个圆圈。

输入是一个字符串，仅由数字字符组成。长度不超过100000。

例如：1234567890 答案为 5

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

int main(){
    string s;
    cin >> s;
    int res = 0;
    for (auto c : s) {
        if (c == '0' || c == '6' || c == '9') {
            res++;
        } else if (c == '8') {
            res += 2;
        }
    }
    cout << res << "\n";
    return 0;
}

T2

游游定义一个排列中，满足以下条件的为"好元素"：对于第公个元素a而言，a为前 i 个元素的最大值。例如，[3,1,5,2,4]中，第一个和第三个元素是好元素。游游希望你构造一个长度为n的排列，其中有k个好元素，且任意两个好元素都不相邻。你能帮帮她吗？

排列的定义：由1到九所有正整数组成的长度为n的数组，每个正整数出现恰好一次。

输入：

两个正整数 n，k，用空格隔开。

输出：

一行 n 个整数

位置 i 放 i + 1, 位置 i + 1 放 i，这样会消耗一个好元素个数。

对于最后一个好元素直接放 n 即可。后面元素可以随便放。

例如 5 个元素的排列，有 2 个好元素，按照以上规则构造：2 1 5 3 4

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

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ) {
        if (k > 1) {
            a[i] = i + 2;
            a[i + 1] = i + 1;
            i += 2;
            k--;
        } else if (k == 1) {
            a[i] = n;
            i++;
            k--;
        } else {
            a[i] = i;
            i++;
        }
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << " \n"[i == n - 1];
    }
    return 0;
}

T3

游游拿到了一个正整数 n，她希望找到一对正整数 x, y 满足 |x!*y - y - n| 最小，且 x,y 都不等于2，感叹号表示阶乘。你能帮帮她吗？

1 <= n <= 1e9

x! 很容易就超过 1e9，如果超过太多，答案不会更优，因此直接枚举 x，然后计算 y。

枚举 x 的范围从 2 到 20 即可（更小或许也可以），计算 y 时有两个可能值。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// |x! * y - y - n| 最小
// |a * y - y - n| 最小的 y
// (a - 1) * y >= n
// (a - 1) * y < n
ll n;
ll get(ll x, ll y) {
    if (y == 2) {
        return n + 1;
    }
    return abs(x * y - y - n);
}
int main(){
    cin >> n;
    ll acc = 1;
    ll res = n;
    int x = 1, y = 1;
    for (int i = 2; i <= 20; i++) {
        acc *= i;
        if (i == 2) continue;
        int j = n / (acc - 1);
        
        ll cur = get(acc, j);
        if (cur < res) {
            res = cur;
            x = i;
            y = j;
        }
        j++;
        cur = get(acc, j);
        if (cur < res) {
            res = cur;
            x = i;
            y = j;
        }
    }
    cout << x << ' ' << y << endl;
}

T4

游游拿到了一棵树，树的每条边有边权。游游准备选择一些边染成红色，她希望不存在两条染红的边共用同一个点，且最终染红边的权值之和尽可能大。你能帮帮她吗？

注：所谓树，即不包含重边、自环和回路的无向连通图。

节点个数 n <= 1e5, 边权 w <= 1e9

裸的树上DP，d[i][k] 表示以 i 为根的子树，是否染边(k=1) 时的最大权值。

是否染边是说，i 和 i 的子节点间的边是否被染色。

对于 x 节点的子节点 y，max(d[y][0], d[y][1]) 可以直接贡献给 d[x][0]。

而 d[x][1] 的更新比较复杂，它可以选择一个 y，去用 d[y][0] + w，而其他的 y 用 max(d[y][0], d[y][1])。

所以，枚举每个 y，用 d[x][0] - max(d[y][0], d[y][1]) + d[y][0] + w 来更新 d[x][1] 即可。

时间复杂度为 O(n)。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    int n;
    cin >> n;
    vector<vector<pair<int, int>>> g(n + 1);
    vector<vector<ll>> d(n + 1, vector<ll>(2, 0));
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    function<void(int, int)> dfs = [&](int x, int f) {
        for (auto &[y, z] : g[x]) {
            if (y == f) {
                continue;
            }
            dfs(y, x);
            d[x][0] += max(d[y][0], d[y][1]);
        }
        for (auto &[y, z] : g[x]) {
            if (y == f) {
                continue;
            }
            d[x][1] = max(d[x][1], d[x][0] - max(d[y][0], d[y][1]) + d[y][0] + z);
        }
    };
    dfs(1, 0);
    cout << max(d[1][0], d[1][1]) << endl;
}