csp信奥赛C++高频考点专项训练之前缀和差分 --【一维前缀和】：宝石串
csp信奥赛C++高频考点专项训练之前缀和&差分 --【一维前缀和】：宝石串
题目描述
有一种宝石串，由绿宝石和红宝石串成，仅当绿宝石和红宝石数目相同的时候，宝石串才最为稳定，不易断裂。安安想知道从给定的宝石串中，可以截取一段最长的稳定的宝石串，有多少颗宝石组成。请你帮助他。
绿宝石用G \texttt GG表示，红宝石用R \texttt RR表示。
输入格式
一行，一个由G \texttt GG和R \texttt RR组成的字符串。
输出格式
一行一个整数，表示最长的稳定的宝石串有多少颗宝石组成。
输入输出样例 1
输入 1
GRGGRG输出 1
4说明/提示
RGGR \texttt {RGGR}RGGR为答案。
宝石数小于等于10 6 10^6106。
思路分析
将绿宝石G视为数值+1，红宝石R视为数值-1。问题转化为：在给定整数序列（由+1和-1组成）中，寻找最长的连续子段，其和为0。
经典解法：计算前缀和pre[i]（表示前i个字符的数值和），那么子段[l+1, 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)。
代码实现
#include<bits/stdc++.h>usingnamespacestd;intmain(){string s;cin>>s;//输入字符串intn=s.size();//长度intd=n;//偏移量，使下标非负vector<int>f(2*n+5,-2);//记录每个前缀和首次出现的位置，-2表示未出现f[d]=-1;//前缀和0的位置设为-1intcur=0,maxl=0;//当前前缀和，最大长度for(inti=0;i<n;i++){//遍历每个字符cur+=(s[i]=='G'?1:-1);//更新前缀和，G为+1，R为-1intidx=cur+d;//映射后的下标if(f[idx]==-2)f[idx]=i;//首次出现则记录位置elsemaxl=max(maxl,i-f[idx]);//否则计算长度并更新答案}cout<<maxl<<'\n';//输出结果return0;}功能分析
- 输入处理：读取一行仅含
G和R的字符串。 - 前缀和转换：将
G视为+1，R视为-1，实时计算前缀和。 - 哈希数组：利用偏移量将前缀和映射到数组下标，记录每个前缀和首次出现的位置，初始时将前缀和
0映射到位置-1。 - 最长子段查找：遍历每个字符，如果当前前缀和之前出现过，则计算子段长度并更新最大值；否则记录当前位置。
- 输出结果：输出最长稳定宝石串的长度（即
G和R数量相等的最长连续子串长度）。
【完整系列请查看专栏】：
信奥赛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;}