百度0313笔试总结

写在前面：

百度还是很温和的，第一道纯送分，第二道考了一个构造的脑筋急转弯，第三道难度也没有想象中的大，但我没做出来，算法之路任重而道远。

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

题目 1

题目描述

若干次询问，每次询问给出一个字符串，需要输出该字符串是否能够重新排列成 "Baidu"，要求大小写一致。

解题方法

水题。

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin>>t;
    string target = "Baidu";
    sort(target.begin(), target.end());
    while (t--) {
        string q;
        cin>>q;
        sort(q.begin(), q.end());
        if (q == target) {
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
    }
}

题目 2

题目描述

给定一个整数 x，请你构造一个仅由 'r' , 'e' , 'd' 三种字符组成的字符串，其中回文子串的数量恰好为 x

解题方法

数学题。对于一个长度为 k 的字符串，如果其仅有一种字符组成，则该字符串的回文子串数量为 \(n(n + 1)/2\)，贪心构造即可。

#include<bits/stdc++.h>

using namespace std;

int main() {
    long long int x;
    long long int i = 0;
    cin>>x;
    while (x != 0) {
        for (i = 1; i*(i+1)/2 <= x; i++) {
            cout<<"r";
        }
        i--;
        x -= i*(i+1)/2;
        for (i = 1; i*(i+1)/2 <= x; i++) {
            cout<<"e";
        }
        i--;
        x -= i*(i+1)/2;
        for (i = 1; i*(i+1)/2 <= x; i++) {
            cout<<"d";
        }
        i--;
        x -= i*(i+1)/2;
    }
    cout<<endl;
}

题目 3

题目描述

小红拿到了一棵树，每个节点被染成了红色或者蓝色。

小红定义每条边的权值为：删除这条边时，形成的两个子树的同色连通块数量之差的绝对值。

小红想知道，所有边的权值之和是多少？

输入描述

第一行输入一个正整数 n ,代表节点的数量。

第二哈输入一个长度为 n 且仅由 R 和 B 两种字符组成的字符串。

第 i 个字符为 R 代表 i 号节点被染成红色，为 B 则被染成蓝色。

接下来的 n−1 行，每行输入两个正整数 u 和 v ，代表节点 u 和节点 v 有一条边相连。

\(1 \le n \le 200000\)

输出描述

一个正整数，代表所有节点的权值之和。

样例

输入

4
BBRR
1 2
3 2
4 1

输出

2

解题方法

这道题目在笔试中没有做出来，当时看到题目就知道是树形 DP，前段时间做过一道类似的题目：2581. 统计可能的树根数目，用到了换根DP的思想。但是因为对于树形 DP 的练习过少，错误地高估了这道题的难度（换根 DP 似乎更不容易理解），短时间内也没有想到正解。

赛后补了一下这道题和树形 DP，使用 \(dp[i]\) 表示以第 \(i\) 个节点为根的连通块个数，初始时所有的节点连通块个数为 1，使用 dfs 跑一遍树可以计算出所有 \(dp[i]\) 的值。

随后再一次 dfs 尝试拆边，对于每一条边 \((l, r)\) ：

• 如果其左右节点颜色不同，则拆边不会影响连通块的个数，贡献为；\(abs((dp[0] - dp[r]) - dp[r])\)；
• 若左右节点颜色相同，则拆边会导致连通块个数加 1 ，贡献为：\(abs((dp[0] - dp[r] + 1) - dp[r])\)。

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    vector<vector<int>> g(n);
    vector<int> dp(n, 1);
    for (int i = 0; i < n - 1; i++) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        g[l].emplace_back(r);
        g[r].emplace_back(l);
    }
    long long int ans = 0;
    function<void(int, int)> dfs = [&] (int cur, int p) {
        for (auto &nx : g[cur]) {
            if (nx == p) {
                continue;
            }
            dfs(nx, cur);
            if (s[cur] != s[nx]) {
                dp[cur] += dp[nx];
            }
            else {
                dp[cur] += dp[nx] - 1;
            }
        }
    };
    function<void(int, int)> solve = [&] (int cur, int p) {
        for (auto &nx : g[cur]) {
            if (nx == p) {
                continue;
            }
            solve(nx, cur);
            if (s[cur] == s[nx]) {
                ans += ((dp[0] - dp[nx] + 1) - dp[nx]);
            }
            else {
                ans += ((dp[0] - dp[nx]) - dp[nx]);
            }
        }
    };
    dfs(0, -1);
    solve(0, -1);
    cout << ans << endl;
}