Codeforces Round #411 D. Minimum number of steps【逆向思维+模拟】

题意:对于字符串s,其由’a’和’b’组成,对于”ab”的子串,我们可以把”ab”变成”bba” , 问最少的次数使得该操作不能继续。

思路:先模拟一下,对于abbab的操作,如果我先处理前面的ab,那么要执行5次,先处理后面的ab要处理4次,那么我们应该要事先处理后面的ab,再去处理前面的ab。 对于当前的a,所要执行的次数就是后面的b的数量。执行完该次后,b的数量*2。

数据分析: len∈[1,1e6]

复杂度分析:O(len)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD=1e9+7;
const int maxn= 1e6+50;
char str[maxn];

int main(void)
{
    scanf("%s",str+1);
    int len=strlen(str+1);
    ll ans=0,cntb=0;
    for(int i=len;i>=1;i--)
    {
        if(str[i]=='b') cntb++;
        else if(str[i]=='a')
        {
            ans=(ans%MOD+cntb%MOD)%MOD;
            cntb=(cntb%MOD*2);
        }
    }
    cout << ans << endl;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-21 13:38
8月实习会变多吗现在还没找到实习该怎么办...回复的hr好少
码农索隆:3-4月就要开始找,基本上6月份就发offer,7月初已经开始暑期实习了。
点赞 评论 收藏
分享
06-13 10:15
门头沟学院 Java
想去夏威夷的大西瓜在...:我也是27届,但是我现在研一下了啥项目都没有呀咋办,哎,简历不知道咋写
点赞 评论 收藏
分享
06-26 22:20
门头沟学院 Java
码农索隆:让你把简历发给她,她说一些套话,然后让你加一个人,说这个人给你改简历,然后开始卖课
我的求职精神状态
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-21 13:41
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务