自动搬运

查看原文

来自洛谷，原作者为

	fangzichang 1-96 | 私立海亮高等学校 情報部門 芳賀織乃

搬运于2025-08-24 22:14:19，当前版本为作者最后更新于2024-05-29 20:02:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

写了同一场的 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 上这题时限两秒，洛谷上是三秒，卡时的话需要注意。