写在前面

我第一次接触前缀和是什么时候呢？
就是考ccf的时候，呵呵。
很多同学都是暴力拿了70分，于是，很多同学在刚第二题的时候阵亡了…
而我，去后面偷了点分，我215过了…
来，骗，来，偷吸，哎，后面我们再说怎么骗分…
真题地址
CCF-2020-12-2 期末预测之最佳阈值(低俗题)-你留的眼泪，我来帮你拭去~~~
2021-4-2第二题在
202104-2 领域均值 二维前缀和

【问题描述】

给定一个由字符’a’和字符’b’组成的字符串，可以删除若干字符，使得剩下来的字符串满足前后段为a，中间段为b（aaa…aaabbbb…bbbbaaa…aaa）,区段可以没有字符（ba,ab,b,aa都是合法的），求最长剩下字符串的长度。

【输入形式】

输入为一行一个长度不超过5000的非空字符串，字符串仅由字符’a’和字符’b’组成。

【输出形式】

输出为一个整数，表示符合要求的最长剩下字符串长度

【样例输入1】

abba

【样例输出1】

4

【样例输入2】

bab

【样例输出2】

2

题解

思路

• 1.这个题开始看会有点蒙，其实很简单的，就是看成三个部分，前面是a，中间是b，后面是a。暴力就可以做，两层循环然后遍历三个部分，然后数里面的a和b就可以了
• 2.但是暴力解法是无法通过全部样例的
• 3.所以我们有了前缀和，这个就和前n项和是一样的，这样一说，大家肯定都懂了，大家高考数学做的题目中，已知前n项和表达式，求an的表达式这些…
• 4.这样，我们计算某个区间的a和b就可以简化了，比如是第一个部分的a不用一个个去数了，可以直接调用
• 5.第二个部分的b可以，用两个点的b相减得到中间区间的b
• 6.遍历两个节点，得到所有情况的三个部分，然后我们计算三个部分的值相加，求出最大值即可

代码

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
	string s;
	vector<int> a,b;
	cin>>s;
	/**********前缀和init初始化**************/
	if(s[0]=='a') {
		a.push_back(1);
		b.push_back(0);
	}else{
		a.push_back(0);
		b.push_back(1);
	} 
	for(int i=1;i<s.length();i++){
		if(s[i]=='a'){
			a.push_back(a[i-1]+1);
			b.push_back(b[i-1]);
		}else{// == 'b'
			a.push_back(a[i-1]);
			b.push_back(b[i-1]+1);
		}
	}
	int max=-1;//记录结果，最大值 
	int a_first,b_mid,a_final;//其实就是三个部分相加，
	//这个题用暴力也可以做，但是拿不到满分，所以我们用前缀和来降低复杂度 
	/************下面遍历两个节点，可以截出三个部分作为上面的三个部分***********************/
	for(int i=0;i<s.length();i++){
		for(int j=i;j<s.length();j++){
			a_first=a[i-1];//第一部分所有的a 
			b_mid=b[j]-b[i-1];//第二部分所有的b 
			a_final=a[s.length()-1]-a[j];//第三部分所有的a 
			if(a_first+b_mid+a_final>max){
				max=a_first+b_mid+a_final;
			} 
		}
	} 
	cout<<max<<endl;
	return 0;
} 

文中遍历的i，j是b部分的起点和终点，所以说我们计算b部分的时候是要包含起点的，所以b_mid=b[j]-b[ i-1]
同理a的部分是不包含这两个这个起点，终点的
所以第一个部分的a_first=a[i-1]
最后一个部分的a_final=a[s.length()-1]-a[j]

那么，我们也可以b都不包含，我们可以写为
a[i]
b[j-1]-b[i]
a[s.length()-1]-a[j-1]