CF2144F Bracket Groups Solution

Monomial · 2025-09-16 10:46:41 · 题解

介绍一个随机化做法。

首先有 \texttt{()} 的情况必然不合法。

接下来我们声称，其他情况必然有解，且 m \leq 2。证明如下，我们构造两个长度为 k 的括号序列 \texttt{(((\dots)))} 和 \texttt{()()\dots()()}，容易发现同时作为两者子串的只有 \texttt{()}，所以我们的猜想是正确的。

所以我们只需要考虑是否存在 m=1 的解。我不太会串串，所以考虑直接随出来一些合法的括号序列，判定它们是否合法。若全部失败，我们直接构造 m=2 的解。感性理解一下，在本题的数据范围下，该做法较难被卡掉。