[洛谷题解] CF451D Count Good Substrings

发布于 2019-09-25  230 次阅读

题目链接：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;
}

提交记录：R24334233

赏

undefined