这个题说实话不难（会了就不难了.jpg） 首先搞一个序列自动机（每个位置向其后每种字符首次出现位置连边）来贪心，每次走的时候先考虑字典序小的。如果一个位置是合法可走的，那么他要满足那26个约束条件，这个问题使用一个后缀和来处理。走之前，检查要走的位置后面每种字符是不是都能满足最低要求即可。 接着要考虑正好取够k个的问题，面对bcdbcda，只要求取1个a，其他不要求取，但是k > 1这种样例，上述做法如果不加限制，那么肯定会直接飞到a，而a后面已经无物可取了，即还要保证走的位置后面至少能够取完k个（该位置起始后缀长度要大于k - 已取长度，即至少无脑全选，可以搞出k个）。 然后还需要计算一下走的位置对满足约束做出的贡献。有的时候约束只要求你取一点点字符即可满足，剩下的位置自然是要为字典序最小服务的，这些多余不受约束的位置，必须不能挤占必须选取的位置。 满足上述所有约束，序列自动机中取k个，就是答案，取不到k个，输出-1。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 5; /* abcdabcda 4 2 100 1 1 0 100 1 100 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 */ int k, len, l, r; char s[maxn]; vector<pair<int, int>> seg; struct seqam { int next[maxn][26]; int sum[maxn][26], cnt[26]; void build() { memset(sum, 0, sizeof(sum)); memset(cnt, 0, sizeof(cnt)); for (int i = len; i > 0; --i) { for (int j = 0; j < 26; ++j) { next[i - 1][j] = next[i][j]; } next[i - 1][s[i] - 'a'] = i; } for (int i = len; i > 0; --i) { for (int j = 0; j < 26; ++j) { sum[i][j] = sum[i + 1][j]; } ++sum[i][s[i] - 'a']; } } void solve() { int p = 0, now = 0; vector<int> ans; while (now < k) { bool cctt = 0; for (int i = 0; i < 26; ++i) { if (!next[p][i]) { continue; } if (cnt[i] + 1 > seg[i].second) { continue; } bool flag = 1; for (int j = 0; j < 26; ++j) { if (cnt[j] < seg[j].first && sum[next[p][i]][j] < seg[j].first - cnt[j]) { flag = 0; break; } } if (flag && len - next[p][i] + 1 >= k - now) { ++cnt[i]; int res = 0; for (int j = 0; j < 26; ++j) { res += max(0, seg[j].first - cnt[j]); } if (res > k - now - 1) { --cnt[i]; continue; } p = next[p][i]; ans.push_back(i); cctt = 1, ++now; break; } } if (!cctt) { break; } } if (ans.size() < k) { printf("-1\n"); return; } for (auto e : ans) { printf("%c", char('a' + e)); } printf("\n"); } } seq; int main() { while (~scanf("%s%d", s + 1, &k)) { len = strlen(s + 1); seg.clear(); for (int i = 0; i < 26; ++i) { scanf("%d%d", &l, &r); seg.push_back({l, r}); } seq.build(); seq.solve(); } return 0; }