bzoj 3998 [TJOI2015]弦论—

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3998

相同子串算多个的话，先求好 right ，然后求一个 sm 表示走到这个点之后有几种走法，即把 DAG 上自己能走到的点的 right 都收集起来，可用拓扑序解决。

相同子串算一个的话，给 DAG 上每个节点都赋上一个1，表示走到那个节点的话算一个子串；然后把 DAG 上自己能走到的点的1都收集起来。

然后可按字典序 dfs 这个 DAG ，如果 k 在这个分支里的话就走进去，否则 k -= sm[ ] ，然后看别的分支。

不用管 len[ ] ，因为 len[ ] 表示自己这个点管辖的许多子串，但如果自己是 dfs 地走过来，就只对应了其中一个子串，所以只用管 right 就行了。

之所以相同子串算一个的话要给复制出来的那些 nq 也赋一个1，是因为 nq 只是分了一些 q 管辖的子串；如果自己 dfs 着本应走到 q 点，但因为 nq 分管了一些而走到了 nq 点的话，自己也算走到了一个子串结尾的位置（1个而不是len个），所以应该计数1。

注意用 a[ i ] 而不是 i 。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=5e5+,M=1e6+,K=;

int lst=,cnt=,go[M][K],fa[M],l[M],rt[M];ll sm[M];

int tx[N],a[M];

char ch[N];

void add(int w)

{

  int p=lst,np=++cnt;lst=np;l[np]=l[p]+;rt[np]=;

  for(;p&&!go[p][w];p=fa[p])go[p][w]=np;

  if(!p)fa[np]=;

  else

    {

      int q=go[p][w];

      if(l[q]==l[p]+)fa[np]=q;

      else

    {

      int nq=++cnt;l[nq]=l[p]+;

      fa[nq]=fa[q];fa[q]=nq;fa[np]=nq;

      memcpy(go[nq],go[q],sizeof go[q]);

      for(;go[p][w]==q;p=fa[p])go[p][w]=nq;

    }

    }

}

void Rsort(int n,bool T)

{

  for(int i=;i<=cnt;i++)tx[l[i]]++;

  for(int i=n-;i>=;i--)tx[i]+=tx[i+];

  for(int i=cnt;i;i--)a[tx[l[i]]--]=i;

  for(int i=;i<=cnt;i++)

    {

      int d=a[i];

      if(!T)rt[d]=;

      else rt[fa[d]]+=rt[d];

    }

  //  if(T)for(int i=1;i<=cnt;i++)rt[fa[a[i]]]+=rt[a[i]];//if()!!!!///a[]!!!!!!

  for(int i=;i<=cnt;i++)

    {

      int d=a[i];///

      sm[d]=rt[d];

      for(int j=;j<=;j++)

    if(go[d][j])

      {

        sm[d]+=sm[go[d][j]];

      }

    }

  rt[]=;//

}

int main()

{

  scanf("%s",ch);int n=strlen(ch);

  for(int i=;i<n;i++)add(ch[i]-'a'+);

  int T,k; scanf("%d%d",&T,&k);

  Rsort(n,T);

  int cr=;

  bool flag=;

  while()

    {

      if(rt[cr]>=k)break;

      k-=rt[cr]; int ycr=cr;

      for(int i=,d;i<=;i++)

    if(sm[d=go[cr][i]]>=k)

      {putchar(i+'a'-);cr=d;break;}

    else k-=sm[d];

      if(cr==ycr){printf("-1");break;}

    }

  return puts("");

}

巴特西

bzoj 3998 [TJOI2015]弦论——后缀自动机

最新文章

热门文章