最少步

「爱情、让人受尽委屈。」 2022-04-12 12:16 219阅读 0赞

### 题目描述 ###

有一天课堂上老师出了一个难题给张三，题目：开头给你一个字符串，你可以把ab替换成bba，直到没有ab就算完成任务，然后问你最少替换次数是多少，结果%1000007  
输入  
输入一个字符串，只含有a与b（1<=字符串长度<=100000）  
输出  
输出最少替换次数  
样例输入  
aab  
样例输出  
3  
提示  
多组输入  
aab->abba->bbaba->bbbbaa

##### 分析： #####

由题目样例解析我们会发现，替换完后，最终结果肯定是前面都是b，后面都是a，所以我们在替换的时候就是取决于a后面有多少个b，  
例如 abb->bbab->bbbba 这里就是被替换了两次  
所以我们每次只要数每个a后面有多少个b即可  
因为我们考虑到从前面的a开始算的话，后面的a再替换前面也会受到影响，所以我们从后面的a开始处理，然后到每个a的时候去计算后面有多少个b，每找到一个a,b的个数变的规则也很容易看出就是翻了一倍变成2\*b，用个变量单独计算b的个数即可

#include"stdio.h"
    char a[100000000];
    
    int main()
    {
    
        long long count,i,j,l,countb;
        while(~scanf("%s",a))
        {  count=0;
           countb=0;
           l=strlen(a)-1;
           while(l>=0)
           {
               if(a[l]=='b')
               {
                   countb++;
               }
               else
               if(countb!=0)
                 {
                     count=(count+countb)%1000007;
                     countb=2*countb;
                     countb=countb%1000007;
                 }
                l--;
           }
    
         printf("%lld\n",count);
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，219人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法题】走迷宫、求最少步数

走迷宫、求最少步数 ![在这里插入图片描述][bfa4d443138c4d81bfdcba01a885c882.png] package bfs;

约定不等于承诺〃/ 2024年03月27日 10:39/ 0 赞/ 59 阅读

相关华为od机试 Java 【计算最少步数】

题目小明计划在周末去爬山。他有一份包含山峰高度的地图，其中 0 代表平地，而 1 到 9 表示不同的山峰高度。小明可以向上、下、左或右移动一步。但是，由于他不想爬得

╰半夏微凉°/ 2024年03月02日 09:29/ 0 赞/ 51 阅读

相关 nyoj 58 最少步数（bfs）

最少步数时间限制： 3000 ms | 内存限制： 65535 KB 难度： 4 描述这有一个迷宫，有0~8行和0~8列： 1,1,1,1,1,1,1,1,1

╰半橙微兮°/ 2024年02月17日 20:56/ 0 赞/ 42 阅读

相关华为od机试 Python 【计算最少步数】

题目小明计划在周末去爬山。他有一份包含山峰高度的地图，其中 0 代表平地，而 1 到 9 表示不同的山峰高度。小明可以向上、下、左或右移动一步。但是，由于他不想爬得

水深无声/ 2023年10月16日 11:58/ 0 赞/ 24 阅读

相关华为OD机试 C++【最少步数】

题目你在一个一维的数轴上，起始位置为0。你每次只能走2步或3步，无论是向左还是向右。有时你可能需要走到负坐标上去，才能最终到达你的目标位置。任务：给定一个坐标

た入场券/ 2023年10月15日 09:06/ 0 赞/ 9 阅读

相关 NYOJ 58-最少步数【DFS】

最少步数时间限制：3000 ms | 内存限制：65535 KB 难度：4 描述这有一个迷宫，有0~8行和0~8列： 1,1,1,1,1,1,1,1,1

旧城等待，/ 2022年09月24日 07:25/ 0 赞/ 143 阅读

相关最少步数

最少步数 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述给定一个数字n，我们可以进行3种操

川长思鸟来/ 2022年08月14日 05:37/ 0 赞/ 163 阅读

相关最少步数（bfs）

最少步数时间限制： 3000 ms | 内存限制： 65535 KB 难度： 4 描述这有一个迷宫，有0~8行和0~8列： 1,1,1,1,1,1,1,

蔚落/ 2022年08月02日 04:59/ 0 赞/ 141 阅读

相关 nyoj--58--最少步数(bfs&dfs)

最少步数时间限制： 3000 ms | 内存限制： 65535 KB 难度： 4 描述这有一个迷宫，有0~8行和0~8列： 1,1,1,1,1,1,1,

柔光的暖阳◎/ 2022年06月11日 06:45/ 0 赞/ 179 阅读

相关最少步

题目描述有一天课堂上老师出了一个难题给张三，题目：开头给你一个字符串，你可以把ab替换成bba，直到没有ab就算完成任务，然后问你最少替换次数是多少，结果%100000

「爱情、让人受尽委屈。」/ 2022年04月12日 12:16/ 0 赞/ 220 阅读