题意
链接：https://vjudge.net/problem/HDU-6586
给你一个字符串和k，还有每个字符出现次数的限制，求一个长度为k的字典序最小的满足限制的子序列。
思路
先构造出序列自动机，顺带把num（i,j）（下标为i后面的字符为j的个数）求出来。
题目要求字典序最小，我们就贪心的对每一位每次从a~z枚举，check是否满足。
check（x,y,t）：第x位放字符y且第x-1位是原串的下标t所表示的字符。要满足以下几点：
- 用过的字符y的数量+1<=r[y]
- t后面要有j字符
- 每一个字符需要的位置个数和（即∑l[i]-vis[i]）<=k-x
- 每一个字符当前用过的数量+y字符后面的每一个字符还剩的数量>=每个字符的下限
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char str[N];
char s[N];
int nxt[N][30],l[N],r[N],num[N][30];
int vis[N],k;
char ans[N];
void getnext()
{
memset(nxt, 0, sizeof(nxt));//初始化为0代表i位置之后没有该字符
memset(num,0,sizeof(num));
memset(vis,0,sizeof(vis));
int len = strlen(str + 1);//长度相应的从1下标开始
for(int i = len; i >= 1; i --)
{
for(int j = 0; j < 26; j ++)
{
nxt[i - 1][j] = nxt[i][j];//str i-1位置继承str i位置的离其它字符最近的位置是第几个
num[i-1][j]=num[i][j];
}
nxt[i - 1][str[i] - 'a'] = i;// str i-1位置离str[i]字符的最近位置变为第i个.
num[i-1][str[i] - 'a']++;
}
}
bool check(int x,int y,int t)
{
if(vis[y]+1>r[y]) return 0; //超过上限
vis[y]++;
int need=0;
int now=nxt[t][y];
if(now==0)
{
vis[y]--;
return 0;
}
for(int i=0;i<26;i++)
{
need+=max(0,l[i]-vis[i]);
}
if(need>k-x)
{
vis[y]--;
return 0;
}
for(int i=0;i<26;i++)
{
if(vis[i]+num[now][i]<l[i])
{
vis[y]--;
return 0;
}
}
return 1;
}
int main()
{
while(~scanf(" %s %d", str + 1,&k))
{
getnext(); //获得序列自动机的next数组
for(int i=0;i<26;i++)
scanf("%d%d",&l[i],&r[i]);
int pre=0,gg=0;
for(int i=1;i<=k;i++)
{
int flag=0;
for(int j=0;j<26;j++)
{
if(check(i,j,pre))
{
pre=nxt[pre][j];
ans[i]=j+'a';
flag=1;
break;
}
}
if(!flag)
{
gg=1;
break;
}
}
if(gg)
puts("-1");
else
{
ans[k+1]=' ';
printf("%s
",ans+1);
}
}
return 0;
}