【GESP】C++五级练习题（前缀和） luogu-P1114 “非常男女”计划

发表于 2025/12/08

作者 OneCoder

次浏览 14 分钟阅读

GESP C++ 五级练习题，一维前缀和与哈希表（或数组映射）的综合应用。题目难度⭐⭐★☆☆，适合练习将问题转化为数学模型的能力，洛谷难度等级普及-。

luogu-P1114 “非常男女”计划

题目要求

题目描述

近来，初一年的 XXX 小朋友致力于研究班上同学的配对问题（别想太多，仅是舞伴），通过各种推理和实验，他掌握了大量的实战经验。例如，据他观察，身高相近的人似乎比较合得来。
万圣节来临之际，XXX 准备在学校策划一次大型的 “非常男女” 配对活动。对于这次活动的参与者，XXX 有自己独特的选择方式。他希望能选择男女人数相等且身高都很接近的一些人。这种选择方式实现起来很简单。他让学校的所有人按照身高排成一排，然后从中选出连续的若干个人，使得这些人中男女人数相等。为了使活动更热闹，XXX 当然希望他能选出的人越多越好。请编写程序告诉他，他最多可以选出多少人来。

输入格式

第一行有一个正整数 $n\ (1\le n \le 10^5)$，代表学校的人数。
第二行有 $n$ 个用空格隔开的数，这些数只能是 $0$ 或 $1$，其中，$0$ 代表是一个女生，$1$ 代表是一个男生。

输出格式

输出一个非负整数。这个数表示在输入数据中最长的一段男女人数相等的子区间的长度。
如果不存在男女人数相等的子区间，请输出 $0$。

输入输出样例 #1

输入 #1

9
0 1 0 0 0 1 1 0 0

输出 #1

6

题目分析

这道题目的核心是在一个只包含 0 和 1 的序列中，找到一个最长的连续子序列，使得在这个子序列中，0 的数量等于 1 的数量。

1. 问题转化：0 和 1 变 -1 和 1

直接去统计一段区间内的 0 和 1 的个数比较直观，但难以用高效的数学公式表达。我们可以利用权值转化的思想：

把题目中的 0 (女生) 看作 -1。
把题目中的 1 (男生) 看作 1。

这样一来，“男女人数相等”这个条件就等价于：该连续子序列的所有元素之和为 0（因为 +1 和 -1 会相互抵消）。

2. 前缀和的数学原理

我们定义 sum[i] 为序列中前 i 个人的数值之和（转化后的 -1 和 1 的累加）。

sum[0] = 0 (初始状态，没有选人，和为 0)
sum[i] = sum[i-1] + val[i]

根据前缀和的性质，任意一个连续子区间 (j, i]（即从第 $j+1$ 个元素到第 $i$ 个元素）的和可以表示为： $\text{区间和} = sum[i] - sum[j]$

我们的目标是找到一个子区间，使其和为 0： $sum[i] - sum[j] = 0, i \ge j \implies sum[i] = sum[j]$

结论：只要找到两个不同的位置 $i$ 和 $j$，使得它们的前缀和 sum[i] 等于 sum[j]，那么这两个位置之间的区间（$(j, i]$，长度为 $i - j$）就满足“男女人数相等”。

3. 算法思路推导

为了找到最长的子区间，我们需要让 $i - j$ 最大。

当我们遍历到某个位置 $i$，计算出当前的 sum[i]。
我们希望找到一个最小的下标 $j$ ($j < i$)，使得 sum[j] == sum[i]。

因此，算法策略如下：

记录首次出现的位置：我们需要一个数组（或哈希表）来记录每一个前缀和数值第一次出现的下标。记为 first_pos。
初始化：
- first_pos 数组初始化为一个特殊值（如 -2），表示该前缀和尚未出现过。
- 关键点：sum 为 0 的情况在通过第 0 个人时就已经存在了（即空序列），其下标为 0。所以初始化 first_pos[0] = 0。
遍历序列（$i$ 从 1 到 $n$）：
- 计算当前的前缀和 current_sum。
- 查询：检查 current_sum 是否在 first_pos 中出现过。
  - 情况 A：出现过。说明之前有一个位置 $j$ 的前缀和也是 current_sum。那么区间 (first_pos[current_sum], i] 的和为 0。计算长度 len = i - first_pos[current_sum]。如果 len 比当前记录的最大长度 max_len 大，则更新 max_len。注意：此时不要更新 first_pos，因为我们要保留最早出现的下标以获得最长长度。
  - 情况 B：没出现过。这是该 current_sum 第一次出现，记录下来：first_pos[current_sum] = i。

4. 模拟演示 (Dry Run)

以样例输入 9 个人：0 1 0 0 0 1 1 0 0 为例。转化数值：-1, 1, -1, -1, -1, 1, 1, -1, -1

步骤 i	输入值	当前和 (Sum)	first_pos 状态 (仅列出相关)	操作
0	-	0	`pos[0] = 0`	初始状态
1	0 (-1)	-1	`pos[-1] = 1`	-1 首次出现，记录下标 1
2	1 (+1)	0	`pos[0] = 0` (已存在)	0 出现过。长度 = $2 - pos[0] = 2$。`max_len=2`
3	0 (-1)	-1	`pos[-1] = 1` (已存在)	-1 出现过。长度 = $3 - pos[-1] = 2$。`max_len=2`
4	0 (-1)	-2	`pos[-2] = 4`	-2 首次出现，记录下标 4
5	0 (-1)	-3	`pos[-3] = 5`	-3 首次出现，记录下标 5
6	1 (+1)	-2	`pos[-2] = 4` (已存在)	-2 出现过。长度 = $6 - pos[-2] = 2$。`max_len=2`
7	1 (+1)	-1	`pos[-1] = 1` (已存在)	-1 出现过。长度 = $7 - pos[-1] = 6$。`max_len=6`
8	0 (-1)	-2	`pos[-2] = 4` (已存在)	-2 出现过。长度 = $8 - pos[-2] = 4$。`max_len=6`
9	0 (-1)	-3	`pos[-3] = 5` (已存在)	-3 出现过。长度 = $9 - pos[-3] = 4$。`max_len=6`

最终输出：6。

5. 细节处理：负数下标

前缀和 sum 可能是负数（例如连续都是 0，sum 就是 -1, -2, -3…）。在 C++ 中，数组下标不能是负数。由于 $n$ 最大为 $100000$，前缀和的范围在 $[-100000, 100000]$ 之间。为了能用数组存储，我们需要加一个偏移量 (Offset)。令 OFFSET = 100000。

存 sum 时，存入 first_pos[sum + OFFSET]。
查 sum 时，查 first_pos[sum + OFFSET]。

示例代码

  
#include <cmath> 
#include <iostream> 
#include <algorithm> 

// current_sum 数组：存储到当前位置 i 为止的前缀和。
// 这里的 i 是从 1 到 n，所以大小为 n+1。
// n 最大 10^5，所以 100005 足够。
int current_sum[100005];

// first_pos 数组：用于记录某个“前缀和”数值第一次出现的下标位置。
// 因为前缀和可能为负数，范围在 -n 到 +n 之间。
// n 最大 10^5，所以范围是 [-100000, 100000]，总共 200001 种可能的值。
// 数组大小 200005 足够覆盖这个范围，并通过偏移量映射到非负下标。
int first_pos[200005];

// 定义偏移量 OFFSET
// 作用：将负数前缀和映射到数组的非负下标。
// 例如，如果前缀和为 -5，在数组中访问 first_pos[-5 + OFFSET]。
const int OFFSET = 100000;

int main() {
    // n：表示学校的人数
    int n;
    // 从标准输入读取人数 n
    std::cin >> n;

    // 循环读取 n 个学生的性别 (0 或 1)，并计算前缀和
    // i 从 1 开始，与题目描述的序列下标习惯一致
    for (int i = 1; i <= n; i++) {
        int num; // 用于存储当前学生的性别 (0 或 1)
        std::cin >> num; // 读取当前学生的性别

        // 核心转化：将 0 (女生) 视为 -1，将 1 (男生) 视为 +1。
        // 这样“男女人数相等”就等价于“区间和为 0”。
        if (num == 0) {
            num = -1;
        }
        // 计算到当前位置 i 的前缀和
        // current_sum[i] = current_sum[i-1] + (当前学生的转化值)
        current_sum[i] = current_sum[i - 1] + num;
    }

    int max_len = 0; // 初始化最长平衡子区间的长度为 0

    // 初始化 first_pos 数组：将所有位置填充为 -1。
    // -1 表示该前缀和数值尚未出现过。
    std::fill(first_pos, first_pos + 200005, -1);

    // 初始状态设置：
    // 还没开始读入数据时 (即在第 0 个位置之前)，前缀和为 0。
    // 这很重要：如果后续某个位置 i 的前缀和 current_sum[i] 再次变为 0，
    // 那么从序列的开始到位置 i 的这段区间 (长度为 i) 就是一个平衡区间。
    // first_pos[0 + OFFSET] 存储的是前缀和为 0 第一次出现的下标，即 0。
    first_pos[0 + OFFSET] = 0;

    // 再次循环遍历计算出的前缀和数组 (从第一个学生开始)
    for (int i = 1; i <= n; i++) {
        // 计算在 first_pos 数组中的实际索引（加上偏移量，转为非负数）
        int index = current_sum[i] + OFFSET;

        // 检查这个前缀和是否之前出现过
        if (first_pos[index] == -1) {
            // 情况 B：如果这个前缀和是第一次出现
            // 记录当前的下标 i。
            first_pos[index] = i;
        } else {
            // 情况 A：这个前缀和之前出现过！
            // 计算当前平衡子区间的长度：当前下标 i - 第一次出现的下标 first_pos[index]
            // 并用 std::max 更新最长长度
            max_len = std::max(max_len, i - first_pos[index]);
        }
    }

    // 输出最终找到的最长平衡子区间的长度
    std::cout << max_len << std::endl;
    return 0;
}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号

GESP, 五级

本文由作者按照 CC BY-NC-SA 4.0 进行授权