原题

source: 2019 Multi-University Training Contest 1

题目大意：

题目中首先给了我们一个字符串s和所需取的子序列长度k。其后有26行，每行两个数，分别代表着a-z这26个小写英文字母每个字母在子序列中所能出现的最小次数和最大次数。问我们的就是满足以上条件且字典序最大的字符串，如果没有则输出-1

解题思路：

开始想用后缀数组做，但后来发现是个贪心。怎么贪呢？我们逐个取字母，对于每个字母我们以a-z的优先级来考虑，如果我们想要一个字母，那么如果我们通过检验发现这个字母后面剩下的串仍然能够满足题目所给的字母区间要求，那么我们就取这个字母，反之就不取。以上的思想换句话说就是我们每次都贪心地从小字母开始挑，如果从已知答案序列最后一个字母的位置开始一直到字符串结尾的所有该字母都无法被挑，那么我们就再考虑下一个字母。

接下来的问题是如何检验一个位置之后是否能够满足题意。我们首先预处理几个数组：1、pre[i] [j]，存放着第i个字母在序列中第j次出现的位置，考虑到空间限制和动态特性这里用vector存放。2、exi[i]，表示每个字母共有多少个。3、st[i] [j]，表示第i个字母从第j个位置开始（包括j）共有几个i。

有了上面的数组时候我们使用now记录上一次答案串最后的位置，从这个位置开始找一个字母第一个出现的位置，再在这个位置上判断这个位置之后各个字母是否仍足够满足题意以及这个位置之后所有字母都算进去的话还能否满足题意，于是便可得到结果

AC代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
char s[maxn];
vector<int> pos[27];
int L[30],R[30];
int st[28][maxn];
int exi[28];
int used[28],no[28];
char ans[maxn];
int k,co,now;
int main()
{
    freopen("02", "r", stdin);
    freopen("sample.out", "w", stdout);
    while (scanf("%s%d",s,&k)!=EOF)
    {
        co=-1;
        int cmp = k;
        int lens = strlen(s);
        //fulset(st, 0);
        for (int i=0;i<=26;i++)
        {
            exi[i]=0;
            used[i]=0;
            no[i]=0;
        }
        now =0;
        for (int i=0;i<=26;i++)
            pos[i].clear();
        for (int i=1;i<=26;i++)
            scanf("%d%d",&L[i],&R[i]);
        for (int i=lens;i>=0;i--)
        {
            exi[s[i]-'a'+1]++;
            for (int j=1;j<=26;j++)
                st[j][i] = exi[j];
        }
        bool OK = true;
        for (int i=1;i<=26;i++)
            if (L[i]>exi[i])
            {
                OK = false;
                break;
            }
        if (!OK)
        {
            printf("-1\n");
            continue;
        }
        for (int i=0;i<=lens-1;i++)
            pos[s[i]-'a'+1].push_back(i); //index related to string starts from 0
       // int kkkk=0;
        while (1)
        {
            
            //cout << ++kkkk << endl;
            
            for (int i=1;i<=26;i++)
            {
                if (used[i] == R[i] || used[i] == exi[i])
                    continue;
                OK = true;
                int tot=0; int you=0;
                used[i]++; k--;
                int temp = now;
                for (int j=no[i];j<exi[i];j++)
                {
                    if (pos[i][j] >= now)
                    {
                        now = pos[i][j];
                        break;
                    }
                    else no[i]++;
                }
                now++;
                for (int j=1;j<=26;j++)
                {
                    if (st[j][now] + used[j] < L[j])
                    {
                        OK = false;
                        break;
                    }
                }
                if (!OK)
                {
                    used[i]--;
                    k++;
                    now = temp;
                    continue;
                }
                for (int j=1;j<=26;j++)
                {
                    you += min(st[j][now], R[j]-used[j]);
                    tot += max(0,L[j]-used[j]);
                }
                if (tot > you || tot >k || you <k)
                    OK = false;

                if (!OK)
                {
                    used[i]--;
                    k++;
                    now = temp;
                    continue;
                }
                else
                {
                    ans[++co] = 'a'+i-1;
                    break;
                }
            }
            if (!k)
                break;
        }
        if (co+1 != cmp)
            printf("-1\n");
        else
        {
            ans[++co] = '\0';
            printf("%s\n",ans);
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}