题解 | 牛客练习赛91

A.神奇天平

题意：给我们一个能同时确定x（x <= m)个物体中哪个最重，哪个物品最终或者同样重，那么给我们n个物品，问至少需要多少次能够确定最重的物品是哪个？

题意：比赛的时候推了推没过，emmmmm,就很离谱，赛后几分钟想清楚了就A了，我好菜了根据样例我们可以得到将n个物品分成（m+1)堆比较优（让我自己想，怀疑自己想不到），也就是说将当前的n个物品尽可能平均的分成(m+1)堆,那么就按照每堆(n + m) / (m + 1)个进行分配，就可能会使得最后一堆的没有这么多个，那么没关系，那么此时将m堆数量为(n+m)/(m+1)的放到天平上称量，就可以知道重物在哪一堆中，剩下一堆的数量必然是小于等于(n+m)/(m+1)的，我们只需要考虑最坏情况，将这数量为（n+m)/(m+1)的一堆继续进行划分即可。

B.C.魔法学院

B题相信大家都会把，开始想的类似于差分，但是我怀疑复杂度过高，就写了一个线段树的做法

C题想了很久，主席树，差分什么的，感觉根本行不通，这题其实感觉来源于洛谷P4145花神游历各国，我好惭愧，想到做法时已经写不完了。很容易想到的就是，我们把所有修改用结构体存起来，并按照字符从大到小排序，那么一个点如果最多只需要被最大的那个字符修改一次，我们可以，也就是说对于一次修改，我们只需要修改区间[l, r]中没有被修改过的点就可以了，我们就可以用并查集来加速找没有被修改过的点这个过程，一个点被修改过，我们直接跳过去就行了当i这个点没有被修改过时，fa[i] = i，当i被修改过之后，令fa[i] = i + 1(当前点右边相邻点可能就是下一个需要修改点), 以(i+1)号点为起点，寻找下一个需要被修改的点的位置，也就是说在[l, r]不断找fa[i] = i的点

D.监狱逃亡

D题是个很套路的题吧，之前在cf在写过一个很类似的

注意到只有3行，很特殊，就意味着会有特殊的套路

我们假设此人在(1,x)这个位置移动到第二行，在(2,y)(y>=x)这个位置移动到第3行，我们会发现，此时的路线就已经固定了，快速得到一段的和，使用前缀和相信大家都会吧，此时只需要满足sum[1][x] + sum[2][y] - sum[2][x - 1] + sum[3][n] - sum[3][y - 1] >= 0,移项将x,y分开得到sum[1][x] - sum[2][x-1] + sum[3][n] >= sum[3][y - 1] - sum[2]y,这不就类似于逆序对嘛，将这两个式子的分别看作ai,bj,那么只需要满足ai>=bj且i<=j,套个树状数组，相信大家都会

E.游戏人生

看到什么最大值，最小值，可行，什么的就应该想想二分，毕竟这可是wf算法，这道题目让我知道了原来这就是可反悔贪心，还是很好理解的，每次我们只需要假设该次选择为狂暴攻击，如果此时此人的血量小于等于0了，我们就可以将前面的某次狂暴攻击反悔为普通攻击或者普通攻击反悔为防御，因为这两次反悔对怪物的攻击减少值是一样的，那么我们就只需要看哪次操作的回血最多就行了，直到使得该人血量大于0，如果不行，返回false,某个过程中怪物血量为0，返回true。

值得注意的是，此人先攻击，然后轮到怪物攻击，如果此人攻击后，人的血量大于0，而怪物死了，那么人就不会受到攻击，此时就可以返回true，我读了假题，没注意到这个，然后死活过不去样例，后来注意到了，又忘记将每次可以反悔得到的血量加入到堆中，搞了几个小时，麻了，代码能力太拉了。。。