首页 > 代码库 > Codeforces 805 D Minimum number of steps

Codeforces 805 D Minimum number of steps

题意:

给定一串字符串,将所有“ab”的子串替换为“bba”,询问多少次操作后没有子串“ab”。

分析:

观察可得,将“ab”替换为“bba”有两种结果。

①a移到了b的后面

②增加了一个b

而且最终的结果一定是前面全是b,后面全是a。

所以可以猜想从后往前数,设置一个B_cnt, 每当碰到一个b, 就b_cnt++, 碰到A, 就先加上一个b_cnt(因为每替换一次会将a移动后一格,所以要替换b_cnt次),再将b_cnt*2(多出b_cnt个b)。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 #include <map>
 5 #include <string>
 6 #include <iostream>
 7 #include <set>
 8 #include <sstream>
 9 #include <algorithm>
10 using namespace std;
11 const int MOD = 1e9 +7;
12 const int maxn = 1e6+5;
13 char str[maxn];
14 int main()
15 {
16     scanf("%s", str);
17     int len = strlen(str);
18     int cnt = 0;
19     int res = 0;
20     for(int i = len - 1; i >= 0; i--)
21     {
22         if(str[i] == b)
23         {
24             cnt++;
25         }
26         else
27         {
28             res += cnt;
29             res %= MOD;
30             cnt *= 2;
31             cnt %= MOD;
32         }
33     }
34     printf("%d\n", res);
35 }

 

Codeforces 805 D Minimum number of steps