题意

给你一个字符串和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]='\0';

            printf("%s\n",ans+1);

        }

    }

    return 0;

}

巴特西

2019 Multi-University Training Contest 1 String（序列自动机+贪心）

题意

思路

代码

最新文章

热门文章