【日常小测】航海舰队

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_day1-statements.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_day1-solutions.pdf

解题报告

之前在BZOJ上看过这道题,然后当时嫌麻烦没有写
今天刚好考到,然后就被细节给搞死了_(:з」∠)_

一句话题解就是:用FFT做矩阵匹配
详细一点的话,大概就是:

先用FFT做一遍0/1矩阵匹配,求出能放阵型的位置
然后BFS出能到达的位置
最后再做一遍FFT求出每个点被覆盖了多少次

Code

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

const int N = 709;
const int M = 5000000;
const double EPS = 0.5;
const double PI = acos(-1);

char mp[N][N];
int n, m, vis[M], sfe[M];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
CP a[M], b[M], c[M];

inline void FFT(CP *arr, int len, int ty) {
	static int pos[M], init = 0;
	if (init != len) {
		for (int i = 1; i < len; ++i) {
			pos[i] = (pos[i >> 1] >> 1) | ((i & 1)? (len >> 1): 0); 
		}
		init = len;
	}
	for (int i = 0; i < len; i++) {
		if (pos[i] < i) {
			swap(arr[i], arr[pos[i]]);
		}
	}
	for (int i = 1; i < len; i <<= 1) {
		CP wn(cos(PI / i), sin(PI / i) * ty);
		for (int j = 0; j < len; j += i + i) {
			CP w(1, 0);
			for (int k = 0; k < i; k++, w *= wn) {
				CP tmp = arr[j + i + k] * w;
				arr[j + i + k] = arr[j + k] - tmp;
				arr[j + k] = arr[j + k] + tmp;
			}
		}
	}
	if (ty == -1) {
		for (int i = 0; i < len; i++) {
			arr[i] /= len;
		}
	}
}

inline void BFS(int sx, int sy, int lx, int ly) {
	vis[sy * n + sx] = 1;
	queue<pair<int, int> > que;
	for (que.push(make_pair(sx, sy)); !que.empty(); que.pop()) {
		int x = que.front().first;
		int y = que.front().second;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx + lx - 1 < n && 0 <= ny && ny + ly - 1 < m && sfe[ny * n + nx] && !vis[ny * n + nx]) {
				que.push(make_pair(nx, ny));
				vis[ny * n + nx] = 1;
			}
		}
	}
} 

int main() {
	freopen("sailing.in", "r", stdin);
	freopen("sailing.out", "w", stdout);
	cin >> m >> n;
	int mnx = n, mny = m, mxx = 0, mxy = 0; 
	for (int j = 0; j < m; j++) {
		scanf("%s", mp[j]);
		for (int i = 0; i < n; i++) {
			if (mp[j][i] == 'o') {
				mnx = min(i, mnx);
				mxx = max(i, mxx);
				mny = min(j, mny);
				mxy = max(j, mxy);
			}
		}
	}
	for (int j = 0; j < m; ++j) {
		for (int i = 0; i < n; ++i) {
			if (mp[j][i] == 'o') {
				b[(j - mny) * n + i - mnx] = CP(1, 0);
			} else if (mp[j][i] == '#') {
				a[j * n + i] = CP(1, 0);
			}
		}
	}
	int cur = n * m, len = 1;
	for (; len < cur * 2; len <<= 1);
	for (int l = 0, r = cur - 1; l < r; ++l, --r) {
		swap(b[l], b[r]);
	}
	FFT(a, len, 1);
	FFT(b, len, 1);
	for (int i = 0; i < len; i++) {
		a[i] *= b[i];
	}
	FFT(a, len, -1);
	for (int i = 0; i < cur; i++) {
		if (a[i + cur - 1].real() < EPS) {
			sfe[i] = 1;
		}
	}
	BFS(mnx, mny, mxx - mnx + 1, mxy - mny + 1); 
	memset(b, 0, sizeof(b));
	for (int j = 0; j < m; j++) {
		for (int i = 0; i < n; i++) {
			c[j * n + i] = vis[j * n + i]? CP(1, 0): CP(0, 0);
			b[(j - mny) * n + i - mnx] = mp[j][i] == 'o'? CP(1, 0): CP(0, 0);
		}
	}
	FFT(c, len, 1);
	FFT(b, len, 1);
	for (int i = 0; i < len; i++) {
		c[i] *= b[i];
	}
	FFT(c, len, -1);
	int ans = 0;
	for (int i = 0; i < cur; i++) {
		ans += c[i].real() > EPS; 
	}
	printf("%d\n", ans);
	return 0;
}

—————————— UPD 2017.6.30 ——————————
B站题号:4624

279 thoughts to “【日常小测】航海舰队”

  1. Howdy are using WordPress for your site platform? I’m new to the blog world but I’m trying to get started and create my
    own. Do you need any coding expertise to make your own blog?
    Any help would be greatly appreciated!

  2. Nice post. I was checking continuously this blog and I am impressed!
    Extremely useful information particularly the last part :
    ) I care for such information a lot. I was seeking this particular info
    for a long time. Thank you and good luck.

  3. I’m really loving the theme/design of your website.

    Do you ever run into any browser compatibility problems?
    A few of my blog readers have complained about my website
    not operating correctly in Explorer but looks great in Opera.
    Do you have any suggestions to help fix this problem?

  4. Hey there just wanted to give you a brief heads up and let you know 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
    internet browsers and both show the same results.

  5. Wonderful goods from you, man. I’ve understand your stuff previous to and you are just extremely fantastic.
    I really like what you have acquired here, certainly like what you’re stating
    and the way in which you say it. You make it enjoyable and you still care for to keep it smart.
    I can’t wait to read much more from you. This is really a terrific web site.

  6. Hi! I know this is kinda off topic but I was wondering which blog platform
    are you using for this website? I’m getting fed up of WordPress because I’ve had
    problems with hackers and I’m looking at alternatives for another platform.
    I would be fantastic if you could point me in the direction of a good platform.

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

  8. A person essentially assist to make seriously articles
    I might state. That is the very first time I frequented your website page and to this point?
    I amazed with the analysis you made to create this particular put up amazing.
    Excellent task!

  9. Greetings! I know this is kinda off topic however I’d figured I’d ask.

    Would you be interested in trading links or maybe guest authoring a blog article
    or vice-versa? My website addresses a lot of the same topics as yours and I
    think we could greatly benefit from each other.
    If you are interested feel free to shoot me an email. I look forward to hearing from you!
    Fantastic blog by the way!

  10. Every weekend i used to pay a visit this web page, as i
    wish for enjoyment, for the reason that this this web page conations actually pleasant funny material too.
    natalielise pof

  11. It is the best time to make some plans for the
    future and it is time to be happy. I have read this post and if I could
    I wish to suggest you some interesting things or suggestions.

    Maybe you can write next articles referring to this article.
    I desire to read more things about it!

  12. Hi there! This post couldn’t be written any better! Reading through this post reminds me of my previous room mate!
    He always kept talking about this. I will forward this article to him.
    Pretty sure he will have a good read. Thank you
    for sharing!

  13. Hi there I am so grateful I found your web site, I really found you by error, while I was browsing
    on Google for something else, Anyways I am here now and would just like to say
    many thanks for a incredible post and a all round thrilling blog (I
    also love the theme/design), I don’t have time to look over it all at the moment but I have bookmarked it and
    also added in your RSS feeds, so when I have time I will be
    back to read much more, Please do keep up the superb work.
    plenty of fish natalielise

  14. Its like you read my thoughts! You appear to understand a lot
    approximately this, such as you wrote the e book in it or something.
    I feel that you could do with a few % to
    force the message house a bit, however instead of that, this is magnificent blog.
    A great read. I will definitely be back.

  15. Have you ever considered about adding a little bit more than just your articles?
    I mean, what you say is valuable and everything.

    But imagine if you added some great pictures or video clips to give your
    posts more, “pop”! Your content is excellent but with
    images and videos, this blog could undeniably be one of the most beneficial in its field.

    Good blog!

  16. Hi! This post couldn’t be written any better!
    Reading through this post reminds me of my previous room mate!
    He always kept chatting about this. I will forward this write-up to him.
    Pretty sure he will have a good read. Thanks
    for sharing!

  17. I just could not go away your website before suggesting that I really enjoyed
    the standard info a person provide in your visitors?
    Is going to be again steadily in order to investigate cross-check new posts

  18. Awesome website you have here but I was wondering
    if you knew of any user discussion forums that cover the same topics
    discussed here? I’d really love to be a part of group where I can get responses from
    other knowledgeable people that share the same interest.
    If you have any recommendations, please let me know. Kudos!

  19. I do believe all the concepts you’ve offered for your post.
    They are really convincing and will certainly work.
    Nonetheless, the posts are too brief for newbies.

    Could you please prolong them a bit from next time?
    Thank you for the post.

  20. Hey there just wanted to give you a quick heads up.
    The text in your content seem to be running off the screen in Opera.
    I’m not sure if this is a format issue or something to do with web browser compatibility but
    I figured I’d post to let you know. The layout look great though!
    Hope you get the problem fixed soon. Kudos

  21. Hello, I do believe your website may be having internet browser compatibility
    problems. Whenever I look at your site in Safari, it looks
    fine however when opening in I.E., it has some overlapping issues.
    I simply wanted to give you a quick heads up!
    Besides that, wonderful site!

  22. Its like you read my mind! You seem to know a lot about this, like
    you wrote the book in it or something. I think that you could do with a few pics
    to drive the message home a little bit, but other than that, this
    is excellent blog. A great read. I will definitely be back.

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

  24. Hello there! I could have sworn I’ve visited your blog before
    but after going through many of the articles I realized it’s new to me.
    Anyways, I’m definitely delighted I came across it and
    I’ll be book-marking it and checking back frequently!

  25. You’re so awesome! I don’t think I’ve read through anything like that before.
    So nice to discover somebody with a few genuine thoughts on this topic.

    Really.. thanks for starting this up. This web site is something that is required on the web, someone with a bit
    of originality!

  26. Hi there! I just wanted to ask if you ever have any
    problems with hackers? My last blog (wordpress) was hacked
    and I ended up losing a few months of hard work due to no data backup.
    Do you have any solutions to prevent hackers?

  27. Woah! I’m really enjoying the template/theme of this site.
    It’s simple, yet effective. A lot of times it’s hard to get that “perfect balance” between user friendliness
    and visual appearance. I must say you have
    done a very good job with this. Additionally,
    the blog loads extremely quick for me on Chrome. Outstanding Blog!

  28. Simply want to say your article is as amazing. The clearness in your post is simply cool and i could assume
    you are an expert on this subject. Fine with your permission let me to grab your feed to keep updated with forthcoming post.
    Thanks a million and please continue the gratifying work.

  29. I like the valuable info you provide in your articles.
    I will bookmark your weblog and check again here regularly.

    I am quite certain I’ll learn many new stuff right here!

    Best of luck for the next!

  30. I was curious if you ever considered changing the structure of your
    blog? 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 1 or
    2 images. Maybe you could space it out better?

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

  32. It’s fantastic that you are getting thoughts from this piece of writing as well as from our discussion made at this place.

  33. Today, I went to the beachfront with my children. I found a sea shell and gave it to
    my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed.
    There was a hermit crab inside and it pinched her ear. She never wants to go back!

    LoL I know this is entirely off topic but I had to tell someone!

  34. Excellent blog! Do you have any tips and hints for aspiring writers?
    I’m planning to start my own website 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 confused ..
    Any tips? Kudos!

  35. If some one desires expert view concerning running a blog after that
    i recommend him/her to pay a visit this blog, Keep up
    the fastidious job.

  36. Excellent blog here! Additionally your site a lot up very fast!
    What web host are you using? Can I get your affiliate hyperlink to your host?
    I wish my site loaded up as fast as yours lol

  37. I have been browsing online greater than 3 hours lately, yet I by no means found any attention-grabbing article like yours.
    It is pretty worth sufficient for me. In my view, if all site owners and
    bloggers made good content material as you probably did, the internet will be
    much more useful than ever before.

  38. Just desire to say your article is as surprising. The clearness in your post is simply cool 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 continue the gratifying work.

  39. I will immediately grab your rss as I can not in finding your e-mail subscription link or e-newsletter service.
    Do you’ve any? Kindly allow me recognize so that I may just subscribe.
    Thanks.

  40. My family members every time say that I am wasting my time here at net, but I know I
    am getting knowledge daily by reading such good articles or reviews.

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

  42. Thanks , I have recently been searching for
    information about this topic for a long time and yours is the greatest I have came upon till now.

    But, what concerning the bottom line? Are you sure concerning the supply?

  43. 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!

  44. I think this is one of the most important information for me.
    And i am glad reading your article. But should remark on some general things, The
    site style is ideal, the articles is really great : D. Good job, cheers

  45. hey there and thank you for your info – I have certainly picked up anything
    new from right here. I did however expertise some technical points using this web site, since I experienced to reload the website
    lots of times previous to I could get it to load correctly.
    I had been wondering if your hosting is OK? Not that I am complaining, but slow loading instances times will often affect
    your placement in google and could damage your quality score
    if ads and marketing with Adwords. Anyway I am adding this RSS to my email and can look out for a lot more of your respective intriguing content.
    Ensure that you update this again very soon.

  46. Hello! Someone in my Myspace group shared this website with
    us so I came to look it over. I’m definitely loving the information. I’m book-marking and will be tweeting this to my followers!
    Excellent blog and terrific design.

  47. I’d like to thank you for the efforts you’ve put in writing this
    blog. I’m hoping to see the same high-grade blog posts by you later on as well.

    In truth, your creative writing abilities has inspired me to get
    my own blog now 😉

  48. When I originally commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is added I get four e-mails
    with the same comment. Is there any way you can remove people from that service?

    Thanks a lot!

  49. Hi this is kind of of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually code with HTML.
    I’m starting a blog soon but have no coding expertise so I
    wanted to get guidance from someone with experience.

    Any help would be enormously appreciated!

  50. Aw, this was an extremely nice post. Finding the time and actual effort to generate a good
    article… but what can I say… I procrastinate a whole lot and
    don’t manage to get anything done.

  51. Undeniably consider that that you stated. Your favourite justification appeared to be on the internet
    the simplest thing to take into accout of. I say to you, I definitely get annoyed even as other folks consider concerns that they plainly do not recognize about.

    You managed to hit the nail upon the highest and also defined out the entire thing with no need
    side-effects , folks can take a signal. Will likely be again to
    get more. Thanks

  52. Greetings from Carolina! I’m bored at work so I decided to browse your site on my iphone during lunch break.
    I enjoy the knowledge you provide here and can’t wait to take a look when I get home.
    I’m amazed at how quick your blog loaded on my phone .. I’m not even using WIFI,
    just 3G .. Anyways, awesome site!

  53. This is really interesting, You’re a very skilled blogger. I’ve joined your rss feed and look forward to seeking more of your wonderful post. Also, I have shared your site in my social networks!

  54. 629508 199159Our own chaga mushroom comes with a schokohutige, consistent, charcoal-like arrival, a whole lot of dissimilar to the style of the standard mushroom. Chaga Tincture 253913

  55. I wanted to thank you for this good read!!

    I absolutely loved every little bit of it. I have you saved as a favorite to look at new things you post…

  56. Hi there! Do you use Twitter? I’d like to follow you if that would
    be ok. I’m absolutely enjoying your blog and look forward to new updates.

  57. Thank you for another informative blog. Where else could I get that type of information written in such an ideal way? I’ve a project that I’m just now working on, and I’ve been on the look out for such information.

  58. Can I simply just say what a relief to discover somebody
    that actually understands what they are discussing on the net.
    You certainly understand how to bring an issue to light and
    make it important. A lot more people ought to check this out and understand this side of the story.
    I was surprised that you’re not more popular given that you certainly have the
    gift.

发表评论

电子邮件地址不会被公开。 必填项已用*标注