【BZOJ 2342】[Shoi2011] 双倍回文

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2342

manacher自己做的第一题! 2A! 撒花! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*
最开始看这个题:树套树?二维偏序的既视感……然而树套树求取区间最值的空间复杂度绝对过不了
于是可耻看题解,瞄了一眼:用set就可以水掉QAQ
于是再自己推一推,确定两个set连起来就可以搞
搞一搞520ms水过去了
再一看题解,还可以只用一个set水过去QAQ
不过跑出来反而比hzwer的一个set快一点……..

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;

const int MAXN = 1200000; 

char pat[MAXN],BUF[MAXN];
int p[MAXN],rt,n,len,vout;

inline void manacher(){
	len = n*2+1; 
	for (int i=1,p1,p2;i<=len;i++){ if (p[rt]+rt > i) p[i] = min(p[rt*2-i],p[rt]+rt-i);
		else p[i] = 0; p1 = i+p[i]; p2 = i-p[i];
		while (pat[++p1] ==  pat[--p2]) p[i]++;
		if (pat[rt]+rt < p[i]+i) rt = i;
	}
}

inline void init(){
	scanf("%d%s",&n,BUF+1);
	for (int i=1;i<=n;i++){
		pat[i*2-1] = '@';
		pat[i*2] = BUF[i];
	} pat[n*2+1] = '@';
	pat[0] = '#'; pat[n*2+2] = '$';
}

struct cmp{
	bool operator () (const int &a, const int &b){
		return a+p[a] < b+p[b];
	}
}; 

set<int> por;
set<int,cmp> list;
set<int>::iterator itr;
set<int,cmp>::iterator ITR;
pair<set<int,cmp>::iterator,bool> TMP;

inline void solve(){
	for (int i=3;i<=len;i+=2){
		int p1 = i-p[i]/2,buf=0;
		itr = por.lower_bound(p1);
		if (itr != por.end()){  
			buf = (i-*itr+1)/2;
			vout = max(vout, buf*4);
		}
			
		TMP = list.insert(i);
		if (TMP.second) por.insert(i);		
		
		ITR = list.begin();
		while (!list.empty() && *ITR+p[*ITR] < i+2) 
			por.erase(*ITR), list.erase(ITR),ITR = list.begin();
	}
	printf("%d",vout);
}

int main(){
	init();
	manacher();
	solve(); 
	return 0;	
} 

22 thoughts to “【BZOJ 2342】[Shoi2011] 双倍回文”

  1. Yesterday, while I was at work, my cousin stole
    my iPad and tested to see if it can survive a 30
    foot drop, just so she can be a youtube sensation.
    My apple ipad is now broken and she has 83 views. I know this is
    completely off topic but I had to share it with someone!

  2. Every weekend i used to pay a visit this web site,
    because i want enjoyment, for the reason that this this web site conations genuinely pleasant
    funny stuff too.

  3. I’m very happy to discover this page. I want to to thank you for your
    time for this particularly fantastic read!!
    I definitely really liked every bit of it and i also have you saved
    as a favorite to look at new information in your site.

  4. I know this if off topic but I’m looking into starting
    my own blog and was curious what all is required to get setup?
    I’m assuming having a blog like yours would cost a pretty penny?

    I’m not very internet savvy so I’m not 100% certain. Any suggestions
    or advice would be greatly appreciated. Many thanks

  5. We are a gaggle of volunteers and starting a brand new
    scheme in our community. Your website offered us with helpful
    information to work on. You’ve done a formidable activity and our entire community will be thankful to you.

  6. Superb post but I was wondering if you could write a litte
    more on this subject? I’d be very grateful if you could elaborate a little bit further.
    Bless you!

  7. You actually make it appear so easy with your presentation but I in finding this matter to be really something which I feel I would never understand. It sort of feels too complex and extremely broad for me. I’m looking ahead on your next put up, I¦ll try to get the hold of it!

  8. I’ve been browsing online more than 3 hours today, yet I never
    found any interesting article like yours. It’s pretty worth enough for me.
    In my opinion, if all web owners and bloggers made
    good content as you did, the web will be a lot more
    useful than ever before.

  9. Please let me know if you’re looking for a article author for your blog.

    You have some really great articles and I believe
    I would be a good asset. If you ever want to take some of
    the load off, I’d absolutely love to write some articles for your blog
    in exchange for a link back to mine. Please shoot me an email if interested.
    Thank you!

  10. It’s really a cool and helpful piece of information. I am happy that you simply shared
    this useful information with us. Please stay us up to date like
    this. Thank you for sharing.

  11. I’m truly enjoying the design and layout of
    your blog. It’s a very easy on the eyes which makes it
    much more pleasant for me to come here and visit more often. Did you hire out a designer to create your theme?

    Excellent work!

Leave a Reply

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