[洛谷题解] CF451D Count Good Substrings

题目链接:CF451D Count Good Substrings

题意翻译

题目描述

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

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

输入格式

一行,字符串s

输出格式

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

样例解释

样例1中,有s[1..1]= bs[2..2] = bs[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|是字符串的长度。

字符串只包含小写ab两种字符。

解题思路

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

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

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

最终将ab的答案分别相加即可。

代码与提交记录

// 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;
}

提交记录:R24334233

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注