题解 P3975 【[TJOI2015]弦论】

皎月半洒花

2019-12-13 20:15:27

Solution

~~虽然感觉这题已经被人做烂了再发题解也没啥意思了~~ 这篇题解是非bfs版,感觉更好理解也更好写?反正我觉得初学者如果写这种dp的话应该会更容易理解?emm反正比其他题解思路更直观一点。 首先就是SAM就完事儿了。 然后考虑怎么求这个东西,那肯定先在parent树上dp一遍求出来每个子串的出现次数; 但问题是我们如果要像平衡树那样找第$k$小,求的应该是经过每个点的子串数量,于是就需要在DAG上再dp一遍。 然而上面是老生常谈。由于是DAG,~~所以想怎么dp怎么dp~~所以会比较容易,直接dfs就完了,这样感觉思路比较顺 ~~画外音:为啥总感觉这个人在水题解啊?这不就是换了个dp方式吗~~ ~~我不是我没有……并且感觉这题除了dp还有什么别的值得一提的地方吗?~~ ```cpp struct SAM{ int last, sz ; int trans[MAXN][Sigma] ; int len[MAXN], fa[MAXN] ; void Init(){ last = sz = 1 ; } void Insert(int x){ int np = ++ sz ; int p = last, q, nq ; last = np, f[np] = 1 ; len[np] = len[p] + 1 ; while (p && !trans[p][x]) trans[p][x] = np, p = fa[p] ; if (!p) return fa[np] = 1, void() ; q = trans[p][x] ; if (len[q] == len[p] + 1) return fa[np] = q, void() ; nq = ++ sz, len[nq] = len[p] + 1; fa[nq] = fa[q], fa[q] = fa[np] = nq ; memcpy(trans[nq], trans[q], sizeof(trans[q])) ; while (p && trans[p][x] == q) trans[p][x] = nq, p = fa[p] ; } }S; il void add(int u, int v){ E[++ ctn].to = v, E[ctn].next = head[u], head[u] = ctn ; } void dfs(int u){//第一次的树上dp for (int k = head[u] ; k ; k = next(k)) dfs(to(k)), f[u] += f[to(k)] ; } void dfs2(int u){//第二次的DAG上dp if (vis[u]) return ; vis[u] = 1 ; for (int i = 1 ; i <= 26 ; ++ i) if (S.trans[u][i]) dfs2(S.trans[u][i]), g[u] += g[S.trans[u][i]] ; } void go_Out(int p, int s){//输出 if (s <= f[p]) return ; else s -= f[p] ; for (int i = 1 ; i <= 26 ; ++ i) if (!S.trans[p][i]) continue ; else if (s > g[S.trans[p][i]]) s -= g[S.trans[p][i]] ; else { printf("%c", i + 'a' - 1), go_Out(S.trans[p][i], s) ; return ; } } int main(){ cin >> (In + 1) >> T >> K ; N = strlen(In + 1) ; S.Init() ; for (int i = 1 ; i <= N ; ++ i) S.Insert(In[i] - 'a' + 1) ; for (int i = 2 ; i <= S.sz ; ++ i) add(S.fa[i], i) ; dfs(1) ; for (int i = 1 ; i <= S.sz ; ++ i) g[i] = T ? f[i] : (f[i] = 1) ; f[1] = g[1] = 0, dfs2(1) ; if (K > g[1]) return puts("-1"), 0 ; else return go_Out(1, K), 0 ; } ``` ## $\rm by~Orchidany$