csp信奥赛C++高频考点专项训练之前缀和差分 --【一维前缀和】：“非常男女”计划

csp信奥赛C++高频考点专项训练之前缀和&差分 --【一维前缀和】：“非常男女”计划

题目描述

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

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

输入格式

第一行有一个正整数n ( 1 ≤ n ≤ 10 5 ) n\ (1\le n \le 10^5)n(1≤n≤105)，代表学校的人数。

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

输出格式

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

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

输入输出样例 1

输入 1

9 0 1 0 0 0 1 1 0 0

输出 1

6

思路分析

题目要求找出最长的连续子区间，使得区间内男生（1）和女生（0）人数相等。
经典解法：将女生视为 -1，男生视为 1，那么问题转化为求最长子数组和为 0 的长度。
使用前缀和，并记录每个前缀和第一次出现的位置。当再次遇到相同前缀和时，说明这两个位置之间的子数组和为 0，长度为当前位置 - 第一次出现位置。
注意前缀和为 0 时，应从位置 0 开始（即空前缀），因此初始化pos[offset] = 0。
时间复杂度 O(n)，空间复杂度 O(n)。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin>>n;//读入人数intoff=n,s=0,ans=0;//off为偏移量，s为前缀和，ans为答案vector<int>pos(2*n+5,-1);//记录前缀和第一次出现的位置，大小足够pos[off]=0;//前缀和为0的位置为0for(inti=1;i<=n;++i){intx;cin>>x;//读入性别s+=(x==1?1:-1);//男生+1，女生-1intidx=s+off;//偏移后的下标if(pos[idx]!=-1)ans=max(ans,i-pos[idx]);//已出现过，更新答案elsepos[idx]=i;//第一次出现，记录位置}cout<<ans<<endl;//输出最大长度return0;}

功能分析

• 输入处理：读取人数n和n个性别值（0 或 1）。
• 前缀和转换：将女生视为 -1，男生视为 1，实时计算前缀和。
• 哈希表记录：使用数组pos模拟哈希表，记录每个前缀和首次出现的下标（偏移后存储）。
• 最长子区间计算：遍历过程中，若当前前缀和已出现过，则更新最大长度；否则记录首次出现位置。
• 输出结果：输出最长连续子区间的长度（若不存在则输出 0）。

【完整系列请查看专栏】：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++提高组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}