AB-string

Created by LXC on Sun Jan 7 22:29:41 2024

https://codeforces.com/problemset/problem/1238/D

ranting: 1900

tag: binary search, combinatorics, dp, strings

problem

如果一个字符串的每个字母，属于至少一个（长度大于1）的回文串，则称这个字符串为good。

• AABB：（t1，t2属于回文串t1t2；t3，t4属于回文串t3t4t5）
• ABAA：（t1,t2,t3属于回文串t1t2t3；t4属于回文串t3t4）
• AABB和ABAA都是good

一个长度为n的字符串s（只由字母A,B组成），问s的子串中有多少个good字符串

solution

对于串$s_1s_2…s_n$，如果n不小于2，则只有$s_1$和$s_n$可能不属于某个回文串。对于$s_2…s_{n-1}$任意一个$s_i$，如果$s_{i-1}\ne s_{i+1}$那么$s_{i-1}s_i$与$s_{i}s_{i+1}$必有一个是回文串，否则$s_{i-1}s_is_{i+1}$是回文串。

我们考虑坏字符串的个数，坏字符串只要第一个或最后一个字符不属于某个回文串即可。$s_1s_2…s_n$中如果$s_1$不属于某个回文串，那么$s_2…s_n$中不会有$s_1$字符出现。

因此坏字符串只有四种类型：

$ABB…BB$

$BB…BBA$

$BAA…AA$

$AA…AAB$

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll ans = n*(n-1)/2;
    s = "#"+s+"#";
    int p = 0;
    for (int i=1; i<=n; i++) {
        if (s[i] != s[i+1]) {
            if(p!=0) ans -= i-p;
            p = i;
        }
    }
    p = n+1;
    for (int i=n; i>=1; i--) {
        if (s[i] != s[i-1]) {
            if (p!=n+1) ans -= p-i-1;
            p = i;
        }
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}