相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2437
神犇题解：http://blog.csdn.net/qpswwww/article/details/45368587
解题报告
我们先将整个棋盘黑白染色，将空格棋子所在方格的颜色分类
在可相互转化的状态之间连边，那么这就是一张二分图了
那么原题的问题转换为：
给定一张二分图，每次沿边移动一次
每个点只能到达一次，最后谁不能动谁就输了
询问每一个点作为起点时是否先手必胜
考虑一个点如果在任意一种最大匹配当中，那么先手每一次走匹配边，则后手必败
换一句话来说，如果一个点一定在最大匹配当中，那么这个点是先手必胜的
再考虑一下，如果一个点不一定在最大匹配当中，那么删掉这个点之后存在最大匹配，那后手走到那个点去就可以了！
再换一句话来说，如果一个点不一定在最大匹配中，那么这个点先手必败
现在我们只需要求出一个点是否在最大匹配中就可以了！
我们可以枚举这个点，将其删掉后跑最大匹配验证，但复杂度是$O(n^4)$的
或者我们可以用今年冬令营的那个一般图匹配的算法来做，时间复杂度是$O(n^3)$的
不过我们可以又一个常数更小的算法
我们可以先求出一个最大匹配，然后假设当点在点$a$
将其删掉后，看$a$的匹配点$b$还能不能匹配即可
吐槽
博弈题居然还能这么玩！
真的是长见识了 _(:з」∠)_
不过代码好难写啊，不想写代码 ┑(￣Д ￣)┍
Major thanks for the article.Thanks Again. Really Cool.
I appreciate you sharing this article. Keep writing.
I cannot thank you enough for the post.Really thank you! Will read on…
Fantastic article post.Really looking forward to read more. Want more.
I cannot thank you enough for the blog post. Want more.
Wow, great blog article.Much thanks again. Want more.
I truly appreciate this blog post.Much thanks again. Awesome.
Muchos Gracias for your article post.Thanks Again. Great.
I am so grateful for your post. Keep writing.
Im obliged for the article post.Really thank you! Much obliged.
Really enjoyed this blog.Really looking forward to read more. Really Great.
Great blog article.Really looking forward to read more. Keep writing.
Really enjoyed this article.Much thanks again. Really Great.
I loved your article. Really Cool.
Thanks again for the blog.Much thanks again.
Very neat blog post. Great.
I value the article post. Will read on…
Thanks so much for the blog article. Really Cool.
Thanks so much for the blog.Much thanks again. Want more.
I really liked your blog.Really thank you! Fantastic.
Great blog post.Much thanks again. Will read on…
I truly appreciate this blog post.Much thanks again.
Thank you ever so for you blog post.Really thank you! Want more.
Muchos Gracias for your article.Thanks Again. Really Cool.
Great, thanks for sharing this blog post.Really looking forward to read more. Fantastic.
I truly appreciate this post.Thanks Again. Great.
I cannot thank you enough for the blog.Really looking forward to read more. Will read on…
Very good article.Really thank you! Great.
Awesome blog.Really thank you! Keep writing.
Thanks a lot for the article.Really looking forward to read more. Keep writing.
Looking forward to reading more. Great post.Thanks Again. Fantastic.
Really informative post.Much thanks again. Cool.
Enjoyed every bit of your blog article.Really thank you! Will read on…
Very good post. Will read on…
I really liked your blog post.Much thanks again. Cool.
Very good blog article.Really thank you! Much obliged.
Very informative article post.Really thank you! Really Cool.
Awesome blog article. Great.
Muchos Gracias for your blog article.Much thanks again. Much obliged.
I really liked your article. Really Great.
I really liked your article.Really thank you! Really Cool.
wow, awesome article post.Much thanks again. Cool.
I think this is a real great blog post. Really Great.
A round of applause for your blog post.Much thanks again. Keep writing.
I truly appreciate this article post.Really looking forward to read more. Really Cool.
Very neat article.Thanks Again. Cool.
A round of applause for your post.Really looking forward to read more. Much obliged.
Very neat blog post.Really thank you! Really Great.
I loved your article.Really thank you! Keep writing.
Really enjoyed this post. Want more.
Im obliged for the blog post.Thanks Again. Want more.
I loved your blog.Really thank you! Want more.
Looking forward to reading more. Great article.Really thank you! Cool.
Say, you got a nice article post.Really looking forward to read more. Cool.
I appreciate you sharing this blog article.Much thanks again. Awesome.
Very informative article. Awesome.
Thanks for sharing, this is a fantastic article post.Thanks Again. Fantastic.
I really enjoy the blog.Much thanks again. Really Cool.
I loved your blog. Really Great.
Major thanks for the post. Fantastic.
Great blog.Really looking forward to read more. Really Cool.
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 emails with the same comment. Is there any way you can remove me from that service? Thanks!
Major thankies for the blog post.Thanks Again. Really Great.
Enjoyed every bit of your blog article.Much thanks again. Fantastic.
I really enjoy the blog post. Keep writing.
Fantastic article post.Really looking forward to read more.
Thanks again for the blog.Really looking forward to read more. Fantastic.
I really liked your blog.Really thank you! Cool.
I value the blog article.Really thank you! Really Cool.
This is one awesome post.Really thank you! Awesome.
I am so grateful for your blog.Much thanks again. Really Great.
This is one awesome article post.Really thank you! Much obliged.
Say, you got a nice blog post.Much thanks again. Want more.
I value the blog article. Really Cool.
Wow, great post.Really looking forward to read more. Much obliged.
Muchos Gracias for your blog.Thanks Again. Cool.
I am so grateful for your article post.Really looking forward to read more. Keep writing.
Im thankful for the article.Really looking forward to read more. Want more.
Thanks a lot for the blog article.Much thanks again. Fantastic.
Very neat blog article.Really looking forward to read more. Great.
I really like and appreciate your article post.Really thank you! Cool.
Very informative article post.Really thank you! Will read on…
I really enjoy the blog.Really thank you! Keep writing.
A round of applause for your article.Thanks Again. Want more.
Im grateful for the blog post. Really Cool.
Thanks so much for the blog.Really thank you! Fantastic.
Very informative blog article.Really thank you! Really Cool.
Thanks again for the article post. Fantastic.
Hey, thanks for the blog article.Really thank you! Really Cool.
I really liked your article post.Really thank you! Much obliged.
wow, awesome blog post.Really thank you! Cool.
Thanks for the article.Really looking forward to read more. Fantastic.
Thanks for sharing, this is a fantastic article post.Really looking forward to read more. Much obliged.
Major thanks for the blog post.Much thanks again. Much obliged.
Thanks a lot for the post.Really thank you! Much obliged.
Thank you for your article post.Really looking forward to read more. Awesome.
Very good blog.Much thanks again. Cool.
I really liked your blog post.Much thanks again. Keep writing.
Thanks again for the blog post. Awesome.
Thanks for the article post.Thanks Again. Really Cool.
I really liked your blog post.Much thanks again. Fantastic.
Im grateful for the post.Much thanks again.
Im grateful for the post.Really looking forward to read more. Keep writing.
Very neat blog.
Thank you ever so for you article post.Really thank you! Will read on…
Great blog. Really Cool.
Thanks again for the blog article.Thanks Again. Much obliged.
I cannot thank you enough for the article post.Really looking forward to read more. Will read on…
I cannot thank you enough for the article post. Fantastic.
wow, awesome article.Much thanks again.
I loved your article.Really thank you! Much obliged.
Thanks-a-mundo for the blog article.Really thank you!
Fantastic post. Really Great.
Really appreciate you sharing this blog article.Much thanks again. Fantastic.
Thanks so much for the article. Want more.
I truly appreciate this article post.Really thank you! Much obliged.
Great, thanks for sharing this post.Really looking forward to read more. Fantastic.
Really enjoyed this blog.Thanks Again. Cool.
Really informative blog post.Much thanks again. Keep writing.
Really appreciate you sharing this blog post. Much obliged.
I appreciate you sharing this post.Much thanks again. Awesome.
Thank you ever so for you post.Really looking forward to read more. Great.
Thanks again for the article post.Really thank you! Really Cool.
I cannot thank you enough for the article post. Much obliged.
I really liked your post.Thanks Again. Want more.
I really enjoy the blog article.Really thank you! Fantastic.
Very good post.Much thanks again. Fantastic.
Really informative article post.Much thanks again. Great.
Thanks for sharing, this is a fantastic post.Thanks Again.
Hey, thanks for the blog article.Really thank you! Great.
Very neat blog article.Much thanks again. Fantastic.
Looking forward to reading more. Great blog.Much thanks again. Want more.
Hey, thanks for the article post.Much thanks again.
Appreciate you sharing, great blog article.Really looking forward to read more. Much obliged.
Great article. Keep writing.
I really enjoy the blog post.Thanks Again. Much obliged.
Really appreciate you sharing this article post.Much thanks again. Much obliged.
Thank you for your blog article.Much thanks again.
Really enjoyed this blog post.Really looking forward to read more. Great.
Thanks so much for the article.Thanks Again. Want more.
Looking forward to reading more. Great post.Much thanks again. Keep writing.
I am so grateful for your article. Want more.
Awesome blog.Thanks Again.
A big thank you for your blog article.Really thank you! Will read on…
Thank you for your blog post.Really looking forward to read more. Awesome.
I truly appreciate this post.Thanks Again.
Looking forward to reading more. Great blog.Really looking forward to read more. Fantastic.
I really enjoy the article.Thanks Again. Really Cool.
Muchos Gracias for your blog.Really looking forward to read more. Cool.
Fantastic blog post.Much thanks again. Great.
Major thanks for the blog post. Keep writing.
Great, thanks for sharing this blog post.Really thank you! Much obliged.
I am so grateful for your article post. Really Cool.
I think this is a real great article.Much thanks again. Want more.
Thank you ever so for you article.Really thank you! Really Cool.
Fantastic article.Much thanks again.
Im grateful for the article.Thanks Again. Will read on…
Thanks again for the article post. Really Great.
Very good blog.Really thank you! Will read on…
Major thankies for the blog.Much thanks again. Cool.
Really appreciate you sharing this blog. Awesome.
I truly appreciate this blog post. Will read on…
Good post and right to the point. I don’t know if this is truly the best place to ask but do you guys have any thoughts on where to get some professional writers? Thx 🙂
I think this is a real great blog article. Cool.
I appreciate you sharing this article post.Thanks Again. Awesome.
Enjoyed every bit of your blog post.Really looking forward to read more. Great.
A round of applause for your article post.
A big thank you for your blog.Much thanks again.
Thanks so much for the blog article.Much thanks again. Keep writing.
I am so grateful for your article post.Really looking forward to read more.
I really like and appreciate your article. Much obliged.
Im thankful for the article.Really thank you! Fantastic.
Thanks a lot for the blog article. Cool.
Thanks a lot for the article post.Really looking forward to read more. Much obliged.
I think this is a real great blog post.Thanks Again. Keep writing.
I cannot thank you enough for the article post.Really thank you! Really Cool.
Really informative blog.Really looking forward to read more. Want more.
Major thankies for the post. Want more.
Looking forward to reading more. Great blog article.Much thanks again. Really Great.
wow, awesome article.Thanks Again. Want more.
This post is actually a nice one it helps new net people, who are wishing for blogging.|
In fact no matter if someone doesn’t understand after that its up to other users that they will assist, so here it happens.|
Really enjoyed this article post.Really looking forward to read more. Really Cool.
Thanks-a-mundo for the blog post.Really thank you! Fantastic.
Awesome issues here. I’m very glad to peer your post. Thank you a lot and I’m having a look forward to touch you. Will you please drop me a mail?|
Awesome post.Really looking forward to read more. Cool.
Really informative blog post.Much thanks again. Really Great.
I have been exploring for a little bit for any high quality articles or weblog posts on this sort of area . Exploring in Yahoo I eventually stumbled upon this web site. Studying this info So i am satisfied to show that I’ve a very good uncanny feeling I found out exactly what I needed. I such a lot without a doubt will make certain to don?t forget this web site and provides it a glance regularly.|
I really like what you guys are usually up too. This type of clever work and reporting! Keep up the awesome works guys I’ve incorporated you guys to my blogroll.|
Fantastic blog.Much thanks again. Cool.
Hey, thanks for the article post.Really looking forward to read more. Cool.
Thank you for every other informative blog. Where else could I am getting that type of info written in such a perfect manner? I have a undertaking that I am just now running on, and I’ve been at the look out for such information.|
I truly appreciate this blog.Really looking forward to read more. Keep writing.
I am so grateful for your blog post.
Thanks a lot for the article post.Really thank you! Really Cool.
Thanks again for the article post.Really thank you! Keep writing.
If you are going for most excellent contents like I do, just go to see this site everyday because it provides quality contents, thanks|
I really like and appreciate your blog.Really looking forward to read more. Fantastic.
wow, awesome blog post.Really thank you! Really Cool.
You really make it seem so easy with your presentation but I find this matter to be really something that I think I would never understand. It seems too complicated and very broad for me. I am looking forward for your next post, I will try to get the hang of it!|
A round of applause for your article post. Will read on…
Really appreciate you sharing this blog.Really thank you! Fantastic.
This article provides clear idea in support of the new people of blogging, that in fact how to do blogging and site-building.|
Thanks a lot for the post.Thanks Again. Much obliged.
Very neat post.Really thank you! Really Great.
I loved your post. Really Cool.
Hello every one, here every one is sharing these kinds of knowledge, thus it’s pleasant to read this web site, and I used to pay a quick visit this web site everyday.|
We stumbled over here from a different website and thought I may as well check things out. I like what I see so now i am following you. Look forward to looking at your web page yet again.|
Thank you for sharing your info. I truly appreciate your efforts and I am waiting for your next post thank you once again.|
Thanks so much for the blog post.Really thank you! Fantastic.
Can you tell us more about this? I’d like to find out some additional information.|
I appreciate you sharing this article.Much thanks again. Awesome.
Thank you for your article.Much thanks again. Will read on…
I cannot thank you enough for the article post.Thanks Again. Really Great.
I like the valuable info you provide on your articles. I’ll bookmark your blog and take a look at once more right here regularly. I am reasonably certain I’ll be told a lot of new stuff right here! Good luck for the following!|
A round of applause for your article.Really looking forward to read more. Awesome.
Im obliged for the blog post.Really thank you! Cool.
Very neat blog.Really thank you! Cool.
I value the blog post.Much thanks again. Want more.
Greetings from Los angeles! I’m bored to death at work so I decided to check out your blog on my iphone during lunch break. I love the information you present here and can’t wait to take a look when I get home. I’m surprised at how fast your blog loaded on my cell phone .. I’m not even using WIFI, just 3G .. Anyhow, awesome blog!|
I value the article post.Thanks Again. Awesome.
Major thankies for the article. Want more.
Amazing! Its really amazing article, I have got much clear idea about from this article.|
This post is worth everyone’s attention. When can I find out more?|