[洛谷题解] CF451D Count Good Substrings • KMnO4y

题目链接：CF451D Count Good Substrings ↗

题意翻译#

题目描述#

一个字符串是“好的”，当且仅当合并其中的连续区间后，它是一个回文串。比如“aabba”是好的，因为在合并后它变成了aba

给你一个字符串，现在要你分别求出长度为奇数和偶数的“好的”子串数量。（提示：不是本质不同的子串，不允许空串）

输入格式#

一行，字符串 $s$

输出格式#

一行，两个空格隔开的整数，分别为长度是偶数和奇数的“好的”字串数量。

样例解释#

样例1中，有 $s[1..1]= b$ ， $s[2..2] = b$ 和 $s[1..2]= bb$ 是好的。

样例2中，好的子串有：" $b$ ", " $a$ ", " $a$ ", " $b$ ", " $aa$ ", " $baab$ "

样例3中，好的子串有：" $b$ ", " $a$ ", " $b$ ", " $b$ ", " $bb$ ", " $bab$ ", " $babb$ "

数据范围#

$1 \leq |s| \leq 10^5$ ，其中 $|s|$ 是字符串的长度。

字符串只包含小写 $a$ 和 $b$ 两种字符。

解题思路#

点拨提示：在这题中，由于只存在 $a$ 和 $b$ 两种字符，显然，子串是好的，当且仅当子串两端字符相同。如果只是来找解题提示的就无需往下看了。

因此我们对于 $a$ 和 $b$ 字符做两次，每次只考虑一种字符。假设当前考虑的是 $a$ ，

那么，我们分别统计当前位置以及之前的位置上， $a$ 出现在奇数位置和偶数位置的次数，然后就可以轻松求出以当前位置结尾的“好的子串”数量了（而且可以奇偶分别求）。

最终将 $a$ 和 $b$ 的答案分别相加即可。

代码与提交记录#

// status: [Accepted]
// oj:     [luogu]

#include<bits/stdc++.h>
using namespace std;

string s;
typedef long long ll;
#define int ll

pair<int,int> solve(char c) {
    int st[2];
    pair<int,int> ret = make_pair(0,0);
    st[0] = st[1] = 0;
    for(int i=0;i<(int)s.length();i++) {
        if(s[i] == c) {
            st[i%2]++;
            ret.first += st[(i%2)^1];
            ret.second += st[(i%2)^0];
        }
    }
    return ret;
}

signed main() {
    ios::sync_with_stdio(false);

    cin>>s;

    pair<int,int> x1 = solve('a');
    pair<int,int> x2 = solve('b');

    cout<<x1.first+x2.first<<' '<<x1.second+x2.second<<endl;
}

cpp

提交记录：R24334233 ↗