【codeforces 805D】Minimum number of steps
2024-08-31 08:30:07
【题目链接】:http://codeforces.com/contest/805/problem/D
【题意】
给你一个字符串;
里面只包括a和b;
让你把里面的”ab”子串全都去掉;
方式是,
每次操作可以把”ab”替换成为”bba”;
直到整个字符串里面没有”ab”子串为止
【题解】
从ab开始
ab->bba
左边再加一个a的话
即aab
就相当于在bba左边加了一个a
abba
->
bbaba
bbbbaa
会发现就是最左边那个a一直在往右走;
更一般的;
会发现
每次b前面有x个a
则答案递增2 x −1
且这里的a会一直保留下去;
因为每次,所有的a都会跑到最右边去;
所以,遇到a就累加a的个数cnt;
遇到b就累加答案2 cnt −1
可以预处理出2^x;
也可以用快速幂求。
【Number Of WA】
0
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 1e6+100;
const LL MOD = 1e9+7;
LL ksm(int y)
{
LL t = 1,x = 2;
while (y)
{
if (y&1) t = (t*x)%MOD;
x = (x*x)%MOD;
y>>=1;
}
return t;
}
char s[N];
int main()
{
//freopen("F:\\rush.txt","r",stdin);
ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use
cin >> (s+1);
int len = strlen(s+1);
int numa = 0;
LL ans = 0;
rep1(i,1,len)
if (s[i]=='a')
numa++;
else
ans=(ans+(ksm(numa)-1)%MOD)%MOD;
cout << ans << endl;
return 0;
}
最新文章
- css样式表分类、选择器分类、css基础样式
- 自定义BadgeView
- Kruskal算法(二)之 C++详解
- PHP安装rrdtool扩展
- 转载网页博客:ie7bug:div容器下的img与div存在间隙
- ajax验证码检测
- Linux内核启动代码分析二之开发板相关驱动程序加载分析
- Search Insert Position--寻找插入点Given a sorted array and a target value, return the index if the target
- Jquery+ajax+json+servlet原理和Demo
- A - Wrestling Match HDU - 5971
- ViewGroup事件分发机制解析
- [Codeforces 961G]Partitions
- C#读写Excel的几种方法
- ESP32搭建1.VMware Workstation 12.5下Ubuntu16.04环境搭建(简易搭建)
- The connection string &#39;MysqlEF&#39; in the application&#39;s configuration file does not contain the require异常
- Ubuntu14.04下安装MATLAB后,通过命令行打开其图形界面
- Flask的集中控制
- 详细介绍C++STL:unordered_map
- 13、java中8中基本类型
- SCOJ 4493: DNA 最长公共子串 后缀自动机