https://codeforces.com/contest/1238/problem/D
题目大意
给出 $n$ 长的只包含 ‘AB’ 的字符串 $S$。
定义一个字符串是好的：字符串中所有字符都可以是某个（不同字符不用是同一个）长度至少为 $2$ 的回文串的一部分。
问 $S$ 有多少个好的子串。
$|S| \le 3 \times 10^5$。
简要题解
观察：
- 如果串中某个字符超过两个，则这些字符都可以在某些回文中，因为只要选择相邻的两个同种字符，那中间夹得都是另一种字符，则这一定是一个回文。
- 某个串不合法当且仅当有字符只出现了一次，且该字符在串的起始或者结尾。如果出现在中间显然它两侧会被两个另一种字符包裹，可以构成 $3$ 长的回文。
有了这些观察，我们就可以枚举右边界。假设最右的字符为 $c$，根据观察 2，左边界必须至少包含 $c$ 上一次出现的位置。 然后只需要讨论对于另一种字符 $d$ 的情况，假设目前最大左边界的段已经包含了一个或以上的另一种字符，则所有满足上述约束的左边界都合法。因为如果不出现下一个 $d$ 则 $d$ 的所有频率都包裹在中间。 如果出现了下一个 $d$ 则 $d$ 的频率超过 $2$ 次，也没有问题。如果当前最大左边界的段没有包含 $d$ 则下次第一次遇到 $d$ 时，这是唯一一个不合法的段，因为这个 $d$ 无法属于任何回文，但再左推左边界时，都合法，因为如果左边字符是 $d$ 则满足 1，如果左边字符时 $c$ 则与上一种情况讨论的一致了。
代码只需要保存一下两种字符之前的出现位置即可。（实际上不用存数组，因为都各只用到了上一个）
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n;
string s;
cin >> n >> s;
vector<vector<int>> pos(2);
LL ans = 0;
for (int i = 0; i < n; i++) {
int c = s[i] - 'A';
pos[c].push_back(i);
if (pos[c].size() == 1) continue;
if (pos[c ^ 1].empty()) {
ans += i;
} else {
int r = pos[c][pos[c].size() - 2];
ans += r + 1;
if (pos[c ^ 1].back() < r) {
ans--;
}
}
// cerr << ans << ' ';
}
cout << ans << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] A. LCM Problem - Educational Codeforces Round 92 (Rated for Div. 2)