ACM模版

描述

题解

看到很多人都说这道题是哈希+dp，我看了好久才明白这里所谓的哈希只是一种思想~~~有些傻了，之前一直不知道这种思想叫做哈希。我的dp也有些差劲了，需要加强。

以下思路是借鉴一个大牛的（ID：追梦赤子心）：

首先，我们可以预处理开头到第i个位置0的数量大于1的数量的串的最长长度sum_0[i]，同理，预处理第i个位置到结尾1的数量大于0的数量的串的最长长度。

那么，我们可以发现当结果[i, j]为0的数量大于1的数量的最长长度，那么S[i - 1]一定是1，同理，如果结果[i, j]为1的数量大于0的数量的最长长度，那么S[j + 1]一定等于0，然后我们用-1替代0，用他们的和的正负来表示0、1数量关系。

预处理过程：

设cur表示从开头到i的元素的和（sum_0）：
1、cur < 0：sum_0[i] = i + 1；
2、cur >= 0：sum_0[i] = i - head[cur + 1]，（head[cur + 1]表示cur + 1最早出现的情况）；

同理可以推出sum_1~~~

代码

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int MAXN = 1e6 + 10;

char S[MAXN];

int sum_0[MAXN], sum_1[MAXN];

int head[MAXN];

int main()
{
    while (~scanf("%s", S))
    {
        int cur = 0;
        int len = (int)strlen(S);
        memset(sum_1, 0, sizeof(sum_1));
        memset(sum_0, 0, sizeof(sum_0));
        memset(head, -1, sizeof(head));

        for (int i = 0; i < len; i++)
        {
            if (S[i] == '0')
            {
                cur += -1;
            }
            else
            {
                cur += 1;
            }
            if (cur < 0)
            {
                sum_0[i] = i + 1;
            }
            else
            {
                if (head[cur + 1] != -1)
                {
                    sum_0[i] = i - head[cur + 1];
                }
                else
                {
                    head[cur] = i;
                    sum_0[i] = 0;
                }
            }
        }
        memset(head, -1, sizeof(head));
        cur = 0;
        for (int i = len - 1; i >= 0; i--)
        {
            if (S[i] == '0')
            {
                cur += -1;
            }
            else
            {
                cur += 1;
            }
            if (cur > 0)
            {
                sum_1[i] = len - i;
            }
            else
            {
                if (head[-(cur - 1)] != -1)
                {
                    sum_1[i] = head[-(cur - 1)] - i;
                }
                else
                {
                    sum_1[i] = 0;
                    head[-(cur)] = i;
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < len - 1; i++)
        {
            if (sum_0[i] > 0 && sum_1[i + 1] > 0)
            {
                ans = max(ans, sum_0[i] + sum_1[i + 1]);
            }
        }
        printf("%d\n",ans);
    }

    return 0;
}