【BZOJ 4607】[PA2015 Final] Edycja

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4607
神犇题解Ⅰ：http://www.cnblogs.com/clrs97/p/5545772.html
神犇题解Ⅱ：http://blog.csdn.net/jzhang1/article/details/51697706

前言

这题大概放了三个月了
每一次清理题目的时候都会翻出这个题
然后看一两个小时又扔回去，因为不会啊

解题报告

就是先有一个结论：一号操作最后做不会使答案变劣
然后还有一个结论：对于每一种字符，至多进行一次二号操作
这两个似乎比较显然，想一想都能想出来

有了这两个结论之后我们就可以得到一个贪心的策略：

定义$tra(x,y)$为所有最开始为$x$的位置在目标串中不为$y$的个数
对于每一种字符$c$我们，我们找到字符$g_c$（$g_c$可能等于$c$）
满足$g_c$能使$tra(c,g_c)$最小

考虑将26个字符看成26个点，把$g_c$看作由$c$连向$g_c$的一条边，这显然是一个图
如果这个图上不存环，那么此时已经是最优解。

但如果有环，则你不能找到一种合法的交换顺序，这是不合法的
另外，需要注意，如果一个连通块是一个内向树，则我们是可以多花费一次二号操作的代价使其合法的
比如下面这个图，我们可以先将$a$移动到$e$，然后移动环上的其他字符，最后把$e$移到$a$：

刚刚有说，如果有环，那么环是不合法的，于是我们需要调整一些出边，来破坏掉环
这里又有一个结论：我们破坏环的过程不会产生新的环，这个看起来非常显然，详细证明可以找Claris
至于破坏掉环的过程非常复杂，不能贪心，但我们注意到环的个数最多为13，所以我们可以用状压DP来做
于是这题嘴巴上就做完了！但感觉细节非常多的样子，于是就不写代码了（逃