【Codeforces 805】D. Minimum number of steps

题目链接：http://codeforces.com/contest/805/problem/D

思路：从左到右进行遍历，当遇到b的时候，计算前面有多少个a， 然后求出转换从str[0]到这个位置的子字符串变化需要次数，是2^numA-1次， 写出下面代码，结果TLE。

#include <iostream> #include <cstdio> #include <cstring> using namespace std; char str[1000002]; const int mod= 1e9+7; __int64 findNum(int n){ __int64 num=1; while(n--){ num=num*2; num=num%mod; } return num-1; } int main() { int n; scanf("%s",str); int numA=0,numB=0; __int64 sum=0; for(int i=0;i<strlen(str);i++){ if(str[i]=='a'){ numA++; }else{ sum+=findNum(numA); sum=sum%mod; } } printf("%I64d\n",sum); return 0; }

可以发现findNum有很多重复计算，时间复杂度变成O(N^2)了， 优化后的代码为。

#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int mod= 1e9+7; int main() { int n; string s; cin>>s; int numA=0,numB=0,t=1; __int64 sum=0; for(int i=0;i<s.size();i++){ if(s[i]=='a'){ numA++; t=(t<<1)%mod; }else{ sum+=t-1; sum=sum%mod; } } printf("%I64d\n",sum); return 0; }