题解 P7339 【『MdOI R4』Kotori】

BFqwq · 2021-02-12 14:45:53 · 题解

C.kotori

由于只有一个人，所以——士道一定是燃王！

于是只要输出 T 个 \texttt{kotori} 即可。

因为是两个人，所以只有一场比赛。

根据规则，如果 a_1+m\ge a_2，那么琴里就可以使士道获胜，此时输出 \texttt{kotori}；否则就代表琴里也无力回天，此时输出 \texttt{Yoshino}。

由于人数很少，因此我们可以直接考虑爆搜。

对于每场比赛，如果参赛双方都能获胜，则以双方获胜的情况分别搜一次；否则的话，只搜一次。

最坏情况复杂度 \operatorname O(2^n)，可以通过。

由于 m=0，所以我们没有任何支配权，只能按照原来的票数大小评胜负。

我们可以直接考虑模拟，求出每场比赛的胜者。

这里我们可以采用递归的方式，每次折半，然后找出两个半场的胜者，然后令他们两 PK。

注意如果比赛存在平票情况，那胜者可以任选；但如果此时有 1 参加，那胜者必须为 1。

复杂度为直接递归的复杂度 O(n)。

回顾 Subtask 3，我们发现爆搜冗余的状态非常多。对于同一个人获胜，却可能存在着 2^n 种之多的情况。

受到 Subtask 4 的启发，我们可以考虑递归。

我们求出每一个子区间的所有可能的胜者，并将其以某种方式存起来，然后考虑这个区间的胜者。

对于每个左子区间可能的胜者，如果它要成为最终的胜者，那我们需要在右子区间寻找一个它可以击败（相差小于等于 m）的对手。

我们枚举右子区间，逐个判断对应的选手能否被左子区间的这个选手击败，如果存在能击败的数则代表左子区间这个数可行，否则不可行。

依次合并即可。

上一个 subtask 的做法已经接近正解了，我们只需要考虑如何优化。

其实非常简单，既然要在右子区间击败一个选手，那我们肯定是挑最菜的来击败啦~

于是就考虑如何维护这个最菜（粉丝人数最少）的选手。

如果使用一个堆的话，我们可以以 \operatorname O(n\log n\log n) 的复杂度来解决。

但我们回忆起一个经典的分治模型：归并排序，发现其实我们可以直接按照归并排序的方式来进行合并。

每次删除最小的不满足条件的，然后对剩余的进行归并，可以得到复杂度 \operatorname O(n\log n) 的解法。

事实上，由于区间的最大个数恒定，我们直接枚举区间内的值来找最小，复杂度同样为 \operatorname O(n\log n)，可以通过本题。

当然，这里也可以使用一些可合并的数据结构，比如可并堆等，也可以以相同的复杂度通过。

方法很多，可以自行选择。

综合来说，这是一道比较水的题，放在 C 算是很送分了。

不过其实，这题很容易陷入的一个误区是直接考虑贪心。可惜大部分的贪心都是能够 hack 的，至少在赛前没有那位出题人拥有一个正确的贪心。

本题的主要考察点是分治思想，没有涉及到毒瘤的算法和长篇的代码。为良心的出题人点赞！

附一张琴里世萌冠军（萌王）的海报：