Codeforces 1084C - The Fair Nut and String

Codeforces 1084C - The Fair Nut and String

题解链接

https://lucien.ink


题目链接

https://codeforces.com/contest/1084/problem/C


题意

  给你一串字符串,问你能选出多少个形如 aba 这样的子序列(任意两个 a 之间至少包含一个 b),a 也算,abaabbaab*ba 算同一种,aaba 是非法的,复杂度 $O(n)$。


思路

  显然可以只保留 ab,然后把连续的 a 都提取出来,剩下的类似于统计 $DAG$ 不同路径数那样统计就可以。


实现

https://pasteme.cn/2420

#include <bits/stdc++.h>
const int maxn = int(1e5) + 7, mod = int(1e9) + 7;
char buf[maxn], str[maxn] = {'b'};
int len = 0, cnt[maxn], n = 0;
int main() {
    scanf("%s", buf);
    for (int i = 0; buf[i]; i++) if (buf[i] <= 'b') str[++len] = buf[i];
    for (int i = 1; i <= len; i++) {
        if (str[i] == 'a') {
            if (str[i - 1] == 'b') cnt[++n] = 1;
            else cnt[n]++;
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) ans = (ans + (ans + 1) * cnt[i] % mod) % mod;
    printf("%lld\n", ans);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。