首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。