相关链接
题目传送门: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; }
I always emailed this website post page to all my friends,
since if like to read it next my links will too.
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.
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!
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!
I constantly emailed this blog post page to all my associates, because if like to read it
afterward my contacts will too.
whoah this blog is fantastic i love studying your posts. Stay up
the great work! You recognize, many people are hunting round for this info,
you can help them greatly.
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.
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!
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
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!
I adore looking at and I think this website got some genuinely useful stuff on it! .
My brother recommended I would possibly like
this web site. He was once entirely right. This
post truly made my day. You cann’t consider just how so
much time I had spent for this information! Thanks!
It’s in reality a nice and useful piece of information. I’m satisfied that
you simply shared this helpful info with us.
Please keep us informed like this. Thanks for sharing.
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.
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.
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!!
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.
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
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.
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?
At this time I am ready to do my breakfast, after having my
breakfast coming again to read more news.
I’m still learning from you, while I’m trying to reach my goals. I definitely liked reading all that is written on your site.Keep the aarticles coming. I liked it!