CF edu 162 题解

· · 个人记录

前三个题略。

D

根据题意。随便写一个二分即可。

显然我们一定是把 i 左边或者右边相邻的一个区间联合然后把 i 宰了。显然这个在区间长度大于 2 的是有单调性的。二分。长度为 1 特判。一个区间可以联合当且仅当他长度为一或者不是所有数都相同。

E

法一：根据题意。随便写一个虚树即可。你都会虚树了我还需要给你说怎么在虚树上算答案吗。

法二：根据题意。随便写一个点分治即可。你都会点分治了我还需要给你说点分治怎么算答案吗。

F

根据题意，随意思考，容易发现第二种操作最多做一次，而且一定在最后用。

要么不使用第二种操作。随意写一个贪心即可。你都做到 F 了我还需要给你说怎么写这种贪心吗。

要么使用一次第二种操作。随意写一个贪心套一点字符串即可。

你都做到 F 了我还需要给你说怎么写这个贪心套字符串吗

我们直接把原串翻转，然后第二种操作就变成了删除后缀零，然后返回当前串。

显然我们希望去除前后缀零后串长越短越好。注意到对于每一个 1 要么不存在合法的右端点，要么能找到一个最短的左端点。你都做到 F 了还需要我给你讲怎么找吗。

然后只考虑串长最短的那一批。随意思考会发现直接按照原串比对字典序找最小的就是对的 ^!。

然后随意 SA 一下就可以了。

最后两个串取最优。你都会 SA 了，我还需要给你说这步怎么做还有怎么算答案吗。