P1114 “非常男女”计划

题目描述

近来，初一年的 XXX 小朋友致力于研究班上同学的配对问题（别想太多，仅是舞伴），通过各种推理和实验，他掌握了大量的实战经验。例如，据他观察，身高相近的人似乎比较合得来。

万圣节来临之际，XXX 准备在学校策划一次大型的 “非常男女” 配对活动。对于这次活动的参与者，XXX 有自己独特的选择方式。他希望能选择男女人数相等且身高都很接近的一些人。这种选择方式实现起来很简单。他让学校的所有人按照身高排成一排，然后从中选出连续的若干个人，使得这些人中男女人数相等。为了使活动更热闹，XXX 当然希望他能选出的人越多越好。请编写程序告诉他，他最多可以选出多少人来。

输入格式

第一行有一个正整数，代表学校的人数。

第二行有个用空格隔开的数，这些数只能是或，其中，代表是一个女生，代表是一个男生。

输出格式

输出一个非负整数。这个数表示在输入数据中最长的一段男女人数相等的子区间的长度。

如果不存在男女人数相等的子区间，请输出。

输入输出样例 #1

输入 #1

1 2	9 0 1 0 0 0 1 1 0 0

输出 #1

70pts使用算法

前缀和、双指针

70pts思路

题目说了，要满足几个条件：

男女人数相等
必须是连续区间
人多

那么怎么满足呢？

1，男女人数相等：做一个男女前缀和数组，统计男女人数

2，连续区间：前缀和数组可以做到，双指针去遍历区间

3，人多：把男女相等的区间存起来，取max，最后输出

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n + 1];
    int nan[n + 1], nv[n + 1];
    memset(nan, 0, sizeof(nan));
    memset(nv, 0, sizeof(nv));
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        if(a[i] == 0) {
            nv[i] = nv[i - 1] + 1;
            nan[i] = nan[i - 1];
        }
        else {
            nan[i] = nan[i - 1] + 1;
            nv[i] = nv[i - 1];
        }
    }
    int maxn = -1e9;
    for(int l = 1; l <= n; ++l) {
        for(int r = l + 1; r <= n; ++r) {
            int sum_b = nan[r] - nan[l - 1];
            int sum_g = nv[r] - nv[l - 1];
            if(sum_b == sum_g)
                if(sum_b + sum_g >= maxn)
                    maxn = sum_b + sum_g;
            r++;
        }
    }
    if(maxn == -1e9) {
        cout << 0 << "\n";
        return 0;
    }
    cout << maxn << "\n";
    return 0;
}

剩下四个点会爆TLE，四行泪~~（今天没戴ok镜，戴的框架）awa~~

满分前置算法

前缀和、桶

满分解（萌新慎入）

我们这么记录前缀和sum数组，当遇到男生时就是+1，女生就-1：sum[i] = sum[i - 1] ± 1。那如果一个区间男女个数相等就是sum[r] - sum[l - 1] = 0，换个说法就是sum[r] = sum[l - 1，因为只有相等的数相减得0。

那么我们可以先定义一个maxn，再过一遍for，这边for里干两件事情：

如果sum[i]是第一次出现，那么用一个桶记录这个前缀和数的左端点，也就是sum[i]
如果sum[i]以前出现过，即在桶里有过记录，那sum[i]就是这个区间目前的最右端点。则让当前区间与maxn做比较。

最后输出。

坑

桶要做移位操作，即没有负数下标，这里-n -> 0、0 -> n、n -> 2n，所以数组要开2n + 1，也就是最大 ~~宋泽瑜狂喜~~
以0为前缀和数的区间起始位置一定是0，因为没有人=男女人数相等。所以前缀和数组[0] = 0，同数组[n] = 0。

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n + 1];
    int sum[n + 1];
    memset(sum, 0, sizeof(sum));
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] == 0)
            sum[i] = sum[i - 1] - 1;
        else
            sum[i] = sum[i - 1] + 1;
    }
    int start[2 * n + 1];
    memset(start, -1, sizeof(start));
    int maxn = -1e9;
    start[0] = 0;
    for (int i = 1; i <= n; ++i) {
        int pos = sum[i] + n;
        if (start[pos] == -1)
            start[pos] = i;
        else
            if (i - start[pos] >= maxn)
                maxn = i - start[pos];
    }
    cout << maxn << "\n";
    return 0;
}

总结

能写出来70pts大概有个j组2等~1等的水平

100pts至少j1

还是挺有难度的。