CF1535C-Unstable String

2022-04-25 题解

题目大意：给出一个由’0’、‘1’和’?‘组成的字符串，目标子串是这样的非空子串（长度可以为1）：将子串中的’?'任意变成’0’或者’1’后，该子串可以变为“0101010…”或“1010101…”，求所有目标子串的长度之和。

这道题的代码非常简单，但是思维量在我近期做过的题中几乎是最大的一道，根本不像一道评分为1400的问题。直到现在我还不知道这究竟是怎么想出来的，只能从结果倒推原因。

dp[0][i]表示第i位取’0’时，以它结尾的最长合法子串的长度。如果第i位在原串s[]中为’1’，dp[0][i]的值就为0。相似的，dp[1][i]表示第i位取’1’时，以它结尾的最长合法子串的长度。dp[0][]和dp[1][]的转移大同小异，这里只说dp[0][]的转移。

显然，dp[0][]的转移方程如下。

if (s[i] == '0' || s[i] == '?')
    dp[0][i] = dp[1][i - 1] + 1;
else
    dp[0][i] = 0;

写的时候灵光一闪想到了一个压行的方法，能把dp[1][]也转移，码量相近

dp[0][i] = dp[1][i] = 0;
if (s[i] != '0')
	dp[1][i] = dp[0][i - 1] + 1;
if (s[i] != '1')
	dp[0][i] = dp[1][i - 1] + 1;

知道了这个有什么用？

一个长度为x的满足条件的串，它的子串也都满足条件。这个子串对答案的贡献就是

C_x^2+x \\ =\frac{x \times (x-1)}{2} + x

注意到，这是一个首项和公差为1，项数为 $x$ 的等差数列的求和公式。所以原式

=1+2+3+...+x

所以，整个答案就是以各项结尾的满足条件的最长子串的长度相加得到的和。状态转移的时候求个和就行了

#include <bits/stdc++.h>
using namespace std;
char s[200005];
long long dp[2][200005];
int main()
{
    int _, n, i;
    scanf("%d", &_);
    while (_--)
    {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        long long res = 0;
        for (i = 1; i <= n; i++)
        {
            dp[0][i] = dp[1][i] = 0;
            if (s[i] != '0')
                dp[1][i] = dp[0][i - 1] + 1;
            if (s[i] != '1')
                dp[0][i] = dp[1][i - 1] + 1;
            res += max(dp[0][i], dp[1][i]);
        }
        printf("%lld\n", res);
    }
    return 0;
}