Educational Codeforces Round 110 Unstable String 题解 (Java/C++)

题解

首先，我们考量本身就是unstable的串能够拆成多少个字串。对于010101。我们发现，可以拆成6个长度为1的，5个长度为2的，……，以及1个长度为6的unstable子串。因此可得，对于任意长度为n的unstable串，可以有$\frac{n\cdot(n+1)}{2}$种解。

现在我们来考虑形如0011这样的串，也就是本身不是unstable串的串。我们可以发现，可以将这个串拆成三个独立的unstable串，即：0，01，1。而这个unstable串可以按照前面的划分字串的方法进一步划分。

于是问题就转化成了寻找最长连续unstable子串。我们发现，unstable串其实本质就两种：1. 0101… 2. 1010…。我们可以将这两种模式带入原串进行匹配。只要能够匹配上的，就是一个独立的unstable子串。
比如0??0。我们首先带入0101。我们可以发现，010可以匹配，最后一位0和1不匹配。于是我们找到了一个最长连续untable子串为：010。（其中两个?被替换为1和0）
接着带入1010。我们发现第一位不能匹配，最后三位可以匹配成010。于是我们找到最长连续unstable子串为010。（其中两个?被替换为0和1）
于是我们就找出了所有可能的最长的连续的unstable串。

最后我们发现，如果直接用最开始的方式计算所有可能数的时候，问号会被计算两次。比如0??0中。带入0101得到的0[10]和带入1010得到的[01]0（[]内表示由?替换得来），按照$\frac{n\cdot(n+1)}{2}$种解的话，两个?的所有可能恰好被计算了两次，于是减去即可。

综上对于0??0有$\frac{3\cdot(3+1)}{2}+\frac{3\cdot(3+1)}{2}-\frac{2\cdot(2+1)}{2}$种解法。

再举个例子，第三组样例：?10??1100。
按010101010匹配，得到2个unstable串：$\begin{matrix}
[?10??1]10[0]\\
[010101]01[0]\\
\end{matrix}$。
带入101010101匹配，得到3个unstable串：$\begin{matrix}
[?]10[??]1[10]0\\
[1]01[01]0[10]1\\
\end{matrix}$。
同时我们发现原串有2组连续?，也就是[?]10[??]1100。
于是得到$(\frac{6\cdot(6+1)}{2}+\frac{1\cdot(1+1)}{2})+(\frac{1\cdot(1+1)}{2} +\frac{2\cdot(2+1)}{2}+\frac{2\cdot(2+1)}{2})-\frac{1\cdot(1+1)}{2}-\frac{2\cdot(2+1)}{2}=25$。

代码

Java

C++