2019 Multi-University Training Contest 1 - String

贪心

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

#include <bits/stdc++.h>
#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 <typename A, typename B, typename C>
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;
}