贪心

先记录每一个位置后面字母的第一个位置，以及出现次数，然后一位一位的构造字母，如果选了该字母后，后续字母可以满足约束条件，那么就合法。

#include 
    
     #define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)#define FAST_IO ios::sync_with_stdio(false)using namespace std;typedef long long LL;inline int lowbit(int x){ return x & (-x); }inline int read(){    int ret = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        ret = (ret << 3) + (ret << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -ret : ret;}inline int lcm(int a, int b){ return a / __gcd(a, b) * b; }template 
     
      inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}const int N = 100005;int k, nexts[N][26], freq[N][26], l[N], r[N], use[N];string s, ans;bool calc(int pos, int len){    int L = 0, R = 0;    for(int i = 0; i < 26; i ++){        if(freq[pos][i] + use[i] < l[i]) return false;        R += use[i] + min(r[i] - use[i], freq[pos][i]); // 每个字母在不超过约束条件的情况下最大能拿的数量        L += max(0, l[i] - use[i]); // 满足条件至少还需要拿的字母数    }    if(R < k) return false;    if(L > k - len) return false;    return true;}int main(){    FAST_IO;    while(cin >> s >> k){        for(int i = 0; i < 26; i ++) cin >> l[i] >> r[i];        full(nexts[s.size() - 1], -1), full(freq[s.size() - 1], 0), full(use, 0);        ans.clear();        for(int i = s.size() - 2; i >= 0; i --){            for(int j = 0; j < 26; j ++){                nexts[i][j] = nexts[i + 1][j];                freq[i][j] = freq[i + 1][j];            }            nexts[i][s[i + 1] - 'a'] = i + 1;            freq[i][s[i + 1] - 'a'] ++;        }        int cur = 0, len = 0;        bool no = false;        while(cur < s.size() && len < k){            bool good = false;            for(int i = 0; i < 26; i ++){                if(nexts[cur][i] != -1 && use[i] < r[i]){                    use[i] ++;                    if(calc(nexts[cur][i], len + 1)){                        len ++, cur = nexts[cur][i];                        ans.push_back(i + 'a');                        good = true;                        break;                    }                    use[i] --;                }            }            if(!good){                no = true;                break;            }        }        if(no) cout << "-1" << endl;        else cout << ans << endl;    }    return 0;}