20250910NOIP模拟赛

20250910NOIP模拟赛

A

题意：

有 \(n\) 个小球分为红、蓝两种颜色排成一排，现在你可以进行若干次操作，每次操作选择任意 \(R+B\) 个小球，使其有 \(R\) 个红球，\(B\) 个蓝球，把这些小球全部染为白色，且在该选择序列中，最左侧的球到最右侧的球之间不得存在已经被染为白色的小球。

其中 \(n\le 1e5\)

思路：

首先我们考虑操作过程，存在 跳着删除 和 整段删除 这两种删除方法，且当以点 \(i\) 为删除右端点时，我们肯定是想要使得左端点与 \(i\) 的距离最近（因为此时对于白点的分布影响最小），但是观察到在跳着删除之后我们剩下的若干个联通块互不干扰，所以我们若存在一种方案使得左端点与 \(i\) 的距离最近时可能无法保证删除完成之后剩下的联通块本身能够被消除掉。

所以我们不妨把时间轴倒序，暂且考虑 整段删除 都已操作完成的情况，那么我们若把尚未被匹配的节点压入栈时，此时以 \(i\) 为右端点（如果可以消除的话）要消除的就是栈顶的 \(R+B\) 个节点，因为若让 \(i\) 再在栈上进行 跳着删除 操作时，我们必定会产生新的白色联通块，使得下一次在栈上进行操作时必定会跨越一个白色联通块，这样也能满足我们想要的 “左端点与 \(i\) 的距离最近”这一条件。

所以我们直接在栈上进行操作，每次判断栈顶的 \(R+B\) 个元素是否能够形成一次操作。