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输入 19 0 1 0 0 0 1 1 0 0输出 16思路分析题目要求找出最长的连续子区间使得区间内男生1和女生0人数相等。经典解法将女生视为 -1男生视为 1那么问题转化为求最长子数组和为 0 的长度。使用前缀和并记录每个前缀和第一次出现的位置。当再次遇到相同前缀和时说明这两个位置之间的子数组和为 0长度为当前位置 - 第一次出现位置。注意前缀和为 0 时应从位置 0 开始即空前缀因此初始化pos[offset] 0。时间复杂度 O(n)空间复杂度 O(n)。代码实现#includebits/stdc.husingnamespacestd;intmain(){intn;cinn;//读入人数intoffn,s0,ans0;//off为偏移量s为前缀和ans为答案vectorintpos(2*n5,-1);//记录前缀和第一次出现的位置大小足够pos[off]0;//前缀和为0的位置为0for(inti1;in;i){intx;cinx;//读入性别s(x1?1:-1);//男生1女生-1intidxsoff;//偏移后的下标if(pos[idx]!-1)ansmax(ans,i-pos[idx]);//已出现过更新答案elsepos[idx]i;//第一次出现记录位置}coutansendl;//输出最大长度return0;}功能分析输入处理读取人数n和n个性别值0 或 1。前缀和转换将女生视为 -1男生视为 1实时计算前缀和。哈希表记录使用数组pos模拟哈希表记录每个前缀和首次出现的下标偏移后存储。最长子区间计算遍历过程中若当前前缀和已出现过则更新最大长度否则记录首次出现位置。输出结果输出最长连续子区间的长度若不存在则输出 0。【完整系列请查看专栏】信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}