WEEK12 csp模拟 T4 咕咕东学英语

题解

这道题如果要是想通，就会觉得很简单。否则就会觉得很难。自己在测试时对这道题就一头雾水，没什么思绪。后来看了一些题解，才明白过来。

如果要是找出所有的字串，然后检查这个字串中的所有字母是不是符合要求，这样的话时间复杂度就太大了。所以我们必须想其他的方法----先算出总的子串数，再减去不是delicious子串的子串数。总的子串数：ans=n*(n-1)/2。如何判断一个字串不是delicious字串呢，经过总结发现，不是delicious子串的格式都为：A…AB、B…BA、AB…B、BA…A，也就是说，在一个子串中，如果第一个字母（或最后一个字母）与其他字母都不相同的话，那这个字串就不是delicious子串，其他别的情况都是delicious子串。所以我们在找不是delicious的串的时候，就简单多了。先从头遍历所有字符，若第i个字符与第i-1个字符不相同的话，则以第i-1个字符前面与其相同的字符为起点、以第i个字符为结尾的这些字串都不是delicious的，用ans减去这些的数目。然后从后向前遍历，若第i个字符与第i+1个字符不相同的话，则以第i个字符为起点、以第i+1个字符后面与其相同的字符为结尾的这些字串都不是delicious的，用ans减去这些的数目。最后得出的答案就是最终答案。注意AB与BA在两次循环中被算成非delicious两次，在ans中减去了两次。所以必须在其中一次的时候补回来。

ans很大，不可以用int来存储，用long long。

代码

#include <iostream>
#include <string>
using namespace std;
long long n,ans,las;
string str;
int main(int argc, char** argv) {
	cin>>n;
	cin>>str;
	ans=(n*(n-1))/2;
	las=0;
	for(int i=1;i<n;i++){
		if(str[i]!=str[i-1]){
			ans-=(i-las);
			ans++;
			las=i;
		}
	}
	las=n-1;
	for(int i=n-2;i>=0;i--){
		if(str[i]!=str[i+1]){
			ans-=(las-i);
			las=i;
		}
	}
	cout<<ans;
	return 0;
}