【BZOJ 4319】[CERC2008] Suffix Reconstruction

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4319
神犇题解:http://www.cnblogs.com/Skyminer/p/6414088.html

解题报告

之前在做这个题的时候就听说过这题
但当时想了一会儿,感觉不可做,以为是他们记错题目了 QwQ
今天居然看到原题了,但想了很久,还是只会$O(26 \cdot n \log{n})$

先来说说$O(26 \cdot n \log{n})$的做法吧!
我们可以从上到下单个字符填,就是尽量往小的填,填完以后$O(n)$验证一遍

我们考虑分出不同的地方,因为填了都是比他小的,所以如果冲突,那一定是之前的太大了
但之前的部分已经贪心尽量小地填了,所以之前的肯定不能改小了,只能把当前位改大

所以这么做是对的,时间复杂度:$O(26 \cdot n^2)$
不难发现$SA$数组上一定是一段连续的A,之后一段连续的B。后面也是这样
于是我们可以二分每一个字符地分界点,这样复杂度就是$O(26 \cdot n \log{n})$的了

正解的话,是$O(n)$的,仍然是从小到大贪心
我们考虑计算$height$数组时候那个Trick的正确性证明
如果$rank[sa[i]+1] > rank[sa[i+1]+1]$的话,那么$sa[i]$填的字符一定比$sa[i+1]$小
否则他俩相等也没有关系,因为后面还是会把他们区分出来
于是贪心就可以$O(1)$验证了,于是总的时间复杂度就是线性的了!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500009;

int n,sa[N],rak[N];
char ans[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main() {
	n = read(); 
	for (int i=1;i<=n;i++) rak[sa[i]=read()]=i;
	ans[sa[1]] = 'a';
	for (int i=1,w='a';i<n;i++) (rak[sa[i]+1]>rak[sa[i+1]+1])? ans[sa[i+1]]=++w: ans[sa[i+1]]=w;
	if (ans[n] <= 'z') printf("%s",ans+1);
	else puts("-1");
	return 0;
}

22 thoughts to “【BZOJ 4319】[CERC2008] Suffix Reconstruction”

  1. Howdy, i read your blog from time to time and i own a similar one
    and i was just wondering if you get a lot of spam comments?
    If so how do you stop it, any plugin or anything you can advise?
    I get so much lately it’s driving me insane so any support is very much appreciated.

  2. Very nice post. I just stumbled upon your blog and wished to say that I have
    truly enjoyed browsing your blog posts. After all I’ll be subscribing to your
    rss feed and I hope you write again very soon!

  3. Hey would you mind stating which blog platform you’re using?
    I’m going to start my own blog in the near future
    but I’m having a tough time selecting between BlogEngine/Wordpress/B2evolution and Drupal.

    The reason I ask is because your design and style seems different then most blogs and I’m looking
    for something completely unique. P.S My apologies for getting off-topic
    but I had to ask!

  4. We stumbled over here from a different web address and thought I should check things out.

    I like what I see so now i am following you. Look forward to finding out
    about your web page for a second time.

  5. Hey there! Quick question that’s completely off topic. Do you
    know how to make your site mobile friendly? My blog looks weird when viewing from
    my iphone4. I’m trying to find a theme or plugin that might be able
    to fix this problem. If you have any recommendations, please
    share. With thanks!

  6. Nice blog here! Also your site loads up very fast!
    What web host are you using? Can I get your affiliate
    link to your host? I wish my website loaded up as fast as yours lol

  7. Hi! This is my first comment here so I just wanted to give a quick shout out and say I truly enjoy
    reading your articles. Can you suggest any other blogs/websites/forums that
    cover the same subjects? Thanks a lot!

  8. What’s up it’s me, I am also visiting this web page regularly,
    this web site is in fact good and the viewers are truly sharing
    nice thoughts.

  9. Heya i’m for the first time here. I found this board and
    I find It really useful & it helped me out much. I hope to give something back and aid others like you
    aided me.

  10. Good blog you have got here.. It’s hard to find high quality writing like yours nowadays.
    I truly appreciate individuals like you! Take care!!

  11. You made some decent points there. I looked on the net to find out more about the issue and found most people will go along with your views
    on this website.

  12. Thanks a lot for sharing this with all people you actually recognise what you’re speaking about!

    Bookmarked. Kindly additionally talk over with my site =).
    We may have a link exchange arrangement between us

  13. Everyone loves what you guys tend to be up too. This kind of clever
    work and reporting! Keep up the wonderful works guys I’ve added you guys to our blogroll.

  14. Thanks , I’ve recently been searching for information about this topic for
    a long time and yours is the best I’ve came upon till now.
    However, what concerning the conclusion? Are you certain concerning the supply?

Leave a Reply

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