3.13百度后端笔试编程题

第一题

给定一个字符串，问是否可以排列为：Baidu

#include <iostream>
#include <map>
#include <string>

using namespace std;

bool solve() {
    string s; cin >> s;
    if(s.size() != 5) return false;
    
    map<char, int> mp;
    string Baidu = "Baidu";
    for(char c : s) mp[c] ++;
    for(char c : Baidu) if(mp[c] != 1) return false;
    
    return true;
}

int main() {
    int tt; cin >> tt;
    while(tt--) cout << (solve() ? "Yes" : "No") << '\n';
    
    return 0;
}

第二题

给定数字p，构造s使得s的子字符串为回文串的数目为p。(p<1e9,s.size() < 1e5);

#include <iostream>
#include <string>

using namespace std;

int main() {
    int x; cin >> x;
    
    string s, red = "red";
    
    int c = 0;
    while(x) {
        int sum = 0, i = 1;
        while(sum + i <= x) { // 构造连续相同的c
            sum += i, i++;
            s += red[c];
        }
        
        x -= sum, c = (c + 1) % 3;
    }
    cout << s;
    
    return 0;
}

第三题

给定一棵树，每个节点有蓝色和红色两种颜色，问：删除其中一条边，剩下两个联通块的色块的个数的差值，求所有差值的和；（n<2e5)

#include <iostream>
#include <vector>
#include <string>


using namespace std;
using ll = long long;
const int N = 200010;

int n;
string s;
vector<int> edge[N];
ll sum, ans, dp[N];

ll init(int x, int fa) {
    dp[x] = 1;
    for(int y : edge[x]) {
        if(y == fa) continue;
        
        dp[x] += init(y, x);
        // 如果子节点与父节点颜色相同，合并为一个块
        if(s[x] == s[y]) dp[x] --; 
    }
    return dp[x];
}

void dfs(int x, int fa) {
    for(int y : edge[x]) {
        if(y == fa) continue;
        dfs(y, x);
        ll son = dp[y];
        // 父亲节点所拥有的颜色块的数目为：总-儿子节点颜色块的数目+分割产生的一个颜色块
        ll father = sum - son + (s[x] == s[y]);
        
        ans += abs(father - son);
    }
}

int main() {
    cin >> n >> s;
    for(int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        x--, y--;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    
    sum = init(0, -1);
    dfs(0, -1);
    cout << ans;
    
    return 0;
}

代码为回忆版本，非现场通过版本