P1335 [NOI2013] 小Q的修炼 题解

· · 题解

前言

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

希望严查本题抄题解情况，其中 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:

**Case 5-6:** 我们只是片面的看 C4，但是 C5，C6 却又多出了两个问题，第一个是跳转不再均匀，如果不满足条件可能会跳到任意地方，这个可以通过更改背包实现方法做到，但此时又出现了一些无意义的条件跳转，它使得数据不均匀，可以通过把分段背包改成对每一个操作进行的背包解决，不过这真的很慢。 # Case 7-10： 上次讲到数据中会出现无意义跳转，而放在本文段的数据上直接处理很麻烦，所以我又打了个代码把那些无意义跳转处理掉。 TrainChange-II 就是在 TrainChange-I 的基础上去掉无意义跳转，而TrainRead-II 就是将此时的数据可视化处理。 其实这四个数据大体相同，那么我就合在一起讲。这四个点都有着 C6 的特征，但其中其它的变量明显增加，而它们的具体结构和 C3 很相似，那么只需要将两代码结合即可，但是要注意一点，它的数据在这次富有变化，所以不能直接照搬前面数据的性质敲代码。 **结尾** ------------ 很好的找规律的码力题，下次不许再出了。