洛谷 CF804B Minimum number of steps

嗯...

 

题目链接：https://www.luogu.org/problemnew/show/CF804B

这道题没有什么技巧，只是一道找规律的题。

首先看到“ab”可以换成“bba”，所以首先要确定我们要逆序枚举（注意s从s_0开始），如果遇到a，则把ans += cntb，因为可以换的次数即为a后面b的个数，然后把cntb的个数乘二，因为一个ab可以换bba，也就一个b换两个b。如果遇到b，则直接cntb++即可，不需要别的操作。

 

注：mod可以随时模，不会影响最后结果。

AC代码：

#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;

const int mod = 1e9 + 7;
char s[1000005];
long long ans, cntb;

int main(){
    scanf("%s", s);
    int len = strlen(s);
    for(int i = len - 1; i >= 0; i--){
        if(s[i] == 'a'){
            (ans += cntb) %= mod;
            (cntb *= 2) %= mod;
        }
        else cntb++;
    }
    printf("%lld
", ans % mod);
    return 0;
}