题意：

给你一个串，现需要你给出一个子序列，满足26个约束条件，\(len(A_i) >= L_i\) 且 \(len(A_i) <= R_i\)， \(A_i\)为从a到z的26个字母。

思路：

先用序列自动机（？）构造出某个位置后每个字母的个数，每个字母的第一个位置。

然后每次贪心地加入最小的字符，加入的条件为当前字母加入后，后面的字符满足剩余的条件。

即剩余的字母\(A_i\)在不超\(R_i\)的情况下能构成k长度的串，剩余的字母\(A_i+\)已拿取字母\(A_i >= L_i\)且满足\(L_i\)所需的长度小于剩余可添加长度。

官方题解：

代码：

#include<cstdio>

#include<set>

#include<cmath>

#include<stack>

#include<vector>

#include<queue>

#include<cstring>

#include<string>

#include<sstream>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn = 1e5 + 5;

const ll INF = 1e18;

int nex[maxn][30];

char s[maxn];

int len, k;

int l[30], r[30];

int cnt[maxn][30], getnum[30];

char ans[maxn];

bool check(int pos, int nowlen){

    int len = 0;

    int dis = 0;

    for(int i = 0; i < 26; i++){

        if(getnum[i] + cnt[pos][i] < l[i]) return false;

        len += getnum[i] + min(r[i] - getnum[i], cnt[pos][i]);

        dis += max(0, l[i] - getnum[i]);

    }

    if(len < k) return false;

    if(dis > k - nowlen) return false;

    return true;

}

int main(){

    while(~scanf("%s%d", s + 1, &k)){

        len = strlen(s + 1);

        for(int i = 0; i < 26; i++){

            scanf("%d%d", &l[i], &r[i]);

        }

        memset(nex[len], -1, sizeof(nex[len]));

        memset(cnt[len], 0, sizeof(cnt[len]));

        for(int i = len - 1; i >= 0; i--){

            for(int j = 0; j < 26; j++){

                nex[i][j] = nex[i + 1][j];

                cnt[i][j] = cnt[i + 1][j];

            }

            nex[i][s[i + 1] - 'a'] = i + 1;

            cnt[i][s[i + 1] - 'a']++;

        }

        memset(getnum, 0, sizeof(getnum));

        int pos = 0, tot = 0;

        bool ok = true;

        while(pos <= len && tot < k){

            bool can = false;

            for(int i = 0; i < 26; i++){

                if(nex[pos][i] != -1 && getnum[i] < r[i]){

                    getnum[i]++;

                    if(check(nex[pos][i], tot + 1)){

                        can = true;

                        ans[tot++] = i + 'a';

                        pos = nex[pos][i];

                        break;

                    }

                    getnum[i]--;

                }

            }

            if(!can){

                ok = false;

                break;

            }

        }

        ans[tot] = '\0';

        if(ok) printf("%s\n", ans);

        else printf("-1\n");

    }

    return 0;

}

巴特西

杭电多校HDU 6586 String（预处理 + 贪心）题解

题意：

思路：

官方题解：

代码：

最新文章

热门文章