自动搬运

查看原文

来自洛谷，原作者为

	PosVII OI(2021.3-2025.3)

搬运于2025-08-24 21:23:54，当前版本为作者最后更新于2021-11-26 13:29:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

本题解曾是最高赞题解，最近将网盘的链接更新了，请审核通过。

希望严查本题抄题解情况，其中 uid362162 的题解甚至没有给出全部思路，而他的 AC 代码与最优解后排的几位完全重复，或者说，他所谓的优化是通过打表过题？

耗时 $4$ 天，用时 $6$ 小时 AC，谨以此记录我和我小号获得的两个最优解。

我的代码及答案 云盘，出于私心我不会把我用一晚上调出来的 $7-10$ 代码给出，但测试点思路及代码使用方法会在正文给出。

Case 1-7:

文件夹中的 TrainRead-I 的文件可以通过输入文件并将其可视化处理。

而 TrainChange-I 可以将输入文件处理成纯数字输入，每一个 TrainCode 文件的使用都需要先运行它。

Case 1-2:

我们不难发现，数据非常的小，体现在选择跳转操作次数极小，可以打 $O(2^n)$ 的暴力 AC。

Case 3:

这个点其实有着和 C1，C2 同样的性质，即它可以分成一段一段的，每一个段都会让你做几个选择改变一些变量，而最后答案加上变量的绝对值后所有变量清零。发现每一个段内的选择跳转次数同样很小，那么我们只需要针对每一个段爆搜寻找最大值并输出即可。

Case 4:

$m=2$，意味着仅有一个变量需要讨论，我们发现，该变量在整个数据中增加的次数仅有一，再看就发现这实际上就是一个输出序列的背包，数据中可以分成均匀的段模拟一个物品，不难实现。

Case 5-6:

我们只是片面的看 C4，但是 C5，C6 却又多出了两个问题，第一个是跳转不再均匀，如果不满足条件可能会跳到任意地方，这个可以通过更改背包实现方法做到，但此时又出现了一些无意义的条件跳转，它使得数据不均匀，可以通过把分段背包改成对每一个操作进行的背包解决，不过这真的很慢。

Case 7-10：

上次讲到数据中会出现无意义跳转，而放在本文段的数据上直接处理很麻烦，所以我又打了个代码把那些无意义跳转处理掉。

TrainChange-II 就是在 TrainChange-I 的基础上去掉无意义跳转，而TrainRead-II 就是将此时的数据可视化处理。

其实这四个数据大体相同，那么我就合在一起讲。这四个点都有着 C6 的特征，但其中其它的变量明显增加，而它们的具体结构和 C3 很相似，那么只需要将两代码结合即可，但是要注意一点，它的数据在这次富有变化，所以不能直接照搬前面数据的性质敲代码。

结尾

很好的找规律的码力题，下次不许再出了。