题解 P6878 [JOI 2020 Final] JJOOII 2

发布时间 2023-11-05 20:56:41作者: djh0314

好久没写题解,水一篇。

题意

题意显然。

分析

看到这道题,我们就应该进行一个小贪心,对于最左边某一字符,直到最右边的这一字符,我们不会在中间删除同样的字符,不然则可以保留这一字符,将两边往内缩。

也就是说,我们确定了最左边的 J 后,那么留下最后一个 J 必然是当前这个 J 的后面的第 \(K-1\) 个 J,对于 O 和 I 同理,找到从当前节点开始,包括当前结点的,向后共有 \(K\) 个某字符的最左端点。

这个处理,我们可以使用一个栈从右向左来维护相同字符即可。

最后的答案,我们通过枚举最左边的 J,进一步确定最右的 J,确定最右的 O,最右的 I,这两个之间的价值就是 \(R-L+1-3\times K\)