2019HDU多校第一场 String 贪心

题意：给你一个字符串，问是否存在一个长度为m的子序列，子序列中对应字符的数目必须在一个范围内，问是否存在这样的字符串？如果存在，输出字典序最小的那个。

思路：贪心，先构造一个序列自动机，序列自动机指向在它后面离它最近的某个字符的位置。对于当前位置，从a开始枚举字符，如果答案串的下个位置填这个字符可以，就立马填上这个字符，最后看一下贪心构造的字符串长度是不是m就可以了。

代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;

int cnt[26], last[26], l[26], r[26];

int ssum[maxn][26], Next[maxn][26];

int n, m, tot;

char s[maxn], ans[maxn];

bool valid(int x) {

	if(x == n + 1) {

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

			if(cnt[i] >= l[i] && cnt[i] <= r[i]) continue;

			return 0;

		}

		if(tot != m) return 0;

		return 1;

	}

	bool flag = 1;

	cnt[s[x] - 'a']++;

	tot++;

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

		if(ssum[x + 1][i] + cnt[i] >= l[i] && cnt[i] <= r[i]) continue;

		else flag = 0;

	}

	int tmp = 0;

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

		tmp += max(l[i] - cnt[i], 0);

	}

	if(m - tot > n - x + 1) flag = 0;

	if(m - tot < tmp) flag = 0;

	if(flag == 0) {

		tot--;

		cnt[s[x] - 'a']--;

		return 0;

	}

	return 1;

}

int main() {

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

		tot = 0;

		scanf("%d", &m);

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

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

		}

		n = strlen(s + 1);

		memset(ssum[n + 1], 0, sizeof(ssum[n + 1]));

		memset(cnt, 0, sizeof(cnt));

		for (int j = 0; j < 26; j++) last[j] = n + 1;

		for (int i = n; i >= 1; i--) {

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

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

				Next[i][j] = last[j];

			}

			ssum[i][s[i] - 'a']++;

			last[s[i] - 'a'] = i;

		}

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

			Next[0][i] = last[i];

		int pos = 0;

		while(pos <= n && tot < m) {

			bool flag = 0;

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

				if(valid(Next[pos][j])) {

					ans[tot] = 'a' + j;

					pos = Next[pos][j];

					flag = 1;

					break;

				}

 			}

 			if(flag == 0) break;

		}

		if(tot == m) {

			ans[tot + 1] = 0;

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

		} else {

			printf("-1\n");

		}

	}

}