csp信奥赛C++高频考点专项训练之前缀和差分 --【一维前缀和】：宝石串

csp信奥赛C高频考点专项训练之前缀和差分 --【一维前缀和】宝石串题目描述有一种宝石串由绿宝石和红宝石串成仅当绿宝石和红宝石数目相同的时候宝石串才最为稳定不易断裂。安安想知道从给定的宝石串中可以截取一段最长的稳定的宝石串有多少颗宝石组成。请你帮助他。绿宝石用G \texttt GG表示红宝石用R \texttt RR表示。输入格式一行一个由G \texttt GG和R \texttt RR组成的字符串。输出格式一行一个整数表示最长的稳定的宝石串有多少颗宝石组成。输入输出样例 1输入 1GRGGRG输出 14说明/提示RGGR \texttt {RGGR}RGGR为答案。宝石数小于等于10 6 10^6106。思路分析将绿宝石G视为数值1红宝石R视为数值-1。问题转化为在给定整数序列由1和-1组成中寻找最长的连续子段其和为0。经典解法计算前缀和pre[i]表示前i个字符的数值和那么子段[l1, r]的和为pre[r] - pre[l]。要使和为0需要pre[r] pre[l]。因此对于每个位置i记录前缀和cur第一次出现的位置first[cur]当再次遇到相同前缀和时从第一次出现的位置1到当前位置的子段和即为0长度为i - first[cur]。遍历所有位置更新最大长度即可。前缀和的范围为[-n, n]n为字符串长度可以通过加偏移量n映射到非负下标用数组快速访问。初始时前缀和为0对应的位置为-1表示空串便于计算从开头开始的合法子串。时间复杂度O(n)空间复杂度O(n)。代码实现#includebits/stdc.husingnamespacestd;intmain(){string s;cins;//输入字符串intns.size();//长度intdn;//偏移量使下标非负vectorintf(2*n5,-2);//记录每个前缀和首次出现的位置-2表示未出现f[d]-1;//前缀和0的位置设为-1intcur0,maxl0;//当前前缀和最大长度for(inti0;in;i){//遍历每个字符cur(s[i]G?1:-1);//更新前缀和G为1R为-1intidxcurd;//映射后的下标if(f[idx]-2)f[idx]i;//首次出现则记录位置elsemaxlmax(maxl,i-f[idx]);//否则计算长度并更新答案}coutmaxl\n;//输出结果return0;}功能分析输入处理读取一行仅含G和R的字符串。前缀和转换将G视为1R视为-1实时计算前缀和。哈希数组利用偏移量将前缀和映射到数组下标记录每个前缀和首次出现的位置初始时将前缀和0映射到位置-1。最长子段查找遍历每个字符如果当前前缀和之前出现过则计算子段长度并更新最大值否则记录当前位置。输出结果输出最长稳定宝石串的长度即G和R数量相等的最长连续子串长度。【完整系列请查看专栏】信奥赛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;}