前晚 ABC E 题解
2025-12-15 23:32:59
发布于：广东
36阅读
0回复
0点赞
ABC 依旧蒸蒸日上，前五题有高达三道原题和四道水题。我挑唯一一道不是水题的原题讲。
给定一个 的排列 。你可以对它进行若干次操作，每次操作可以交换 中任意两个元素。记将 排序的最小交换次数为 。求有多少种第一次交换的情况，使得再进行 次交换可以将 排序。
结论：对于一个任意的 的排列 ，如果建一张 个节点的有向图，将 与 连边，则该图一定能分成若干个独立的环。
证明：
显然每个点有且仅有一条出边，且有且仅有一条入边。
考虑从任意一个点开始，沿着它的出边走。显然只有两种情况：
- 走到一个新的点。
- 回到最开始的点。此时形成一个环。
以此类推，该图可分成若干个独立的环。
考虑交换两个数会对环造成什么影响。
假设交换的两个数在一个环内：
显然只可能分裂成两个环。
假设交换的两个数在两个不同的环：
显然只可能合并成一个环。
而除了已经排好序了，不管排列是怎样的，第一种情况一定存在。
而排好序就是 个点各形成自环。
所以我们只需要在两个及以上的点的环内不断进行交换就可以实现排序。根据上面的推理可以证明这是最优情况，且所有最优情况都是这种操作。
所以记第 个环的大小为 ，答案就是 。
时间复杂度：。
Bonus：如果求所有最优解的情况次数呢？
我猜应该和卡特兰数有关。
有帮助，赞一个