CF1672H

NusGhy · 2022-04-26 18:29:47 · 题解

nb 题

考虑计数区间内 00 和 11 二元组的数量，分别设为 x,y。

首先显然每次会删掉一个极长的满足条件的区间。

假如删掉了一个偶数长度的区间（0[0101...0101]1\rightarrow 01），那么 x 和 y 都会减少一。

假如删掉一个奇数长度的区间，（1[1010...0101]1\rightarrow 11），那么 x 或 y 会减少一。

并且发现只要 x 和 y 都不为 0，那么总是可以找到一个偶数长度的区间删（相邻的两个不同的二元组之间总是可以删掉）。

同理，奇数长度段在 x 或 y 不为零时一定可以找到并删掉。

由于我们一定要消掉所有的二元组，并且显然没有更好的删掉的策略，所以消掉所有的二元组最少要 \max (x,y) 次（不妨设 x\leq y，前 x 次删偶数长度段，后 y-x 次删奇数长度段）。

于是最终的答案就是 \max(x,y)+1 ，前缀和优化回答询问即可。

code & data：https://codeforces.com/contest/1672/submission/155021164

题外话：CF 官方题解是一个超级复杂的论文解法，想锻炼英语阅读的话可以去看看（