题目描述

You are given a string s consisting of A, B and C.
Snuke wants to perform the following operation on s as many times as possible:
Choose a contiguous substring of s that reads ABC and replace it with BCA.
Find the maximum possible number of operations.
Constraints
1≤|s|≤200000
Each character of s is A, B and C.

输入

Input is given from Standard Input in the following format:
S

输出

Find the maximum possible number of operations.

样例输入

ABCABC

样例输出

3

提示

You can perform the operations three times as follows: ABCABC → BCAABC → BCABCA → BCBCAA. This is the maximum result.


参考:SZG大佬的题解

题意

在一个只包含A、B、C的字符串,有一种操作,可使 “ABC” 变成 ”BCA“,求字符串s的最多操作数。

1≤∣s∣≤200000

思路

  易得,该操作是将A与BC交换位置,可用 1、0分别代表“A”、“BC”。题意转化对一个只包含10的序列,

将所有的10更新01,即将所有的0放在1前面。假设序列中共有kk个0,每个0前面有ai​个1,则ans=∑​ai (1,k)​

  对于单独B、C,则可看作是两个序列分隔的标志。


 #include<bits/stdc++.h>
using namespace std;
const int N = 2e5+;
typedef long long ll;
char s[N];
int main()
{
scanf("%s",s);
ll cnt = ;
ll ans = , i = ;
int len = strlen(s);
while ( s[i] ) {
if( s[i] == 'A' ){
//printf("#1 %d \n" ,i);
cnt ++ ;
i++ ;
}else if ( s[i] == 'B' && s[i+] == 'C' ){
//printf("#2 %d \n" ,i);
ans = ans + cnt ;
i+= ;
if( i >= len ) break ;
}else if ( s[i] == 'B' || s[i] == 'C' || s[i] == '\0' ){
cnt = ;
i++ ;
}
}
//ans = ans + cnt ;
printf("%lld\n",ans);
}

ABC

最新文章

  1. Spring AOP详解
  2. 浏览器中Javascript单线程分析
  3. [转]Neural Networks, Manifolds, and Topology
  4. WCF Windows Service Using TopShelf and ServiceModelEx z
  5. C++学习45 流成员函数put输出单个字符 cin输入流详解 get()函数读入一个字符
  6. Codeforces Round #Pi (Div. 2) E. President and Roads 最短路+桥
  7. MQTT之 Mosquitto hello world的使用
  8. Qt添加窗口背景图片、Label图片显示、、Label文字显示
  9. Poj 2187 Beauty Contest_旋转凸包卡壳
  10. Android Phone和Pad UA区别
  11. BufferedReader 输出与BufferedWriter 输入的用法
  12. 百度api集合!
  13. 小兴趣:用python生成excel格式座位表
  14. Android自定义View的套路
  15. [JLOI2015]城池攻占
  16. Python常见面试题
  17. Redis 集群环境的搭建
  18. python之常用模块补充
  19. 《高性能SQL调优精要与案例解析》——10.4_SQL语句改写部分文档
  20. Qt_HelloWrold

热门文章

  1. final关键字的理解
  2. jenkins权限问题
  3. PyTricks-json dumps优雅的输出字典
  4. puppeteer注入cookie然后访问页面
  5. Linux设备驱动程序 之 工作队列
  6. 《你不知道的JavaScript(上)》笔记——关于this
  7. linux下如何交叉编译util-linux?
  8. windows 10中的ubuntu子系统安装桌面环境的方法
  9. 12 Flutter仿京东商城项目 商品列表页面请求数据、封装Loading Widget、上拉分页加载更多
  10. python中关于with以及contextlib的使用