【BZOJ 3998】[TJOI2015] 弦论

Qizy Suffix Array, Suffix Automaton, 字符串, 解题报告

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3998
离线版题目：http://paste.ubuntu.com/18145026/
数据生成器：http://paste.ubuntu.com/18145048/

解题报告

这个，SAM求k小串的板题，然而我这个纸张写了两次、调了7h+才过QAQ     (浅谈模板写挂了的悲伤有多大.pdf
t==0 -> 后缀自动机的每一个节点只代表一个串
t==1 -> 后缀自动机的每一个节点代表|fail数的大小|个节点
然后顺着走一走就好。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 1000000+9;
const int SGZ = 26;

char pat[MAXN];
int n,t; LL k;

namespace Suffix_Automaton{
	#define SAM Suffix_Automaton
	int ch[MAXN][SGZ],fail[MAXN],sz[MAXN],len[MAXN];
	int cnt,last,bot[MAXN],ord[MAXN]; LL cho[MAXN];
		
	inline void extend(int c){
		int w = last; last = ++cnt; 
		len[last] = len[w]+1; sz[last]=1;
		while (w && !ch[w]) ch[w] = last, w=fail[w];
		if (!w) fail[last] = 1;
		else {
			int nw = ch[w];
			if (len[nw] == len[w]+1) fail[last] = nw;
			else {
				int nnw = ++cnt; len[nnw] = len[w]+1;
				for (int i=0;i<SGZ;i++) ch[nnw][i]=ch[nw][i];
				fail[nnw] = fail[nw]; fail[nw] = fail[last] = nnw;
				while (w && ch[w]==nw) ch[w] = nnw, w = fail[w];
			}
		}
	}
	
	inline void build(){
		cnt = last = 1;
		n = strlen(pat+1);
		for (int i=1;i<=n;i++)
			extend(pat[i]-'a');
	}
	
	inline void sign(){
		for (int i=1;i<=cnt;i++) bot[len[i]]++;
		for (int i=1;i<=n;i++) bot[i] += bot[i-1];
		for (int i=cnt;i;i--) ord[bot[len[i]]--] = i;
		
		if (t == 1) for (int j=cnt,i=ord[j];j;i=ord[--j]) sz[fail[i]] += sz[i];
		else for (int i=2;i<=cnt;i++) sz[i] = 1;
		
		for (int j=cnt,i=ord[j];j;i=ord[--j]){
			cho[i] += (LL)sz[i];
			for (int c=0;c<SGZ;c++) 
				cho[i] += cho[ch[i]];
		}
	}
	
	inline void solve(){
		if (cho[1] < k) printf("-1\n");
		else {
			int w = 1; while (k > 0){
				for (int c=0;c<SGZ && k>0;c++) 
					if (cho[ch[w]] < k) k -= cho[ch[w]];
					else {putchar(c+'a');w=ch[w];k-=sz[w];break;}
			}
		}	
	}
};

int main(){
	scanf("%s%d%lld",pat+1,&t,&k);
	SAM::build();
	SAM::sign();
	SAM::solve();
	return 0;
}

194 thoughts to “【BZOJ 3998】[TJOI2015] 弦论”

  29. I’ve been exploring for a bit for any high quality articles or
    weblog posts on this sort of space . Exploring in Yahoo I eventually stumbled upon this site.
    Reading this information So i am happy to show that I’ve a very good uncanny feeling I discovered exactly what
    I needed. I such a lot indisputably will make sure to don?t put
    out of your mind this web site and provides
    it a look on a constant basis.

    Reply

  45. Thank you a lot for sharing this with all of us you actually realize what you’re
    speaking about! Bookmarked. Please additionally
    discuss with my web site =). We can have a hyperlink trade arrangement among us

    Reply

  47. Nice post. I was checking constantly this blog and I’m impressed!
    Very helpful information specially the last part 🙂 I
    care for such info much. I was seeking this certain info for a very long time.
    Thank you and best of luck.

    Reply

  49. Hi, i feel that i saw you visited my website thus i came to return the choose?.I’m attempting to in finding things to improve my web site!I suppose its good
    enough to use a few of your ideas!!

    Reply

  52. Hi there! This is kind of off topic but I need some
    help from an established blog. Is it very difficult to set up your own blog?
    I’m not very techincal but I can figure things out pretty quick.
    I’m thinking about creating my own but I’m not sure where
    to start. Do you have any tips or suggestions? Many thanks

    Reply

  53. Hello There. I found your blog using msn. This is an extremely
    well written article. I’ll make sure to bookmark it and come back
    to read more of your useful information. Thanks for the post.
    I will definitely comeback.

    Reply

  55. Hi there, just became alert to your blog through Google,
    and found that it is really informative. I’m going to watch out for brussels.
    I’ll be grateful if you continue this in future. A lot of people will be benefited from
    your writing. Cheers!

    Reply

  62. Hello! I could have sworn I’ve been to this web site before but after browsing through some of the
    posts I realized it’s new to me. Nonetheless, I’m certainly
    delighted I found it and I’ll be bookmarking
    it and checking back regularly!

    Reply

  64. I got this web site from my buddy who shared with me
    concerning this web page and now this time I am browsing this
    site and reading very informative articles or reviews here.

    Reply

  65. I love your blog.. very nice colors & theme. Did you make this website yourself or did you hire someone to do it for you? Plz answer back as I’m looking to design my own blog and would like to find out where u got this from. cheers

    Reply

  68. I have been browsing online more than 4 hours today, yet I never found any interesting article like yours.
    It’s pretty worth enough for me. Personally, if all webmasters and bloggers made good content as you did, the web will
    be much more useful than ever before.

    Reply

  89. Just want to say your article is as surprising.

    The clearness in your post is simply excellent and i can assume
    you’re an expert on this subject. Well with
    your permission let me to grab your RSS feed to keep up to date with forthcoming post.
    Thanks a million and please keep up the gratifying
    work.

    Reply

  122. Hello there, I do believe your site might be having
    web browser compatibility issues. Whenever I look at your blog in Safari, it looks fine
    however, when opening in IE, it’s got some overlapping issues.
    I merely wanted to give you a quick heads up!
    Besides that, excellent blog!

    Reply

  129. I am in fact glad to glance at this website posts which
    contains tons of helpful information, thanks for providing these kinds of information.

    Reply

  153. Generally I do not read article on blogs, however I wish to say that this write-up very pressured me to try and do it! Your writing taste has been amazed me. Thanks, very nice article.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *