洛谷1114 “非常男女”计划

原题链接

日常写水题
将所有女生看作\(-1\)，然后对整个序列进行前缀和操作（设前缀和数组为\(S[]\)）。那么若\(S[x] = S[y]\)，就表明区间\((x, y]\)之间的男女人数是相同的。
因此我们扫一遍前缀和数组，开一个桶记录某个值下的最小下标（即上面提到的区间左端点\(x\)），而当下一次扫到该值时，就拿当前的下标去与桶里记录的最小下标作差。
那么答案就是对每次作差取\(\max\)。
另外，因为前缀和会有负数，所以要将桶的下标平移下，并注意下前缀和为\(0\)的情况。

#include<cstdio>
using namespace std;
const int N = 1e5 + 10;
int a[N], v[N << 1];
inline int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c < '0' || c > '9'; c = getchar())
        p |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return p ? -x : x;
}
inline int maxn(int x, int y) { return x > y ? x : y; }
int main()
{
    int i, n, x, ma = 0;
    n = re();
    for (i = 1; i <= n; i++)
        a[i] = a[i - 1] + (re() ? 1 : -1);
    for (i = 1, v[N] = 0; i <= n; i++)
    {
        x = a[i] + N;
        if (!a[i] || v[x])
            ma = maxn(ma, i - v[x]);
        if (!v[x] && a[i])
            v[x] = i;
    }
    printf("%d", ma);
    return 0;
}

洛谷1114 “非常男女”计划

原文：https://www.cnblogs.com/Iowa-Battleship/p/10580728.html