CodeForces 1238-D AB-string

题目:

传送门

思路:

因为字符串只有A和B两种字符,我们不妨研究一下符合条件的特点.
对于一个字符串我们将相同的连续的分为一段,如果分成了三段,则可以构成 ABA 或者 BAB类的回文串,则三段以上都是成立的,如果分成了两段，如果有一段连续的个数为 1,则是构不成回文串的,如果只有一个段,很明显个数为 1不符合其他均符合.
可以发现不符合条件的串的特点很明显,所以我们考虑计算不符合条件的串,然后从总字符串中减去就可以了.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <map>
#include <string>
#include <cstring>
#define fir first
#define sec second
using namespace std;
 
int n;
int pre;
string s;
 
int main() {
	long long ans = 0;
	cin>>n>>s;
	pre = 1;
	for(int i=1;i<n;i++) {
		if(s[i] != s[i-1]) {
			ans += pre;
			pre = 1;
		}
		else pre++;
	}
	pre = 1;
	for(int i = n-2;i>=0;i--) {
		if(s[i] != s[i+1]) {
			ans += pre-1;
			pre = 1;
		}
		else pre++;
	}
	cout<< (1ll*(n-1)*n/2 - ans)<<endl; 
	return 0;
}