【贪心】codeforces D. Minimum number of steps

http://codeforces.com/contest/805/problem/D

【思路】

要使最后的字符串不出现ab字样，贪心的从后面开始更换ab为bba，并且字符串以"abbbb..."形式出现的话，那么需要替换的次数就是b的个数，并且b的个数会翻倍，因此遍历查找存在"ab”子串的位置，然后开始替换，并记录下每个位置开始及其后面b的个数，然后更新答案即可。

【Accepted】

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <cmath>
 4 #include <vector>
 5 #include <algorithm>
 6 #include <set>
 7 #include <map>
 8 #include <queue>
 9 #include <deque>
10 #include <stack>
11 #include <string>
12 #include <bitset>
13 #include <ctime>
14 #include<algorithm>
15 #include<cstring>
16 using namespace std;
17 typedef long long ll;
18 const int maxn=1e6+2;
19 char str[maxn];
20 const ll mod=1e9+7;
21 int main()
22 {
23     while(~scanf("%s",str))
24     {
25         int l=strlen(str);
26         ll cnt=0;
27         ll ans=0;
28         for(int i=l-1;i>=0;i--)
29         {
30             if(str[i]=='b')
31             {
32                 cnt=(cnt+1)%mod;
33             }
34             else
35             {
36                 ans=(ans+cnt)%mod;
37                 cnt=(cnt*2%mod);
38             }
39         }
40         cout<<ans<<endl;
41     }
42     return 0;
43 }

View Code

【教训】

一开始cnt是int,ans=(ans+(ll)cnt)%mod,cnt直接在cnt*2的时候就爆long long了，然后把cnt换成了ll,结果还是爆了.....因为cnt最大都可能达到2^1e6，所以必须每次更新cnt之后都取模