一道题目，两次修改，三份代码，四种分数。

评测记录

90分 代码，TLE，朴素暴力

不知道为什么错的27分代码

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 5e5 + 10;
//爆枚
int n;
bool a[MAXN];
//是否为g牛
int b[MAXN];
//g牛个数
int g[MAXN];
//下一头g牛
int h[MAXN];
//下一头h牛
 
int main(){
	scanf("%d\n",&n);
	char c;
	for(int i = 1;i<=n;i++){
		scanf("%c",&c);
		if(c=='G'){
			a[i] = true;
		}
		else{
			a[i] = false;
		}
	}
	for(int i = 1;i<=n;i++){
		if(a[i]){
			b[i] = b[i-1] + 1;
		}
		else{
			b[i] = b[i-1];
		}
	}
	int last = n+1;
	//n+1:空 
	for(int i = n;i>=1;i--){
		g[i] = last;
		if(a[i]){
			last = i;
		}
	}
	last = n + 1;
	for(int i = n;i>=1;i--){
		h[i] = last;
		if(a[i]==false){
			last = i;
		}
	}
	g[n+1] = h[n+1] = n+1;
	int ans;
	ans = 0;
	for(int i = 1;i<=n;i++){
		if(a[i]){
			if(g[i]!=n+1){
				//更1个, 
				//i+2=>g[i]-1
				ans+=max(0,g[i] - i - 2);
				//printf("g%d %d %d\n",g[i],i,ans);
				//if(h[h[i]]!=n+1){
					//下两个h牛中间 
					ans+=min(h[h[i]] - i - 2,h[h[i]] - h[i]);
					//printf("gh%d %d %d\n",h[h[i]],h[i],ans);
			}
		}
		//思路错误，应该连通块 
		//左右几个连续G或者H
		//特判在一边的 
		else{
			if(h[i]!=n+1){
				ans+=max(0,h[i] - i - 2);
					ans+=min(g[g[i]] - g[i],g[g[i]] - i - 2);
			}
		}
	}
	printf("%d",ans);
	return 0;
} 

用类似题解的思路写出了个81分

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 5e5 + 10;
int n;
bool a[MAXN];
//是否为更牛 
int b[MAXN];
//连通块第一个
int d[MAXN];
//连通块长度

void method_3(){
	scanf("%d",&n);
	char c;
	for(int i = 1;i<=n;i++){
		scanf(" %c",&c);
		if(c=='G'){
			a[i] = true;
		}
		else{
			a[i] = false;
		}
	}
	int last = 1;
	b[1] = 1;
	for(int i = 2;i<=n;i++){
		if(a[i]==a[last]){
			b[i] = last;
		}
		else{
			last = i;
			b[i] = i;
		}
	}
	for(int i = 1;i<=n;i++){
		d[b[i]]++;
	}
	for(int i = 1;i<=n;i++){
		d[i] = d[b[i]];
	}
	int ans = 0;
	for(int i = 1;i<=n;i++){
		if(d[i]==1){
			ans+=d[i-1]*d[i+1];
			ans+=max(0,d[i-1] - 1);
			ans+=max(0,d[i+1] - 1);
		}
	}
	printf("%d",ans);
	return ;
}
int main(){
	method_3();
	return 0;
}

改了改，成了9分

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 5e5 + 10;
int n;
bool a[MAXN];
//是否为更牛 
int b[MAXN];
//连通块第一个
int d[MAXN];
//连通块长度

void method_3(){
	scanf("%d",&n);
	char c;
	for(int i = 1;i<=n;i++){
		scanf(" %c",&c);
		if(c=='G'){
			a[i] = true;
		}
		else{
			a[i] = false;
		}
	}
	int last = 1;
	b[1] = 1;
	for(int i = 2;i<=n;i++){
		if(a[i]==a[last]){
			b[i] = last;
		}
		else{
			last = i;
			b[i] = i;
		}
	}
	for(int i = 1;i<=n;i++){
		d[b[i]]++;
	}
	for(int i = 1;i<=n;i++){
		d[i] = d[b[i]];
	}
	int ans = 0;
	last = -1;
	for(int i = 1;i<=n;i++){
		if(d[i]==1&&b[i]!=b[last]){
			ans+=d[i-1]*d[i+1];
			//ans+=max(0,d[i-1] - 1);
			//ans+=max(0,d[i+1] - 1);
			//printf("%d",ans);
			last = i;
		}
		else if(b[i]!=b[last]){
			last = i;
			ans+=d[b[i+1]] + d[i] - 2;
		}
	}
	printf("%d",ans);
	return ;
}
int main(){
	method_3();
	return 0;
}

求大佬debug

附：捞帖