鏈接：https://ac.nowcoder.com/acm/contest/888/G
來源：牛客網

題目描述

Gromah and LZR have entered the seventh level. There are a sequence of gemstones on the wall.
After some tries, Gromah discovers that one can take exactly three successive gemstones with the same types away from the gemstone sequence each time, after taking away three gemstones, the left two parts of origin sequence will be merged to one sequence in origin order automatically.
For example, as for "ATCCCTTG", we can take three 'C's away with two parts "AT", "TTG" left, then the two parts will be merged to "ATTTG", and we can take three 'T's next time.
The password of this level is the maximum possible times to take gemstones from origin sequence.
Please help them to determine the maximum times.

輸入描述:

Only one line containing a string ss_{}s?, denoting the gemstone sequence, where the same letters are regarded as the same types. 1≤∣s∣≤1051 \le |s| \le 10^51≤∣s∣≤105 ss_{}s? only contains uppercase letters.

輸出描述:

Print a non-negative integer in a single line, denoting the maximum times. 示例1

輸入

復制 ATCCCTTG

輸出

復制 2

說明

One possible way is that ‘‘ATCCCTTG?"??→??‘‘ATTTG?"??→‘‘AG?"``ATCCCTTG\," \; \rightarrow \; ``ATTTG\," \; \rightarrow ``AG\,"‘‘ATCCCTTG"→‘‘ATTTG"→‘‘AG". #include <cstdio> #include <iostream> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <queue> #include <vector> #include <map> using namespace std;#define ll long long #define eps 1e-9string s; int sign[100000 + 8], num[100000 + 8];int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>s;int len = s.size();int id = 0;int ans = 0;memset(num, 0, sizeof(num));for(int i = 0; i < len; i++){if(!i){sign[id] = s[i];num[id]++;}else{if(s[i] == sign[id]){num[id]++;if(num[id] == 3){num[id] = 0;id--;ans++;}}else{sign[++id] = s[i];num[id]++;}}}cout << ans << '\n';return 0; }

?

轉載于:https://www.cnblogs.com/RootVount/p/11368600.html

總結

以上是生活随笔為你收集整理的2019牛客暑期多校训练营（第八场）G Gemstones（模拟）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。