前缀和
作业介绍
/*
R 1
G -1
区间和为0的区间个数
sum[i]
t sum[i]-sum[t] = 0
*/
#include <bits/stdc++.h>
using namespace std;
int a[1000005],sum[1000005];
int cnt[2000005];//cnt[i]和为i的下标的最小值
//1 -1 1 1 -1 1
/*
cnt[1] = 1
cnt[2] = 3
cnt[3] = 4
*/
int main(){
string s;
cin>>s;
memset(cnt,0x3f,sizeof(cnt));
for(int i=0;i<s.size();i++){
if(s[i]=='R'){
a[i+1] = 1;
}
else a[i+1] = -1;
sum[i+1] = sum[i]+a[i+1];
cnt[sum[i+1]+1000000] = min(i+1,cnt[sum[i+1]+1000000]);
}
// for(int i=-5+1000000;i<=5+1000000;i++){
// cout<<i-1000000<<" "<<cnt[i]<<endl;
// }
//-1 1 -1 -1 1 -1
//-1 0 -1 -2 1 -2
cnt[0] = 0;
int res = 0;
for(int i=1;i<=s.size();i++){
if(sum[i]==0)res = max(res,i);
res = max(res,i-cnt[sum[i]+1000000]);
}
cout<<res<<endl;
return 0;
}
题目
认领作业后才可以查看作业内容。
- 状态
- 正在进行…
- 题目
- 8
- 开始时间
- 2026-3-29 0:00
- 截止时间
- 2026-4-6 23:59
- 可延期
- 24 小时