【题意】 给出一个包含a和b的字符串，在串中碰到ab就将其变为bba，求最小变化次数。 【题解】 贪心思想，考虑从后往前处理得解最优，依次分别处理a和b即可。每次处理a相当于后面b数量倍增。
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”.
分析：
因为字符中要么是 a , 要么是 b ,可以得出最后的字符串必定是 bbbb…aaa….后接一个 b ,处理后会产生两个 b； 一个 b 需要一次处理碰到 a 才结算一次。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define mem(s,t) memset(s,t,sizeof(s)) #define D(v) cout<<#v<<" "<<v<<endl #define inf 0x3f3f3f3f const ll mod=1e9+7; int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif string s;cin>>s; ll cnt=0,ans=0; for(ll i=s.size()-1;i>=0;i--){ if(s[i]=='b'){ cnt++; cnt%=mod; }else { ans=(ans+cnt)%mod; cnt<<=1; cnt%=mod; } } cout<<ans%mod<<endl; return 0; }