A，B，C其实本来还想写点儿啥的。。。结果过了之后一看题解和题解想的一样啊。。。那我就没什么说的了。。。简单说一下每道题的做法吧
题意可以上ch看。
A.这是个置换，然后分成了若干个圈。交换的最小次数为n-环的个数。坑点是方案数。对于每一个环分别处理，ans+起来，因为交换两个环的元素一定不会最优。而一个环内任何交换两个都会使一个环拆成两个。这样也是有效的。
B.注意到能吃的n-1次是固定的，而且我们不能从前往后推这次吃不吃。所以我们从后往前，先到1只狮子的情况。然后往回移。一旦发现每次找到最晚的因为进行了捕食活动而丧命的狮子，撤销他到last-1的捕食活动，并且更改这些捕食中丧命的狮子的存活状态。然后继续。
C.这题yy了好久，真是太弱了。。。其实只要倍增d[i]即可，d[i]表示fa[i]向下但不经过i的最短路径，这只要预处理一下就好了。所以需要保留最大，次大，三大这三个值。（LCA的特殊性）还有加上LCA向上最短，x，y向下最短。一条链的情况单独处理。这样就ok了。
D.神题果断不会做。搬运题解：
算出A类液体的总量和B类液体的总量，易知最后只剩总量更多的那种液体，下面我们都假定A类液体多于B类液体。
对A类液体的杯子考虑状态转移，设f(i)为保留第i个杯子，前i个最少剩下多少个杯子。那么f(i)能从f(j)转移过来，须满足从第j+1到第i-1个杯子中B类液体的量大于等于A类液体的量且从第j+1到第i个杯子中A类液体的量大于B类液体的量。（OrzOrzOrz！！！）
其实想到这一步就不难了，接下来就用平衡树优化一下即可。Orz STD写动态开点线段树。
评论 (0)
