[AT2698] Don't Be a Subsequence

题目大意：给定一个字符串，求一个最短的串要求没有在该字符串的子串中出现过，如果有多个，输出字典序最小的那一个。

题解：倒着跑一遍原字符串（以下编号为$1\sim n$），按出现了所有$26$个字母来分段，把完整的段从左到右编号，第$i$段为$[l_i,r_i]$，答案的长度就是分成的完整的段$+1$，考虑字典序最小，第一个字母一定是$[1,l_i)$中最小的没有出现的字符；对于第$i$位答案，令$x$为$ans_{i-1}$在$[l_{i-1},r_{i-1}]$中第一次出现的位置，则$ans_i$等于在$[x,r_{i-1}]$中最小的没出现过的字符

卡点：无

C++ Code：

#include <cstdio>

#include <cstring>

#define maxn 200010

#define N maxn / 26 + 10

char s[maxn];

int l[N], r[N];

int cnt[26];

int sum[maxn][26], nxt[maxn][26];

int n, m, sz, ans;

char find(int r, int l = 0) {

	for (int i = 0; i < 26; i++) if (!(sum[r][i] - sum[l][i])) return i + 97;

	return 20040826;

}

int main() {

	sz = sizeof cnt;

	scanf("%s", s + 1);

	n = strlen(s + 1);

	int num = 0; r[m = 1] = n;

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

		memcpy(nxt[i], nxt[i + 1], sz);

		int x = s[i] - 'a';

		nxt[i][x] = i;

		num += cnt[x]++ == 0;

		if (num >= 26) {

			l[m] = i;

			r[++m] = i - 1;

			memset(cnt, 0, sz);

			num = 0;

		}

	}

	for (int i = 1; i <= n; i++) {

		memcpy(sum[i], sum[i - 1], sz);

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

	}

	putchar(ans = find(r[m]));

	for (int i = m - 1; i; i--) putchar(ans = find(r[i], nxt[l[i]][ans - 'a']));

	putchar(10);

	return 0;

}

巴特西

[AT2698] Don't Be a Subsequence

最新文章

热门文章