BZOJ 3998: [TJOI2015]弦论(后缀自动机）

解题思路

　　\(T=0\)时就和SP7258一样，\(T=1\)时其实也差不多，只不过要把每个点原来是\(1\)的权值改为\(Right\)集合的大小。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

const int MAXN = 500005;

int k,type,cnt,lst,n,T;

int fa[MAXN<<1],ch[MAXN<<1][27],l[MAXN<<1],siz[MAXN<<1];

int c[MAXN<<1],a[MAXN<<1],f[MAXN<<1];

char s[MAXN];

inline void Insert(int c){

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

	for(;p && !ch[p][c];p=fa[p]) ch[p][c]=np;

	if(!p) fa[np]=1;

	else {

		int q=ch[p][c];

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

		else {

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

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

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

			for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;

		}

	}

	siz[np]=1;

}

inline void query(int x){

	int p=1;

	while(x){

		for(int i=1;i<=26;i++)if(ch[p][i]){

			if(f[ch[p][i]]+siz[p]<=x) x-=f[ch[p][i]];

			else {p=ch[p][i];putchar('a'+i-1);x-=siz[p];break;}

		}

	}

}

int main(){

	scanf("%s%d%d",s+1,&T,&k);cnt=lst=1;n=strlen(s+1);

	for(int i=1;i<=n;i++) Insert(s[i]-'a'+1);

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

	for(int i=1;i<=cnt;i++) c[i]+=c[i-1];

	for(int i=1;i<=cnt;i++) a[c[l[i]]--]=i;

	if(T){

		for(int i=cnt;i;i--){int p=a[i];siz[fa[p]]+=siz[p];}

	}

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

		int p=a[i];if(T) f[p]=siz[p];else f[p]=siz[p]=1;

		for(int j=1;j<=26;j++)if(ch[p][j])

			f[p]+=f[ch[p][j]];

	}

	if((n*(n+1)/2<k)) puts("-1");

	else query(k);

	return 0;

}

巴特西

BZOJ 3998: [TJOI2015]弦论(后缀自动机）

解题思路

代码

最新文章

热门文章