codeforce 804B Minimum number of steps

71 阅读 0 评论 47 点赞

我是靠谱客的博主动听酸奶，最近开发中收集的这篇文章主要介绍codeforce 804B Minimum number of steps，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

We have a string of letters 'a' and 'b'. We want to perform some operations on it. On each step we choose one of substrings "ab" in the string and replace it with the string "bba". If we have no "ab" as a substring, our job is done. Print the minimum number of steps we should perform to make our job done modulo 109 + 7.

The string "ab" appears as a substring if there is a letter 'b' right after the letter 'a' somewhere in the string.

Input

The first line contains the initial string consisting of letters 'a' and 'b' only with length from 1 to 106.

Output

Print the minimum number of steps modulo 109 + 7.

   Examples 
 
     input 
   
ab

     output 
   
1

     input 
   
aab

     output 
   
3

Note

The first example: "ab" → "bba".

The second example: "aab" → "abba" → "bbaba" → "bbbbaa".

核心思路就是ab变成bba后相当于把a往右挪了一下并在a前面添加一个b

这样就好写了从右往左扫，如果遇到b就把b的个数+1，如果遇到a就把答案加上a后面b的个数并把b的个数翻倍

因为是从右往左扫的，这样就保证a往右挪的时候为后面的a添加的b的个数尽可能少，保证答案最小

不需要考虑一串a连在一起的情况，如果最右边全是a，那么不用管了对答案没贡献，就算左边的a挪过去也越不过这一串a

如果中间是一串a，那么右端点一定接了一个b，最右边的a挪过去后次右边又接上了b，这样就能保证所有的a都能挪到末尾恩核心思路就是ab变成bba后相当于把a往右挪了一下并在a前面添加一个b

这样就好写了从右往左扫，如果遇到b就把b的个数+1，如果遇到a就把答案加上a后面b的个数并把b的个数翻倍

因为是从右往左扫的，这样就保证a往右挪的时候为后面的a添加的b的个数尽可能少，保证答案最小

不需要考虑一串a连在一起的情况，如果最右边全是a，那么不用管了对答案没贡献，就算左边的a挪过去也越不过这一串a

如果中间是一串a，那么右端点一定接了一个b，最右边的a挪过去后次右边又接上了b，这样就能保证所有的a都能挪到末尾

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
char s[1000010];
int main()
{
    scanf(" %s",s);
    int len = strlen(s);
    long long cntb = 0, ans = 0;
    for(int i=len-1;i>=0;--i)
    {
        if(s[i] == 'a') {
            (ans += cntb) %= mod;
            (cntb *= 2) %= mod;
        } else {
            cntb++;
        }
    }
    printf("%I64dn", ans%mod);
}