【NOI六连测】[D2T1] 矩阵

题目传送门:http://pan.baidu.com/s/1pLvQmx1
离线版题目:http://paste.ubuntu.com/18292275/
数据传送门:http://pan.baidu.com/s/1dFDf8p7

哎呀,第一次看到这个题,一脸懵逼。之前在POJ上倒是做过矩阵的KMP,但这货没有模式串啊!
但是乱搞了一阵之后,如有神助般想到了二分+Hash,时间复杂度O(n^2*log(n))嗯,刚刚好!
于是就开始码Hash,码完之后不放心,还写了一个O(n^4)的SA来对拍,然后满心欢喜,终于可以A题啦!
然后被卡T了 QAQ, 只有暴力分QAQ, 然后今天就爆炸了,这题写了4h+啊!60分滚粗

下面说一点正事,这题正解也是Hash,那么能体现出优劣的就是Hash的方式了
Ⅰ.Sparse_Table版本http://paste.ubuntu.com/18292055/
在考试的时候YY出来的,提前处理出以每一个点为右上角、边长为2的整次方幂的Hash值
然后任意一个矩阵都可以用4个矩阵拼起来
但是预处理是O(n^2*log(n))的时间复杂度
所以大的点全部跑了1.09-1.27s不等,全部被判T。然而std最大的点都跑了0.6s+啊!被卡常了( ▼-▼ )
Ⅱ.前缀和版本http://paste.ubuntu.com/18292096/
这个是std的算法。统计二维的前缀和,然后每一维单独乘以一个以幂的级数递增的质数
然后要提取矩阵的时候,前缀和减一减,然后统一次数即可。于是预处理只需要O(n^2)即可
Ⅲ.常规矩阵Hashhttp://paste.ubuntu.com/18292122/
之前两个算法都可以做到随机访问。这个Hash方式不行。
它是把x轴和y轴分开Hash,然后滑动窗口,虽然不能做到O(1)的随机访问,但是遍历的话,还是可以做到O(1)的
总结:三种Hash方式应该都是不错的,但从时间复杂度和代码的优美程度来讲,我以后会选择第二种

另外,Hash都会涉及到判重的问题,一般来讲,大家都是使用set
但这一次lcr给我提供了一个很好的解决方案:sort+unique
理论复杂度一样,但实测效果比set快了3-4倍
有图有真相:matrix_set_versionmatrix_unique_version

贴一份前缀Hash+unique的版本:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define UL unsigned long long 
using namespace std;

const int MAXN = 500+9;
const int N = MAXN*MAXN;
const UL P = 131313131;
const UL Q = 49999;

int n,m,lim; char pat[MAXN];
UL mat[MAXN][MAXN],PP[MAXN*2],QQ[MAXN*2],tmp[N];

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

inline UL GetHash(int x, int y, int L){
	UL ret = 0;
	ret = mat[x][y] + mat[x+L][y+L];
	ret -= mat[x+L][y] + mat[x][y+L];
	return ret*PP[1000-y]*QQ[1000-x];
}

inline void init(){
	m = read(); n = read();
	UL p=P,q; lim = min(n,m);
	for (int j=1;j<=m;j++){
		scanf("%s",pat+1);	
		q = Q;
		for (int i=1;i<=n;i++,q*=Q)
			mat[i][j] = (UL)pat[i]*q*p;
		p *= P;
	}
	for (int i=n;i;i--) for (int j=m;j;j--)
		mat[i][j] += mat[i+1][j]+mat[i][j+1]-mat[i+1][j+1];
	QQ[1] = Q; PP[1] = P;
	for (int i=2;i<=1000;i++) 
		QQ[i] = QQ[i-1]*Q,
		PP[i] = PP[i-1]*P;
}

inline bool judge(int L){
	int cnt = 0;
	for (int i=1;i<=n-L+1;i++) 
		for (int j=1;j<=m-L+1;j++)
			tmp[++cnt] = GetHash(i,j,L);
	sort(tmp+1,tmp+1+cnt);
	int tot = unique(tmp+1,tmp+1+cnt) - tmp - 1;
	return tot != cnt;
}

int main(){
	freopen("matrix.in","r",stdin);
	freopen("matrix.out","w",stdout);
	init();
	int l=1,r=lim,mid,vout=0;
	while (l <= r){
		mid = (l+r)/2;
		if (judge(mid)) l = mid+1, vout = mid;
		else r = mid - 1;
	}
	printf("%d\n",vout);
	return 0;
}

327 thoughts to “【NOI六连测】[D2T1] 矩阵”

  1. Do you have a spam issue on this site; I also am a blogger,
    and I was wondering your situation; we have developed some nice procedures and we are looking
    to exchange techniques with other folks, why not shoot me an e-mail if interested.

  2. Thanks for every other excellent article. The place else may
    anyone get that kind of information in such a
    perfect method of writing? I have a presentation next week, and I’m on the look for such info.

  3. Thanks for one’s marvelous posting! I definitely enjoyed reading it,
    you may be a great author.I will make certain to bookmark your blog and will come back in the foreseeable
    future. I want to encourage one to continue your great posts,
    have a nice morning!

  4. I loved as much as you will receive carried out right here.

    The sketch is attractive, your authored subject matter stylish.

    nonetheless, you command get got an impatience over that you wish be delivering the following.
    unwell unquestionably come further formerly again as exactly the same nearly a lot often inside case you shield this increase.

  5. You really make it seem so easy with your presentation but I find
    this topic to be actually something that I think I would
    never understand. It seems too complex and extremely
    broad for me. I’m looking forward for your next post, I’ll try to get
    the hang of it!

  6. certainly like your web-site but you need to test
    the spelling on quite a few of your posts. Many of them are rife
    with spelling issues and I find it very troublesome to inform the reality on the other hand
    I’ll certainly come back again.

  7. Hi there just wanted to give you a quick heads up
    and let you know a few of the pictures aren’t loading properly.
    I’m not sure why but I think its a linking issue. I’ve
    tried it in two different internet browsers and both show the same results.

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

    Outstanding work!

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

  10. Thank you for every other excellent article. The place else could anyone get
    that kind of info in such an ideal approach of writing?
    I have a presentation next week, and I’m at the look
    for such info. natalielise pof

  11. It’s a shame you don’t have a donate button! I’d most certainly donate to this outstanding blog!

    I suppose for now i’ll settle for bookmarking and adding your RSS feed to my Google account.

    I look forward to fresh updates and will share this
    website with my Facebook group. Chat soon!

  12. You could definitely see your expertise within the
    article you write. The world hopes for even more passionate
    writers like you who aren’t afraid to mention how they believe.
    At all times go after your heart. plenty of fish natalielise

  13. Hmm is anyone else encountering problems with the images on this blog loading?
    I’m trying to figure out if its a problem on my end or if it’s the blog.
    Any suggestions would be greatly appreciated.

  14. Thanks for a marvelous posting! I seriously enjoyed reading it, you
    may be a great author. I will make sure to bookmark your blog and will often come back in the future.
    I want to encourage you to ultimately continue your great work, have a nice holiday weekend!

  15. Hey there, I think your site might be having browser compatibility issues.
    When I look at your blog in Chrome, it looks fine but when opening in Internet Explorer, it has some overlapping.
    I just wanted to give you a quick heads up! Other then that,
    excellent blog!

  16. I just like the valuable info you supply on your articles.

    I’ll bookmark your blog and take a look at again here frequently.
    I am slightly certain I’ll learn a lot of new stuff right right here!
    Good luck for the following!

  17. Hello, I think your website might be having browser
    compatibility issues. When I look at your blog in Safari, it looks fine but when opening in Internet
    Explorer, it has some overlapping. I just wanted to give you a quick heads
    up! Other then that, great blog!

  18. Hi there! This is my 1st 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 deal with the same subjects? Thanks a ton!

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

  20. Thanks for the marvelous posting! I actually enjoyed reading it, you may
    be a great author.I will be sure to bookmark your blog and will eventually come back
    very soon. I want to encourage you continue your great
    writing, have a nice afternoon!

  21. Terrific work! This is the kind of info that are supposed to be shared across the internet.
    Shame on Google for now not positioning this post higher!
    Come on over and seek advice from my web site .
    Thanks =)

  22. Thank you a lot for sharing this with all people you
    actually realize what you are talking about! Bookmarked. Please additionally seek advice
    from my web site =). We will have a link change arrangement among
    us

  23. Hey just wanted to give you a quick heads up. The text in your article seem to be
    running off the screen in Chrome. I’m not sure if this is a formatting issue or something to
    do with browser compatibility but I thought I’d post to let you know.
    The style and design look great though! Hope you get the issue fixed soon. Cheers

  24. What i do not understood is in truth how you are not actually a lot more smartly-appreciated than you might be now.
    You are so intelligent. You already know thus considerably in the case of this topic, produced me individually consider it
    from numerous numerous angles. Its like men and women aren’t involved except
    it’s one thing to accomplish with Lady gaga! Your personal
    stuffs excellent. Always handle it up!

  25. Do you have a spam problem on this website; I also am
    a blogger, and I was wondering your situation; we have created
    some nice methods and we are looking to exchange solutions with other folks, please shoot me an e-mail if interested.

  26. Unquestionably consider that which you stated. Your favourite justification seemed to be at the net
    the easiest thing to be aware of. I say to you, I definitely get irked whilst other people think about concerns that they plainly don’t recognize about.
    You controlled to hit the nail upon the top and outlined out
    the whole thing with no need side-effects , other
    people could take a signal. Will probably be again to get more.

    Thanks

  27. Hey very nice blog!! Man .. Excellent .. Wonderful ..

    I will bookmark your blog and take the feeds additionally?
    I’m glad to seek out numerous useful information here in the submit, we want develop more techniques on this regard, thanks for sharing.
    . . . . .

  28. Just want to say your article is as astonishing. The clarity in your post is simply nice and i can assume you’re an expert on this subject.
    Fine with your permission allow me to grab your RSS feed to
    keep up to date with forthcoming post. Thanks a million and please carry
    on the rewarding work.

  29. Excellent pieces. Keep posting such kind of info on your site.
    Im really impressed by your blog.
    Hey there, You have performed an excellent job. I will certainly digg
    it and for my part recommend to my friends. I am confident they’ll be benefited from this site.

  30. Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point.
    You definitely know what youre talking about, why waste your intelligence on just posting videos to your
    site when you could be giving us something informative
    to read?

  31. I blog frequently and I genuinely appreciate your information. This great article has really peaked my interest.
    I am going to take a note of your website and keep checking for
    new details about once a week. I opted in for your RSS feed as
    well.

  32. When I originally commented I seem to have clicked
    the -Notify me when new comments are added- checkbox and from now on whenever
    a comment is added I receive four emails with the same comment.
    There has to be an easy method you are able to remove me from that service?

    Cheers!

  33. Thanks for the auspicious writeup. It in fact was a enjoyment account it.
    Glance complicated to far brought agreeable from
    you! However, how could we communicate?

  34. I’m not sure why but this weblog is loading very slow
    for me. Is anyone else having this problem or is it a issue on my
    end? I’ll check back later and see if the problem
    still exists.

  35. Wonderful work! That is the kind of information that are
    meant to be shared around the web. Shame on the search engines for now not positioning this post upper!
    Come on over and consult with my site . Thanks =)

  36. Everyone loves what you guys tend to be up too.

    Such clever work and reporting! Keep up the good works guys I’ve incorporated you guys to my own blogroll.

  37. Have you ever considered about including a little bit more than just your articles?
    I mean, what you say is valuable and everything. But imagine if you added some great
    images or video clips to give your posts more, “pop”!
    Your content is excellent but with pics and video clips, this
    website could definitely be one of the greatest in its niche.
    Great blog!

  38. I used to be suggested this website by my cousin. I am no longer positive whether this put up
    is written by way of him as nobody else know such designated approximately my problem.
    You are wonderful! Thanks!

  39. I was curious if you ever considered changing the layout
    of your site? Its very well written; I love what youve got to say.
    But maybe you could a little more in the way of content so people could connect with it
    better. Youve got an awful lot of text for only having
    one or 2 images. Maybe you could space it out better?

  40. My brother suggested I might like this blog.

    He was entirely right. This post truly made my day.
    You can not imagine simply how much time I had spent for this information!
    Thanks!

  41. Does your site have a contact page? I’m having problems locating it
    but, I’d like to shoot you an email. I’ve got some recommendations for your blog you might be interested in hearing.
    Either way, great website and I look forward to seeing it
    grow over time.

  42. Hmm it appears like your website ate my first comment (it was super long) so I guess
    I’ll just sum it up what I submitted and say, I’m
    thoroughly enjoying your blog. I too am an aspiring blog writer but I’m still new to everything.

    Do you have any suggestions for rookie blog
    writers? I’d certainly appreciate it.

  43. Hi! This is kind of off topic but I need some advice from an established blog.
    Is it very hard to set up your own blog? I’m not very
    techincal but I can figure things out pretty fast. I’m thinking about
    creating my own but I’m not sure where to start.
    Do you have any ideas or suggestions? Cheers

  44. I’m curious to find out what blog platform you happen to
    be using? I’m experiencing some small security problems with my latest site and I’d like to
    find something more safeguarded. Do you have any recommendations?

  45. I truly love your website.. Pleasant colors & theme. Did
    you create this site yourself? Please reply back as I’m looking to create my own site and would love to
    find out where you got this from or what the theme
    is named. Thank you!

  46. each time i used to read smaller posts that as well clear their motive, and that is also happening with this
    piece of writing which I am reading at this place.

  47. Oh my goodness! Impressive article dude! Many thanks,
    However I am going through difficulties with your RSS.
    I don’t know why I am unable to subscribe to it. Is there anyone else having identical RSS problems?
    Anyone that knows the solution will you kindly respond? Thanks!!

  48. I’ve been browsing on-line more than three hours these days,
    yet I by no means found any attention-grabbing article like yours.
    It’s lovely value sufficient for me. In my view, if
    all site owners and bloggers made good content as you probably did,
    the web shall be a lot more useful than ever before.

  49. Fantastic blog! Do you have any suggestions for aspiring writers?

    I’m hoping to start my own site soon but I’m a little lost on everything.
    Would you suggest starting with a free platform like WordPress or go for a
    paid option? There are so many choices out there that I’m completely overwhelmed ..
    Any suggestions? Thanks!

  50. Hello! Do you use Twitter? I’d like to follow you if that would be okay.
    I’m undoubtedly enjoying your blog and look forward to new posts.

  51. Good day! I just wish to give you a big thumbs up for
    the great information you have got here on this post.
    I’ll be coming back to your website for more soon.

  52. Mersin eşya depolama olarak eşyalarınızı kendi firmalarımıza ait bakımlı kontrollü depolarımızda muhafaza ediyoruz hem yer sorununu hallediyor hem de uygun bekle firmalarımız sizlere bu imkanları sunuyor. Mersin ev eşyası depolama için anında farklı kuruluşlardan farklı fiyat alın.

  53. Appreciating the hard work you put into your blog and in depth information you present. It’s nice to come across a blog every once in a while that isn’t the same old rehashed material. Great read! I’ve bookmarked your site and I’m including your RSS feeds to my Google account.

  54. Hi there just wanted to give you a brief heads up and let youknow a few of the images aren’t loading properly.I’m not sure why but I think its a linking issue. I’ve tried it in two different browsers and both showthe same results.

  55. Helpful information. Lucky me I discovered your website accidentally, and I am stunned why this twist of fate didn’t happened in advance! I bookmarked it.

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

  57. hello!,I like your writing very much! share we keep up a correspondence more approximately your post on AOL? I need an expert on this space to solve my problem. May be that is you! Taking a look forward to look you. |

  58. My partner and I stumbled over here from a different web page and thought I might as well check things out. I like what I see so now i am following you. Look forward to looking over your web page again.|

  59. Ankara küçük nakliyat hizmeti Ankara gibi büyük şehirler de oldukça önemli bir yere sahiptir. Şehir içi ve şehirler arası küçük çaplı eşya taşımacılığı anlamına gelen ve birçok kişi veya kurum tarafından icra edilmektedir. Burada en önemli olan uygun fiyat ve hızlı çözümdür. Bunun içinde en ideal çözüm bünyemizde yer alan Ankara küçük nakliye ihtiyaçlarınıza doğru çözümler sunan firmalarımızdan alabilirsiniz.

  60. Generally I don’t read article on blogs, but I would like to say that this write-up very compelled me to check out and do it! Your writing taste has been amazed me. Thanks, quite nice post.|

  61. I really like your blog.. very nice colors & theme. Did you design this website yourself or did you hire someone to do it for you? Plz reply as I’m looking to construct my own blog and would like to know where u got this from. many thanks|

  62. After exploring a few of the blog articles on your blog, I truly like your way of writing a blog. I saved as a favorite it to my bookmark site list and will be checking back in the near future. Take a look at my website too and let me know how you feel.|

  63. Wonderful blog! Do you have any helpful hints for aspiring writers? I’m hoping to start my own site soon but I’m a little lost on everything. Would you propose starting with a free platform like WordPress or go for a paid option? There are so many options out there that I’m completely overwhelmed .. Any recommendations? Appreciate it!|

  64. I like the valuable info you provide in your articles. I’ll bookmark your weblog and check again here frequently. I’m quite sure I will learn many new stuff right here! Best of luck for the next!|

Leave a Reply

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