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

Submission #118442540 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #118491854 - Codeforces
Codeforces. Programming competitions and contests, programming community
蜀ICP备19018968号