20220830携程笔试题解

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


int main() {

    int q;
    cin >> q;
    while(q--) {
        int x;
        cin >> x;
        string s = to_string(x);
        int index = 0;
        int min_ = '9';
        for(int i = 0; i < s.size(); i++) {
            if((s[i] - '0') % 2 == 0) {
                if(s[i] < min_) {
                    min_ = s[i];
                    index = i;
                }
            }
        }
        if((s[index] - '0') % 2 == 0) {
            swap(s[index], s[s.size() - 1]);
            int i = 0;
            while(i < s.size() && s[i] == '0') {
                i++;
            }
            if(i == s.size()) cout << -1 << endl;
            else {
                s = s.substr(i);
                cout << s << endl;
            }
        } else {
            cout << -1 << endl;
        }
    }

    return 0;
}

第二题

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


int main() {

    int q;
    cin >> q;
    while(q--) {
        int a, b, c;
        cin >> a >> b >> c;
        int ans = 0;
        ans = min({a,b,c});
        a -= ans;
        b -= ans;
        c -= ans;
        ans *= 2;
        if(b >= 2) ans += b - 1;
        cout << ans << endl;
    }

    return 0;
}

第三题

首先建图，然后先统计一下所有节点的颜色

然后dfs遍历每个节点，统计以start为根节点，除去except_节点之外的颜色，这样就相当于删除一条边了，然后是记忆化存储遍历结果就好了

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

struct Node {
    int r, g, b;
    Node() {
        r = g = b = 0;
    }
};

unordered_map<long long, Node>mp;
string s;
vector<vector<int>>G;
Node a;

Node dfs(int start, int except_) {
    long long mps = (long long)start * 100000 + except_;
    if(mp.count(mps)) return mp[mps];
    Node ans;
    if(s[start] == 'r') ans.r++;
    else if(s[start] == 'g')ans.g++;
    else ans.b++;
    for(auto &i : G[start]) {
        if(i == except_) continue;
        auto res = dfs(i, start);
        ans.r += res.r;
        ans.g += res.g;
        ans.b += res.b;
    }
    mp[mps] = ans;
    auto temp = ans;
    temp.r = a.r - ans.r;
    temp.g = a.g - ans.g;
    temp.b = a.b - ans.b;
    mp[(long long)except_ * 100000 + start] = temp;
    return ans;
}

int main() {

    int n;
    cin >> n;
    cin >> s;
    G = vector<vector<int>>(n);
    for(int i = 0, u, v; i < n - 1; i++) {
        cin >> u >> v;
        G[u - 1].push_back(v - 1);
        G[v - 1].push_back(u - 1);
    }
    for(int i = 0; i < n; i++) {
        if(s[i] == 'r') a.r++;
        else if(s[i] == 'g') a.g++;
        else a.b++;
    }
    int ans = 0;
    unordered_map<long long, bool>vis;
    for(int i = 0; i < n; i++) {
        for(auto &j : G[i]) {
            if(vis.count((long long)i * 100000 + j)) continue;
            auto res = dfs(j, i);
            if(res.r > 0 && res.g > 0 && res.b > 0) {
                res.r = a.r - res.r;
                res.g = a.g - res.g;
                res.b = a.b - res.b;
                if(res.r > 0 && res.g > 0 && res.b > 0) ans++;
            }
            vis[(long long)i * 100000 + j] = vis[(long long)j * 100000 + i] = true;
        }
    }
    cout << ans << endl;



    return 0;
}

第四题

优先队列记录当前最大差值，map记录每个差值的出现次数

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

int main() {

    int n;
    cin >> n;
    vector<long long>a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] += 1e9;
    }
    long long ans = LLONG_MAX;
    priority_queue<long long, vector<long long>, less<long long>>q;
    unordered_map<long long, int>mp;
    for(int i = 1; i < n; i++) {
        if(!mp.count(abs(a[i] - a[i - 1]))) {
            q.push(abs(a[i] - a[i - 1]));
        }
        mp[abs(a[i] - a[i - 1])]++;
    }
    for(int i = 1; i < n - 1; i++) {
        int sum = a[i - 1] + a[i + 1];
        int old_diff1 = abs(a[i] - a[i - 1]);
        int old_diff2 = abs(a[i + 1] - a[i]);
        int avg = (a[i - 1] + a[i + 1]) / 2;
        if(avg == a[i]) continue;
        int new_diff1 = abs(avg - a[i - 1]);
        int new_diff2 = abs(avg - a[i + 1]);
        mp[old_diff1]--;
        mp[old_diff2]--;
        mp[new_diff1]++;
        mp[new_diff2]++;
        q.push(new_diff1);
        q.push(new_diff2);
        while(mp[q.top()] <= 0) q.pop();
        ans = min(ans, q.top());
        q.push(old_diff1);
        q.push(old_diff2);
        mp[old_diff1]++;
        mp[old_diff2]++;
        mp[new_diff1]--;
        mp[new_diff2]--;
    }
    
    //te shu kao lv di yi ge he zui hou yi ge
    mp[abs(a[1] - a[0])]--;
    mp[0]++;
    q.push(0);
    while(mp[q.top()] <= 0) q.pop();
    ans = min(ans, q.top());
    q.push(abs(a[1] - a[0]));
    mp[abs(a[1] - a[0])]++;
    mp[0]--;
    while(mp[q.top()] <= 0) q.pop();
    // while(!q.empty()) {
    //     cout << q.top() << " " << mp[q.top()] << endl;
    //     q.pop();
    // }
    // cout << ans << endl;
    // return 0;

    mp[abs(a[n - 1] - a[n - 2])]--;
    mp[0]++;
    q.push(0);
    while(mp[q.top()] <= 0) q.pop();
    ans = min(ans, q.top());
    mp[abs(a[n - 1] - a[n - 1])]++;
    mp[0]--;

    // multiset<long long>se;
    // for(int i = 1; i < n; i++) {
    //     se.insert(abs(a[i] - a[i - 1]));
    // }
    // for(int i = 1; i < n - 1; i++) {
    //     int sum = a[i - 1] + a[i + 1];
    //     int old_diff1 = abs(a[i] - a[i - 1]);
    //     int old_diff2 = abs(a[i + 1] - a[i]);
    //     int avg = (a[i - 1] + a[i + 1]) / 2;
    //     if(avg == a[i]) continue;
    //     int new_diff1 = abs(avg - a[i - 1]);
    //     int new_diff2 = abs(avg - a[i + 1]);
    //     se.erase(se.find(old_diff1));
    //     se.erase(se.find(old_diff2));
    //     se.insert(new_diff1);
    //     se.insert(new_diff2);
    //     ans = min(ans, (*max_element(se.begin(), se.end())));
    //     se.erase(se.find(new_diff1));
    //     se.erase(se.find(new_diff2));
    //     se.insert(old_diff1);
    //     se.insert(old_diff2);
    // }
    // //te shu kao lv di yi ge he zui hou yi ge
    // se.erase(se.find(abs(a[1] - a[0])));
    // se.insert(0);
    // ans = min(ans, (*max_element(se.begin(), se.end())));
    // se.erase(se.find(0));
    // se.insert(abs(a[1] - a[0]));

    // se.erase(se.find(abs(a[n - 1] - a[n - 2])));
    // se.insert(0);
    // ans = min(ans, (*max_element(se.begin(), se.end())));
    // se.erase(se.find(0));
    // se.insert(abs(a[n - 1] - a[n - 2]));

    cout << ans << endl;


    return 0;
}