【BZOJ 3990】[SDOI2015] 排序

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3990
神犇题解:http://blog.csdn.net/regina8023/article/details/45503151

解题报告

最开始一眼看成神题,还在想$SDOI$这是要赶超$ZJOI$的节奏啊
然后就发现看漏条件了 _(:з」∠)_

因为每一次只能交换一个$2^k$的块,并且$2$的不同次幂之间不会相互影响
话一句话来说,考虑交换长度为$2^k$的块时,所有长度为$2^{k-1}$的块的顺序必须已经排好
且长度为$2^k$的块,只能有至多两块位置不对
于是我们搞一发$DFS$就好了,时间复杂度:$O(n \log n)$

2 thoughts to “【BZOJ 3990】[SDOI2015] 排序”

  1. Hello! Do you know if they make any plugins to assist with Search Engine Optimization? I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good results. If you know of any please share. Cheers!

  2. I think this is one of the most important info for me. And i’m glad reading your article. But want to remark on few general things, The website style is ideal, the articles is really great : D. Good job, cheers

Leave a Reply

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