拼多多20220903笔试题解【部分】

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


int main() {

    int T;
    cin >> T;
    while(T--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        unordered_map<char, char>mp;
        for(char c = 'a'; c <= 'z'; c++) mp[c] = c;
        int index = 0;
        int max_ = 0;
        for(int i = 0; i < n; i++) {
            if(s[i] - 'a' <= k) {
                index++;
                max_ = max(max_, s[i] - 'a');//记录前面能减的那一部分，比如ekyv中的ek部分，最大是k
            }
            else break;
        }
        k -= max_;
        for(int i = 0; i < index; i++) {
            for(char c = 'a'; c <= s[i]; c++) mp[c] = 'a';
        }
        for(int i = index; i < n && k > 0; i++) {
            s[i] = mp[s[i]];
            int x = s[i] - 'a';
            x = min(x, k);
            k -= x;
            for(int j = 0; j < x; j++) {
                char c = s[i] - j;
                mp[c] = (char)(s[i] - x);
            }
        }
        for(int i = 0; i < n; i++) {
            s[i] = mp[s[i]];
        }
        cout << s << endl;
    }

    return 0;

}

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


int main() {

    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        vector<char>s(n);
        vector<long long>a(n);
        for(int i = 0; i < n; i++) {
            cin >> s[i] >> a[i];
        }
        vector<long long>ans(n);
        for(int i = 0; i < n; i++) {
            if(ans[i] != 0) continue;
            vector<int>path;
            unordered_map<int, bool>vis;//是否走过该点，判断是否成环
            int now = i;
            long long step = 0;
            while(true) {
                // cout << "now: " << now << endl;
                step++;
                path.push_back(now);
                vis[now] = true;
                if(s[now] == 'L') now -= a[now];
                else now += a[now];
                if(now < 0 || now >= n) break;
                if(vis[now]) {
                    step = -1;
                    break;
                }
                if(ans[now] != 0) {
                    if(ans[now] == -1) step = -1;
                    else step += ans[now];//这个点有答案，直接加上
                    break;
                }
            }
            for(int j = 0; j < path.size(); j++) {
                // cout << path[j] << endl;
                if(step == -1) ans[path[j]] = -1;
                else ans[path[j]] = step - j;
            }
        }
        for(int i = 0; i < n; i++) {
            if(i < n - 1) cout << ans[i] << ' ';
            else cout << ans[i] << endl;
        }
    }

    return 0;

}

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


int main() {

    string s, t;
    cin >> s >> t;
    int n = s.size();
    if(s.size() < t.size()) {
        int index = 1;
        while(true) {//调试用的，最后没错，说明后台数据里没有s小于t的情况
            index = index + 23;
        }
        cout << s << endl;
        return 0;
    }
    vector<int>count1(26);
    vector<int>count2(26);
    int count3 = 0;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] != '#') count1[s[i] - 'a']++;
        else count3++;
    }
    for(int i = 0; i < t.size(); i++) {
        count2[t[i] - 'a']++;
    }


    int num = 0;//先看看s可以组成多少个完整的T，并减去这么多个T
    for(int i = 0; i < 26; i++) {
        if(count2[i]) num = min(count1[i] / count2[i], num);
    }
    for(int i = 0; i < 26; i++) {
        count1[i] -= num * count2[i];
    }
    string ans;

    while(count3 > 0) {
        bool flag = true;
        int temp_count3 = count3;
        vector<int>need(26);
        for(int i = 0; i < 26; i++) {
            if(count1[i] >= count2[i]) {//该字符可以由s组成
                count1[i] -= count2[i];
            } else if(count3 >= count2[i] - count1[i]) {//s不够了，由#来凑
                count3 -= count2[i] - count1[i];
                need[i] = count2[i] - count1[i];
                count1[i] = 0;//这里忘记减了，卡了好久。。
            } else {
                flag = false;
            }
        }
        if(!flag) {
            count3 = temp_count3;
            break;
        }
        for(int i = 0; i < 26; i++) {
            while(need[i]--) {
                ans.push_back((char)(i + 'a'));
            }
        }
    }
    while(count3--) {
        ans.push_back('z');
    }
    sort(ans.begin(), ans.end());
    int index = ans.size() - 1;
    for(int i = 0; i < n; i++) {
        if(s[i] == '#') {
            s[i] = ans[index--];
        }
    }
    
    cout << s << endl;


    return 0;

}