P5780 [CTSC2011] 排列 题解

· · 题解

写了同一场的 P5841 之后来写这题，发现阴间程度卧龙凤雏。事后发现大概是我太菜了。

容易把题目的两个限制转化成图论问题：x+A 和 x\times B 在排列中都必须排在 x 前，因此建一张 n 个点的图，x+A 和 x\times B 分别向 x 连边，那么合法的 P 等价于是这张图的一个拓扑序（别忘了判掉 B=1）。
然后观察式子，肉眼可见的是将较小的值放在前面比较优。
注意到评分机制是一个和你的解的优秀程度相关的式子，算出来不是太优也能拿到一些分；n 很小，时限挺大，给了很奇怪的 A 和 B 的值，看起来不太像是一般的题目，大概是要乱搞的。

算法 1：直接用一个优先队列，优先取较小值拓扑排序。得分 28 分左右。
注意到这是一个 O(n\log n) 的算法，对于 n\le 90 的数据明显不合适。考虑引入随机化。
算法 2：为每个值随机一个优先程度权值，按照权值使用优先队列拓扑排序，随机若干次取最优解。顺便发现这个权值和随机一个 1\dots n 的排列是等价的。得分大概 \le 40。
熟悉随机化的朋友们都知道这样随机是非常低效的。
算法 3：考虑爬山算法，每次在原最优解上出发，随机交换两个权值，如果比较优就保留这次交换。得分可以达到 80 左右。
算法 4：容易想到分段爬山，每若干次随机之后，重新随机整个排列重新爬一次。多试几次，调调参就过去了，卡时的话可以少调一个参数，比较方便一点。我设的每次随机交换 10000 对权值，可以稳定通过。
算法 0：注意到测试点 9、10 在数据范围中已经给出，跑不过去的话可以在自己机子上跑充分久然后打表。
我一开始的写法比较垃圾，卡了好久都过不去，上面的写法应该比较容易通过。
代码不建议观看，容易脑溢血。自己写一个很容易的。
总结：比较套路的随机化题，场上写不出来是我太菜了。
附：LOJ 上这题时限两秒，洛谷上是三秒，卡时的话需要注意。