题解 P3728 【曼哈顿序列】

· · 题解

可以到我的博客食用(不一定更佳哦)
题面
如果要求的是第k小字串(即连续子序列)，是可以用后缀自动机做的
然而这道题要求第k小子序列
其实序列自动机也是有的，而且构建及其简单
状态有n+1个，第一个为根，后面的和字符串每一位一一对应
对于第i位对应的状态，接收字符c后转移到j 满足

j=\min_{x\in (i,n]~and~s_j=c}x

说人话就是最近的一个c
感性的理解:我从最前面一个走就能涵盖从后面走的所有情况
然后这个自动机上每一条从根出发的路径唯一对应一个子序列(不重复)
于是求出每个状态能到达的子序列数(也就是从该点出发的路径数)，然后扫一遍即可(不会的话可以参考后缀自动机的做法)
注意一下路径数可能会很大很大，不需要高精，如果一个节点对应的路径数超过k，那么超过部分显然没有意义，直接赋为k即可

#include <bits/stdc++.h>
using namespace std;
int son[1000010][26], n, k;
int tot[1000010];
char s[1000010];
int main() {
    scanf("%d%d", &n, &k);
    scanf("%s", s + 1);
    for(int i = n - 1; i >= 0; i--) {//构建序列自动机
        memcpy(son[i], son[i + 1], sizeof(int[26]));
        son[i][s[i + 1] - 'a'] = i + 1;
    }
    for(int i = n; i >= 0; i--) {//0到n为天然的拓扑序
        long long ans = 1;
        for(int j = 0; j < 26; j++) ans += tot[son[i][j]];//计算路径数
        tot[i] = min(ans, (long long)k);//如果过大就钦定为k
    }
    k++;//这种做法会算上空序列
    for(int now = 0; ;) {
        k -= 1;//去掉空序列(最小)
        if(k == 0) return 0;
        for(int j = 0; j < 26; j++) {
            if(son[now][j] == 0) continue;
            if(k > tot[son[now][j]]) k -= tot[son[now][j]];
            else {
                putchar(j + 'a');
                now = son[now][j];
                break;//转换为子问题
            }
        }
    }
}