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