2019HDU多校第一场 1009 String-蒲公英云

2019HDU多校第一场 1009 String

傷城~ 2021-11-27 00:44 416阅读 0赞

Problem Description

Tom has a string containing only lowercase letters. He wants to choose a subsequence of the string whose length is k and lexicographical order is the smallest. It’s simple and he solved it with ease.
But Jerry, who likes to play with Tom, tells him that if he is able to find a lexicographically smallest subsequence satisfying following 26 constraints, he will not cause Tom trouble any more.
The constraints are: the number of occurrences of the ith letter from a to z (indexed from 1 to 26) must in [Li,Ri].
Tom gets dizzy, so he asks you for help.

Input

The input contains multiple test cases. Process until the end of file.
Each test case starts with a single line containing a string S(|S|≤105)and an integer k(1≤k≤|S|).
Then 26 lines follow, each line two numbers Li,Ri(0≤Li≤Ri≤|S|).
It’s guaranteed that S consists of only lowercase letters, and ∑|S|≤3×105.

Output

Output the answer string.
If it doesn’t exist, output −1.

Sample Input

aaabbb 3 0 3 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

题意：给一个母串，给出每个字符出现次数的上下限，求长度为K的、满足次数要求的子串

思路：一位一位的求答案串，对每一位添加上去之后，判断剩下的串能不能满足条件

#include<vector>
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int M=1e5+50;
int k,n,cnt[M][50],last,ans,l[M],used[M],r[M];
char s[M],res[M];
vector<int> g[26];
int main(){
    while(scanf("%s%d",s,&k)!=EOF){
        memset(used,0,sizeof(used));
        for(int i=0;i<26;i++){
            scanf("%d%d",l+i,r+i);
            g[i].clear();
        }
        n=strlen(s);
        for(int i=0;i<=n+1;i++)for(int j=0;j<26;j++)cnt[i][j]=0;
        for(int i=n-1;i>=0;i--)for(int j=0;j<26;j++)cnt[i][j]=cnt[i+1][j]+(s[i]=='a'+j);
        for(int i=0;i<n;i++)g[s[i]-'a'].push_back(i);
        vector<int>::iterator head[26];
        for(int i=0;i<26;i++)head[i]=g[i].begin();
        ans=last=-1;    
        for(int i=0;i<k;i++){
            int f1=0;
            for(int j=0;j<26;j++){
                if(used[j]==r[j])continue;
                while(head[j]!=g[j].end()&&(*head[j])<=last)head[j]++;
                if(head[j]==g[j].end())continue;
                used[j]++;
                int pos=*head[j],sum1=0,sum2=0,flag=1;
                for(int t=0;t<26;t++){
                    if(cnt[pos+1][t]+used[t]<l[t])flag=0;
                    sum1+=max(l[t]-used[t],0);
                    sum2+=min(cnt[pos+1][t],r[t]-used[t]); 
                }
                if(sum1>k-i-1||sum2<k-i-1)flag=0;
                if(!flag)used[j]--;
                else{
                    res[i]='a'+j;
                    f1=1;
                    last=pos;
                    break;
                }
            }
            if(!f1){
                printf("-1\n");        
                ans=1;
                break;
            }
        }
        if(ans==-1){//如果有答案 
            res[k]=0;
            printf("%s\n",res);
        }
    }
    return 0;
}