文章/全蓝宝石转换理论

^{编 刷 历}

首页 > 文章 > 文章/全蓝宝石转换理论

---

如果是第一次来，按"Ctrl+D"可以收藏随时查看更新~觉得WIKI好玩的话，请推荐给朋友哦～(◕ω＜)☆
按右上角“WIKI功能→编辑”即可修改页面内容。

本文来自：贴吧
原作者：真魔
原视频/文章地址：https://tieba.baidu.com/p/5871628045

相关魔塔

教程塔ex：蓝宝石转换理论

绪论

众所周知，转换是魔塔里的一项非常重要的基本功。狭义的转换可定义为：通过改变同样的一组操作的顺序，从而提高血量。比如面前有5个怪物，每个怪物守着一些宝石，那么打这5个怪物有120种顺序，找出最优的顺序即是一个转换。广义的转换还包括打不同的怪物，从而产生不同的地形连通结构，来获得更高的血量。

狭义转换例子：冥中手0f，无尽轮回

广义转换例子：简单魔塔难度版

请注意，广义转换的界限不是很清楚，有时候会和大路线规划产生交集。但我们一般不把道具使用也算在转换内。

本文只讨论狭义转换。

如果需要转换的操作数较少，可以直接穷举。但如果操作数很多，就需要加以一定的分析了。但由于转换的具体情况极为复杂，一直没有针对具体如何打好转换的具体理论。

本文的目的在于解决一种较简单的情况：狭义转换，怪物守的只有蓝宝石。

由于你的攻击力确定时，1防御对某怪物的减伤一直是一个定值（直到怪物伤害变为0为止），因此拿蓝宝石的顺序比较好把握。为简化问题，本文不考虑怪物伤害变为0的情况，假设怪物伤害一直为正，也不考虑勇士面临缺血问题的情况，假设勇士血量充分大。以上限制条件称为限制条件E。

怪物合并：

由于我们只需要考虑怪物的减伤，且只有蓝宝石，我们不妨把两个连在一起（中间没有蓝宝石）的怪物视为一个大怪物。设1防对怪物A的减伤为a，对怪物B的减伤为b，则1防对大怪物的减伤为a+b。

星型结构图

进行怪物合并后，所有怪物互不干扰，没有打完一个怪物才能打另一个怪物的情况。这是最简单的情况。

例1：假设勇士接下来要打这几个怪物而且面临限制条件E。那么我们不需要任何其他信息就能知道，无论怎么打最后血量都没有区别。（当然连在一起的怪物得一起打）

例2，满足限制条件E，请问勇士接下来怎么打（请想出答案再往下看）

例3，蓝宝石+1防御，请问勇士接下来怎么打（请想出答案再往下看）

分析：勇士血量显然充足，稍微计算可得+18防后怪物伤害全都不是0（怪物伤害-1防减伤*18即可），因此限制条件E满足。

由定理1易得正确顺序为1652473

八爪鱼结构

假设一组怪物以及其守卫的防御为一个点，勇士所处的位置也是一个点，不同的点之间按连通性连边，则形成一个图。

八爪鱼结构定义为将要打的怪物简化成图后，出了勇士所在的点之外所有的点度数至多为2，而且图中没有圈的结构。很明显，星型结构都是八爪鱼结构。

定义1：对一个点中的所有怪物，假设1防对其减伤a，守卫的防御数值为b，定义这个点的“特征”为a/b。

定义2：对于若干个点，设这些点中的所有怪物的1防减伤之和为a，守卫的防御数值之和为b，定义这个点组的特征为a/b。

根据第二章内容我们有：

定理1（星型定理）：在限制条件E下，一个星型结构中，为获得最优解，只需要按点的特征从小到大开始打就可以了。假如几个点特征相同，那么这几个点可以随便安排顺序。

n=2时我们有

定理2（交换基本定理）：在限制条件E下，A，B为两个点，AB优于BA的等价条件是A的特征<B的特征。

从勇士出发，进入一个点之后若这个点度数为2，则沿另一条边一直前进直到遇到一个度数为1的点位置。这样形成的一串点称为一条链，由于图中没有圈，一个八爪鱼结构必定由若干条互不相交链组成。上图为一个由7条链组成的八爪鱼结构。

定义3：假如在一条链中相邻的两个点，后面（离勇士较远）那个点的特征>=前面那个，称为好点组，反之称为坏点组。

以下讨论均假设限制条件E成立。

定理3（坏点组连续定理）：在最优路线中，对一个坏点组，打了前面那个点后一定是立刻打了后面那个点。

证明：设前面的点A特征为a，后面的点B特征为b，b<a 假设不是这样，在打了A之后又进行操作C，然后打B。

操作C即是打了若干个点，设这些点的特征为c

把操作C中所有怪物放一起，守卫的防御也放一起，假设这些怪物守卫这些防御，形成一个点C‘。易知它的特征也是c。

易知操作C比打C‘的血多，而且多了一个固定值（操作C中的蓝宝石对C中的怪物形成的减伤）。

若c>b，根据交换基本定理，ACB劣于ABC，矛盾。（注意到C不是一个点，不能直接用交换基本定理，但是可以得出AC’B劣于ABC‘，而且C和C’差一个固定值，因此可得）

若c<=b<a，根据交换基本定理，ACB劣于CAB，矛盾。

对于一个坏点组A，B，由于打完A一定打B，我们可以把它看成一个更大的点，AB的所有怪物守卫AB的所有宝石，设为C。易知AB的血量和C的血量差一个固定值，因此这样操作后不影响最优路线的选取。

对一个八爪鱼，不停地这样合并后，一定会出现没有坏点组的情况。这时候的图W我们可以按所有“大点”的特征从小打大开始打，由星型定理知这是最优路线。（假设这时所有点是星型的，称为图W‘，则由星型定理W’的最优路线是按特征从小到大开始打，易知W的最优路线的血量一定<=W’的最优路线，而这能达到，因此W的最优路线也是按特征从小到大开始打。

综上所述，我们有

定理4（八爪鱼定理）：在限制条件E下，一个八爪鱼结构中，为获得最优解，若有坏点组，应该将其合并成大点，直到没有坏点组为止。这时，只需要按点的特征从小到大开始打就可以了。假如几个点特征相同，那么这几个点可以随便安排顺序。

例4：蓝宝石+1防御，盾+5防御，血瓶+2000生命，请问怎么打？

例4答案：+31防后怪物伤害仍然全为正，且目前怪物伤害之和低于勇士生命，因此限制条件E满足。（血瓶无用）

楼上图片为：初始点图，第一次合并坏点组，第二次合并坏点组

答案：10,12,13,14,7,8,9,15,6,1,2,3,4,5,11

树结构

此处与图论中的树定义相同。连通性我们默认他有，因此图中没有圈的结构称为树。易知八爪鱼结构是树结构的子集。下图加上了一点看起来复杂的结构，但实际上还是一棵树。（勇士在左下角）

根据树的性质，所有结点到勇士都只有一条路径，定义结点的距离为这条路径的长度。

结点A的后代结点指所有到勇士路径经过A的结点。

一个结点处的子树定义为它和它的所有后代结点形成的树。

结点A的子结点定义为所有到勇士路径经过A且距离比A大1的结点。

定义4：一个结点处的子树定义为“阳光树”，如果它的所有结点均满足：该结点的特征<=该结点的子结点的特征。（如果没有子节点，也算他满足）如果一个结点处的子树是阳光树，称这个节点为阳光结点。

显然，所有的叶结点（没有子节点的结点）都是阳光结点。如果一个节点是阳光结点，则他的所有后代节点都是阳光结点。

我们的目标是在不剪掉最优解的情况下，把一棵树变成阳光树。

定理5（阳光子结点连续定理）：如果一个结点A的所有子结点都是阳光结点，且节点A的特征是a，节点A的子树中特征最小点B的特征b<a，根据假设这个点一定是A的子结点（如果有好几个，至少有一个是），那么至少一个最优解打完A后立刻把这个点打掉。

证明：假设不是，最优解打完A后又打了一系列点，然后打B，把这串点的特征写出来形成一个数列，第一个数是a，最后一个数是b。

从第二个数开始，如果这个点不属于A的子树，染成红色，如果属于A的子树，染成蓝色。

最后一个b是蓝色。b前面那个如果是蓝色，则一定>=b，根据交换基本定理，b和前面那个交换更优或不变，由于B是A的子结点，这个交换可以进行。因此可以把b交换到前面是红色为止，还是最优解。故不妨假设b前面那个是红色。

数列中如果有连续的蓝色或者红色，我们把这个操作看成一个大操作，合并成一个点。（此处用到坏点组连续定理的技巧，大操作和这几个操作血量差一个固定值）这个数用那个合并操作的特征替代。

这样，a之后的数一定是红蓝相间。

注意到，a之后的数如果不是单调不减的，若有相邻的两数c>d,则c和d交换后更优。注意到c和d一个在子树里面，一个在子树外面，因此这样的交换是可以进行的，矛盾。

a后面那个数如果是蓝色，一定>=b，如果>b,但最后一个是b，与单调不减性矛盾。因此a后面所有数都是b。易知结点B的操作与前面所有操作可交换，故可以把B交换到A后面，还是最优解。

a后面那个数如果是红色，一定>=a,否则A与这个操作交换更优，矛盾。但是b<a,与单调不减性矛盾。

根据阳光子节点连续定理，若一个结点A不是阳光结点，但它的所有子结点都是了，那么打完A后一定要再打他的一个子结点B。我们可以把B合并到A里面，B的子结点变成A的子结点。（A的特征将变化）这样A的所有子结点也是阳光结点，如果A还不是阳光结点，可以继续操作。由于每次操作A的子树至少少掉一个点，若干次后A必然是阳光结点，且最优解未被剪掉。

一开始所有叶结点都是阳光结点。从勇士出发，如果这个点的所有子结点还有不是阳光节点的，则进入那个点，重复操作，一定会遇到一个点，它的所有子结点都是阳光结点。按照上述操作若干次这个点就会变成阳光结点。每次操作后非阳光结点个数减少1，若干次后必然会把勇士也变成阳光结点。

此时根据星型定理易知按照特征从小到大开始打即可。

定理6（树定理）：在限制条件E下，一个树结构中，为获得最优解，应当按照上一段描述的，将勇士变为阳光结点。这时，只需要按点的特征从小到大开始打就可以了。假如几个点特征相同，那么这几个点可以随便安排顺序。

例5：蓝宝石+1防，盾+5防，come on！

定理6包括了星定理，八爪鱼定理，是一个比较强的定理。

我们再考虑能否将限制条件E放松一下。

定理7（大树定理）：一个树结构中，不管是否满足限制条件E，先按照定理6的方法得出一条路线，实际操作此路线，如果勇士没死，并且勇士打的怪物伤害为正或恰好为0（即少1防增伤*2=少2防增伤），则这就是最优路线。

这是本文的最强结果，定理7很显然，因为在没有限制条件E时，蓝宝石的减伤效果必定 <=W（见5楼）,而我们已得到W的最大值，并且确保这个值能达到，因此这必然是最优路线。

本文基本结束了，因为有圈的图太困难，我不知道怎么处理。有建议和想法欢迎留言！

后续

好久没更新了，更新一下吧！之前的文章中提到的算法不是最优的，worcher将此题改编为ACM黑龙江省赛题后发现了一个更优的算法，时间复杂度可以降低为O(nlgn)，n为结点个数。

我们计算完所有特征之后，直接观察最小点A，看看它是否有父亲。如果它没有父亲，我们取这个最小点,然后在剩下的树上重复操作。如果有父亲，由最小性，它的父亲B的特征>=A的特征。我们证明：在至少一条最优路径中，取了B之后，立即取A。

我们假设取B之后，进行了另一些操作C之后，再取A。则由A的最小性，C的平均特征>=A的特征。易证明：BAC不劣于BCA。因此得证。

因此我们直接把A并入B中。然后重复操作。这样纸笔算可以简化很多流程。下面证明这个算法的时间复杂度是O(nlgn)。

这里除了取最值之外的操作时间复杂度为O(n)。取动态最小值的时候，可以构造一个小根堆，把所有点放入堆之后，给每个点加上一个时间参数1。每次取堆顶就是最小数。如果有结点合并，把父亲加入小根堆，并给这个点的时间参数+1。（堆中可能有多个同一点，但时间参数不同。）每次取堆顶时，检查时间参数是否是最新，不是的话直接扔掉。易知结点个数<=n,每次删除或添加结点的时间复杂度都是O(lgn)。扔掉无效结点的次数不会超过n次，因为一个新节点被加入时才会增加一个无效结点，新结点被加入仅当合并结点，不会超过n次。取出最小结点的次数也不会超过n次，因此时间复杂度是O(nlgn)。感谢worcher提供的优秀算法!