CodeForces - 804B Minimum number of steps（思维）

本文主要是介绍CodeForces - 804B Minimum number of steps（思维），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://codeforces.com/problemset/problem/804/B

题目大意：给你一个只包含 a, b 的字符串， 要求将其中的 "ab", 都变成 "bba"，问一直到最后没 "ab"子串，需要变化的最少次数。

思路：模拟肯定会超时，我们考虑找规律，最终的结果一定是所有的a在b的后面，所以我们的目的就是将所有的a移动到b的后面，然后对于每个 "ab"，变化后，b 的数量是翻倍的，接着就是，对于每个字符 a  后面后多少个 b ，就需要操作多少次。​​​​​​​

AC代码：

#include <bits/stdc++.h>
#define manx 100005
typedef long long ll;
const int mod = 1e9+7;
using namespace std;
ll poww(ll a, ll b)
{ll ans = 1;while(b){if (b & 1)  ans = (ans * a) % mod;a = (a * a) % mod;b >>= 1;}return ans;
}
int main()
{string s;while(cin >> s){ll len = s.length(), cnt = 0, ans = 0;for (int i = 0; i < len; i++){if (s[i]=='a') cnt++;else ans = (ans + poww(2,cnt) - 1) % mod;}printf("%lld\n",ans);}return 0;
}

 

这篇关于CodeForces - 804B Minimum number of steps（思维）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---