前缀和

作业介绍

/*
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 小时