Codeforces Round #526 (Div. 2) C. The Fair Nut and String

C. The Fair Nut and String

题目链接：https://codeforces.com/contest/1084/problem/C

题意：

给出一个字符串，找出都为a的子序列(比如a_i,a_j,a_k)满足以下条件的个数：

1.子序列的索引单增(i<j<k)；

2.在原字符串中，若a_i=a_j=a_k=a，那么满足i<=k1<j，j<=k2<k 并且 a_k1=a_k2=b。

通俗点说，就是找这样的子序列个数：要么单个a，要么每个a之间都至少有一个b。

题解：

我们考虑在字符串末尾增加一个”哨兵“，其值为b。然后用b对a进行分割，每一段a 的个数为ai。

最后统计结果：(a1+1)*(a2+1)*...*(ax+1)-1。这里减去1是因为至少没有什么都不选的情况。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5+,MOD = 1e9+;

char s[N];

ll a[N];

int main(){

    scanf("%s",s);

    int len=strlen(s);

    s[len]='b';

    int num=,cnt=;

    for(int i=;i<=len;i++){

        if(s[i]=='a') num++;

        if(s[i]=='b'){

            a[++cnt]=num;

            num=;

        }

    }

    ll ans = ;

    for(int i=;i<=cnt;i++) ans=ans*(a[i]+)%MOD;

    printf("%I64d",ans-);

    return ;

}

巴特西

Codeforces Round #526 (Div. 2) C. The Fair Nut and String

最新文章

热门文章