Delicious子串

问题描述

有个字符串，只由 A 或 B 组成，求有多少个子串是Delicious的。
Delicious定义：对于一个字符串，我们认为它是Delicious的，当且仅当它的每一个字符都属于一个大于 1 的回文子串中。

Input

输入第一行一个正整数 n，表示字符串长度。(n ≤ 300000)
接下来一行，一个长度为 n 只由大写字母 A、B 构成的字符串。

Output

输出仅一行，表示符合题目要求的子串的个数。

Sample

Input: 
5
AABBB

Output: 
6

Explain: 
    对于该样例，符合条件的六个子串分别是：
AA AABB AABBB BB BBB BB

Limitation

Time limit      1000 ms
Memory limit    10000 kb

解题思路

题目可能有点难理解，刚开始想 AABB 不是回文， AABBAA 这样的才是回文啊……然后多观察了几下，就是求出多少个回文子串，并把这些位置连续的回文子串组合。

比如AABBB的回文子串是：AABBB，AABBB，AABBB，AABBB。Delicious子串包括这 4 个，再加上组合的 AABBB 跟 AABBB，共6个。

做题思路就是，找出所有子串，然后把他们拼起来……好像很难拼啊，不一定是两两拼接，还可能是3个、4个……然后想到连通图的问题了……然后我崩了，最后一个数据点都没过。

赛后看了别人的思路：所有子串个数是 n(n -1)/2，把它扣去不是Delicious子串的个数就好了……

问题变成什么不是Delicious子串：ABB..B & BAA..A，AA…AB & BB..BA。
从头到尾扫一遍，可以去除后者；从尾到头，可以去除前者。

然而这样 AB 跟 BA 子串会多减一次，所以要加回来。

注意数据范围，用 long long。

源代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const long long maxN = 300020;
char arr[maxN];

long long solve(long long n) {
	long long ans = n * (n - 1) / 2;
	long long same = 1;
	for (long long i = 1; i < n; i++) {
		if (arr[i - 1] == arr[i])
			same++;
		else {
			ans -= same;
			same = 1;
		}
	}

	same = 1;
	for (long long i = n - 2; i >= 0; i--) {
		if (arr[i] == arr[i + 1])
			same++;
		else {
			ans -= same;
			same = 1;
		}
	}
	
	for (long long i = 1; i < n; i++)
		if (arr[i - 1] != arr[i])
			ans++;
	return ans;
}

int main() {
	long long n;
	while (!(cin >> n).eof()) {
		for(long long i = 0; i < n; i++)
			cin >> arr[i];
		long long ans = solve(n);
		cout << ans << endl;
	}

	return 0;
}