587 字
3 分钟
AtCoder ABC447_D: D - Take ABC 2 Editorial
题目链接
题目大意
给定一个长度不超过 且仅由字符 A、B 和 C 组成的字符串 。
每次操作你可以执行以下步骤：
- 在字符串中找到一个（不一定连续的）子序列
ABC。也就是说，找到三个下标 满足 ，并且 。 - 将这三个匹配的字符从原始字符串中删除。
- 剩下的字符按原本的相对顺序向左靠拢，重新拼接成一个新的字符串。
目标：求出对该字符串最多可以执行多少次上述操作。
解题思路
核心观察：每次删除 ABC 后，剩余字符的相对顺序不变，因此能形成 ABC 的三元组只取决于原串的位置关系。问题等价于在原串中选出最多个不相交的 (A, B, C)，满足索引严格递增。
贪心策略：总是使用最靠左的可行三元组。对每个 A，匹配它右侧最早的 B，再匹配该 B 右侧最早的 C。选择越靠左，给后面留下的可选字符越多，因此不会降低最优解。
实现方式：预处理 A/B/C 的位置数组，三指针线性扫描。
i从左到右枚举A。j向右移动到第一个满足B[j] > A[i]的位置。k向右移动到第一个满足C[k] > B[j]的位置。- 若
j或k到末尾则结束；否则计数并j++、k++继续。
时间复杂度 O(N)，空间复杂度 O(N)（存位置数组）。
代码实现
#include <bits/stdc++.h>using namespace std;const int N=1e6+10;int a[N], b[N], c[N]; //存储A, B, C字符的位置int idxa, idxb, idxc, res;//记录A, B, C有多少个string s;int main(){ cin>>s; int n=s.size(); for(int i=0;i<n;i++) { if(s[i]=='A') a[idxa++]=i; if(s[i]=='B') b[idxb++]=i; if(s[i]=='C') c[idxc++]=i; }//记录 A, B, C字符的位置 int j=0, k=0;//当前B和C的位置 for(int i=0;i<idxa;i++){ while(b[j]<a[i]&&j<idxb) j++;//如果目前B的位置在A面前, 就要++, 直到要在B的后面 while((c[k]<b[j]||c[k]<a[i])&&k<idxc) k++;//同理, 要在A和B的后面, 也要加上<idxc的限制 if(j==idxb||k==idxc) break;//到头了, 就说明没有再符合的了 res++;//没执行上一个语句, 就说明找到一个合理的 j++, k++;//j和k都要移向下一位, 同时i++ } printf("%d\n", res); return 0;} AtCoder ABC447_D: D - Take ABC 2 Editorial
https://shenyize.com/solutions/atcoder/abc447_d/