求助一道题目

回复帖子

@幻夢の雨 2020-03-27 09:12 回复

时间:0.2 空间:512M

题目描述:

输入一个字符串a,求不是它的子序列的最短串。如果有多个,输出字典序最小的。

输入格式

一个字符串a

输出格式:

输出格式见题目描述

样例输入:

abcdefghijklmnopqrstuvwxyz

样例输出:

aa

约定:

a的长度小于等于200000,a只包含小写字母。


求助这道题怎么做

@幻夢の雨 2020-03-27 09:26 回复 举报
#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;
}
@SyadouHayami 2020-03-27 09:28 回复 举报

我在想可不可以用最短路来做,毕竟添加字母和最短路的转移很像。

但是这道题 dp 更加显然吧。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。