百度暑期笔试编程题 【2023-3-13】

A题

一个字符串能否重新排列成 "Baidu"

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    std::string s;
    std::cin >> s;
    if (s.size() != 5) {
        std::cout << "No\n";
        return;
    }
    
    std::string t = "Baidu";
    std::set<char> S;
    for (auto ch : s) {
        S.insert(ch);
    }
    for (auto ch : t) {
        if (!S.count(ch)) {
            std::cout << "No\n";
            return;
        }
    }
    std::cout << "Yes\n";
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(nullptr);
    
    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }
    
    return 0;
}

B题

r,e,d三个字符，能否构成含有 cnt 个回文串的字符串 s

• $1\le cnt\le 10^{9}1\backslash le\; cnt\backslash le\; 10^9$
• $1\le len(s)\le 10^{5}1\backslash le\; len(s)\backslash le\; 10^5$

二分找最大就行

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(nullptr);
    
    int x;
    std::cin >> x;
    
    int cnt = 0, cur = 0;
    std::string s = "red";
    std::string ans;
    while (cnt < x) {
        int lo = 1, hi = 1e5;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (1ll * mid * (mid + 1) / 2 > x - cnt) {
                hi = mid - 1;
            } else {
                lo = mid;
            }
        }
        cnt += 1ll * hi * (hi + 1) / 2;
        for (int i = 0; i < hi; i++) {
            ans += s[cur];
        }
        cur = (cur + 1) % 3;
    }
    
    std::cout << ans << "\n";
    
    return 0;
}

C题

树形dp

$dp[u]dp[u]$ 是为以 u 为根节点，该树包含同色连通块的数量。

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(nullptr);
    
    int n;
    std::string s;
    std::cin >> n >> s;
    std::vector adj(n, std::vector<int>());
    std::vector<int> dp(n, 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    i64 ans = 0;
    auto dfs = [&](auto self, int x, int fa) -> void {
        for (auto y : adj[x]) {
            if (y == fa) continue;
            self(self, y, x);
            if (s[x] != s[y]) {
                dp[x] += dp[y];
            } else {
                dp[x] += dp[y] - 1;
            }
        }
    };
    
    auto calc = [&](auto self, int x, int fa) -> void {
        for (auto y : adj[x]) {
            if (y == fa) continue;
            self(self, y, x);
            if (s[x] == s[y]) {
                ans += std::abs(dp[0] - dp[y] + 1 - dp[y]);
            } else {
                ans += std::abs(dp[0] - dp[y] - dp[y]);
            }
        }
    };
    
    dfs(dfs, 0, -1);
    calc(calc, 0, -1);
    std::cout << ans << "\n";
    
    return 0;
}