并没有参加 MX 比赛,这是一篇补题笔记。
T3
神人数据,一个显然假的贪心是从前往后能放就放,最后尝试将前后两端合并起来。
然后你会发现将近 50 个测试点还全是多测的情况下,我们仅仅 WA 了最后一个测试点。于是我们考虑将序列翻转做一遍,或者随机化选几个开头多做几遍我们就过了!
正解显然应该每次找最小值向两边拓展,但这样做显然比较困难,可能需要线段树带 \(\log\),但由于跑不满(没卡)所以能够在 \(n = 3e7\) 的时候通过!
怎么优化到 \(O(n)\) 呢,我们考虑只需要向左拓展到最远,那么拓展到的点一定是某一段的开头。而向左拓展的过程可以通过单调栈维护最大值最小值来达成。我们终于用正解通过了这个题!
T4
这个题数据很诡异。我只是漏了一个特判就被活活打断了双腿获得了 \(0\) 分。
首先如果全 \(1\) 或者全 \(0\) 是好判断的。
然后这种博弈题不妨找找必胜态或者必败态,玩一玩首先发现一个时刻连续 \(0\) 块和 \(1\) 块个数相同。接着发现当出现 \(10101010\) 时先手就输了。因为后手可以跟着先手拿的拿,这样最后一定出现 \(101\) 或者 \(010\) 的情景,这时候 \(1\) 或者 \(0\) 玩家连拿两个就赢了。
进一步分析我们发现,如果一个人拿完后同种颜色的块只剩一个则对手就赢了,所以每个人都要尽量不先拿完。所以每个人每次都只会取走一个,并且尽量不把一个块取完。
所以每个块对一个人的贡献是块长减一,由于两种块的数量相同,所以我们只需要判断 \(0\) 和 \(1\) 的数量即可得到胜者。
当然我们需要特判一下,如果总共就只有两个块,那么先手直接拿完了,不需要判断了。
T5
其实这个计数真的很汤吧。但这场单调栈怎么出现频率这么高。
第一档分好做,对于第二档分我们手玩一下会发现对于一个序列中的点 \(a_i\),对于满足条件的 \((i, j)\),\(j\) 是满足单调性可以二分的。于是有 \(O(n^2\log n)\) 的做法。
到这里直接做就行不通了,考虑如何判定一个段的合法性(这里令第一位为 \(1\))。发现段中每次删除的 \(0, 1\) 数量都相同,于是我们需要任意前缀中 \(1\) 的数量大于等于 \(0\) 的数量。于是将 \(0\) 看作 \(-1\),求出前缀和。则 \((i, j)\) 合法当且仅当 \(\forall k \in [i, j] s_k - s_{i - 1} \geq 0\)。二分加上数据结构维护 \([i, j]\) 中的最小值即可判定。复杂度 \(O(n\log^2n)\)。
但这么做其实比较蠢,我们从 \(n \to 1\) 扫然后用单调栈或者dan'diao维护一下即可。