携程0329笔试总结

写在前面：

携程的题比较简单，但还是因为我知识点不够没有能在场上做出最后一题，春招好多厂都考树形 DP

本篇文章仅分享本人解答代码做学习交流，若涉密或侵权可联系我删除。

题目 1

题目描述

一个只有数字的字符串，统计其中 '0' 的个数，'0', '6', '9' 包含一个 '0' ， '8' 包含两个。

解题方法

水题。

#include<bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;
    int ans = 0;
    for (auto &ch : s) {
        if (ch == '0' || ch == '6' || ch == '9') {
            ans++;
        }
        else if (ch == '8') {
            ans += 2;
        }
    }
    cout << ans << endl;
}

题目 2

题目描述

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

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

输入：

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

输出：

一行 n 个整数

解题方法

可以将前 k 大的数字从头开始间隔摆放，剩下的数字按增序填充即可。

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> ans(n, -1);
    int cur = n - k + 1, tmp = cur - 1;
    int i = 0;
    while (k--) {
        ans[i] = cur++;
        i += 2;
    }
    for (int i = n - 1; i >= 0; i--) {
        if (ans[i] == -1) {
            ans[i] = tmp--;
        }
    }
    cout << ans[0];
    for (int i = 1; i < n; i++) {
        cout << " " << ans[i];
    }
    cout << endl;
}

题目 3

题目描述

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

1 <= n <= 1e9

解题方法

这个题其实比较好想，因为 20! 就已经超过 1e9 只需要枚举 x 然后计算 y ，笔试结束才发现自己有个笔误，只能通过暴力骗了 88.89%，实在是遗憾，以下是正解。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long int> fac(20);
    fac[0] = 1;
    long long int result_x = -1, result_y = -1;
    long long int min_val = LONG_MAX;
    for (int x = 1; x <= 20; x++) {
        fac[x] = fac[x - 1]*x;
    }
    for (int x = 1; x <= 20; x++) {
        if (x == 2) {
            continue;
        }
        long long int y = n/(fac[x] - 1);
        long long int y1 = y + 1;
        long long int y2 = y - 1;
        long long int val = abs(1LL*(fac[x] - 1)*y - n);
        if (y != 0 && y != 2 && val < min_val) {
            min_val = val;
            result_x = x;
            result_y = y;
        }
        val = abs(1LL*(fac[x] - 1)*y1 - n);
        if (y1 != 0 && y1 != 2 && val < min_val) {
            min_val = val;
            result_x = x;
            result_y = y1;
        }
        val = abs(1LL*(fac[x] - 1)*y2 - n);
        if (y2 != 0 && y2 != 2 && val < min_val) {
            min_val = val;
            result_x = x;
            result_y = y2;
        }
    }
    cout << result_x << " " << result_y << endl;
}

题目 4

题目描述

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

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

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

解题方法

吃了百度第三题的亏，赛后也没有认真去学树形 DP ，拿到这道题的时候呆住了，看着像裸的树形 DP 但就是不知道怎么设置状态，我还是太菜了！赛后看到牛客大佬的题解，瞬间就明白怎么做了，于是浅浅补一下题。

我们可以定义状态 \(dp[i][0]\) 表示节点 \(i\) 的出度边不染色的最大收益， \(dp[i][1]\) 表示节点 \(i\) 的出度边染色：

• 当节点 \(i\) 的出度边不染色时，也就意味着其所有子节点 \(nx\) 的出度边可染可不染，此时收益为 \(\sum_{nx}^{(i, nx) \in E}max(dp[nx][0], dp[nx][1])\)；
• 当节点 \(i\) 的出度边染色时，需要从其所有出度边中选择且只选择一条边，此时收益为 \(max(dp[i][0] - max(dp[nx][0], dp[nx][1]) + dp[nx][0] + val), (i, nx) \in E\)。

代码如下（未测）：

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int l, r, val;
        cin >> l >> r >> val;
        l--, r--;
        g[l].emplace_back(make_pair(r, val));
        g[r].emplace_back(make_pair(l, val));
    }
    vector<vector<int>> dp(n, vector<int>(2, 0));
    function<void(int, int)> dfs = [&](int cur, int p) {
        for (auto &[nx, val] : g[cur]) {
            if (nx == p) {
                continue;
            }
            dfs(nx, cur);
            dp[cur][0] += max(dp[nx][0], dp[nx][1]);
        }
        for (auto &[nx, val] : g[cur]) {
            if (nx == p) {
                continue;
            }
            dp[cur][1] = max(dp[cur][1], dp[cur][0] - max(dp[nx][0], dp[nx][1]) + dp[nx][0] + val);
        }
    };
    dfs(0, -1);
    cout << max(dp[0][0], dp[0][1]);
}