AtCoder ABC ：字符串循环移位 题解复盘 基本信息 项目 内容 题目编号、来源 AtCoder / 字符串循环移位 训练层级 A 字符串处理 知识版块 字符串、循环移位、字典序
解题前・关键信号识别 维度 分析 目标、约束、底层结构 目标 ：对字符串 S 进行任意次左移或右移，找出能得到的字典序最小和最大的字符串；约束 ：|S| ≤ 1000；底层结构 ：所有可能的移位结果就是 S 的所有循环同构串，共 n 种。数据规模 n ≤ 1000，O(n²) 暴力枚举即可。 候选算法和依据 字符串拼接 + substr；依据 ：将 S 复制一份拼接成 S+S，则所有长度为 n 的子串就是 S 的所有循环移位结果。 复杂度预判 时间复杂度 O(n²)，n ≤ 1000 完全可行；空间复杂度 O(n)。
解题后・外化复盘 维度 内容 实现结构 / 核心思路 第一步将 S 复制一份拼接成 T = S + S；第二步枚举 i 从 0 到 n-1，取 T.substr(i, n) 得到从第 i 个位置开始的循环移位结果；第三步用两个字符串 minStr 和 maxStr 分别记录字典序最小和最大的结果，每次比较更新；第四步输出 minStr 和 maxStr。核心思想 ：循环移位 = 在 S+S 中取长度为 n 的连续子串。 错因回溯 1. 忘记考虑 0 次移位（即原字符串本身），但枚举 i=0 时已经包含；2. 左右移位本质相同，都是循环移位，不需要分别处理； 边界和易错点 1. n=1 时，只有一个结果，min 和 max 相同；2. 字典序比较直接用 string 的<和>运算符即可；3. 字符串长度 ≤ 1000，O(n²) 不会超时。 下次看到什么信号，我应该想到这个方法 看到「字符串循环移位 + 求字典序最值 」，用 S+S 枚举所有长度为 n 的子串。
AC 完整代码 # include <iostream> # include <algorithm> # include <cstring> # include <queue> # include <vector> using namespace std; int main ( ) { string s; cin>> s; int n= s. length ( ) ; string s1= s+ s; string s2= s, s3= s; for ( int i= 0 ; i< n; i++ ) { string temp= s1. substr ( i, n) ; if ( temp< s2) { s2= temp; } if ( temp> s3) { s3= temp; } } cout<< s2<< endl; cout<< s3<< endl; return 0 ; } AtCoder ABC ：反转与追加 题解复盘 基本信息 项目 内容 题目编号、来源 AtCoder / 反转与追加 训练层级 B 找规律 知识版块 模拟、找规律、双端队列
解题前・关键信号识别 维度 分析 目标、约束、底层结构 目标 ：每次将新元素追加到序列末尾，然后整体反转，求最终序列；约束 ：n ≤ 2×10⁵，必须 O(n)；底层结构 ：直接模拟每次反转 O(n²) 会超时，需要找规律。数据规模 n ≤ 2×10⁵，O(n) 或 O(n log n) 可通过。 候选算法和依据 找规律 / 双端队列；依据 ：每次追加+反转，元素的相对顺序有固定模式，可以从最终序列的奇偶位置推导。 复杂度预判 时间复杂度 O(n)，空间复杂度 O(n)。
解题后・外化复盘 维度 内容 实现结构 / 核心思路 手动模拟几个例子，观察规律：最终序列中，奇数下标（从0开始） 的元素按原数组从后往前的顺序排列，偶数下标 的元素按原数组从前往后的顺序排列（或反过来，取决于 n 的奇偶性）。具体地：先输出原数组从 n-1 开始每隔一个取一个（倒序奇数位），再输出原数组从 0 或 1 开始每隔一个取一个（正序偶数位）。 错因回溯 1. 直接模拟每次反转，O(n²) 超时； 边界和易错点 1. n=1 时，只输出一个数；2. 奇数和偶数长度的处理不同：n 为偶数时，第二段从 0 开始；n 为奇数时，第二段从 1 开始；3. 使用deque模拟也是一种可行方法，但找规律代码更短。 下次看到什么信号，我应该想到这个方法 看到「每次追加 + 反转 + n 很大 」，先手动模拟小数据找规律，不要直接模拟。
AC 完整代码 # include <iostream> # include <algorithm> # include <cstring> # include <deque> # include <vector> using namespace std; const int N= 1e6 ; int v[ N] , a[ N] ; int main ( ) { int n; cin>> n; for ( int i= 0 ; i< n; i++ ) { cin>> v[ i] ; } for ( int i= n- 1 ; i>= 0 ; i-= 2 ) { cout<< v[ i] << " " ; } int k= ( n% 2 == 0 ) ? 0 : 1 ; for ( int i= k; i< n; i+= 2 ) { cout<< v[ i] << " " ; } return 0 ; } AtCoder ABC ：括号序列补全 题解复盘 基本信息 项目 内容 题目编号、来源 AtCoder / 括号序列补全 训练层级 A 括号匹配 知识版块 括号匹配、贪心
解题前・关键信号识别 维度 分析 目标、约束、底层结构 目标 ：在字符串 S 中插入最少数量的(和)，使其成为合法括号序列；若有多个最短结果，输出字典序最小的；约束 ：N ≤ 100；底层结构 ：统计无法匹配的)数量（需要前面补(）和多余的(数量（需要后面补)）。数据规模 N ≤ 100，O(N) 扫描即可。 候选算法和依据 括号匹配 + 贪心；依据 ：扫描 S，维护当前未匹配的(数量；遇到)且没有多余的(时，必须在前面补一个(；扫描结束后，多余的(需要在后面补)。 复杂度预判 时间复杂度 O(N)，空间复杂度 O(N)。
解题后・外化复盘 维度 内容 实现结构 / 核心思路 第一步初始化ans = 0（当前未匹配的(数量），res = 0（需要在前面补的(数量）；第二步遍历 S 每个字符：若为(，ans++；若为)，如果ans > 0则ans--匹配掉，否则res++（前面必须补一个(）；第三步遍历结束后，ans就是多余的(数量，需要在末尾补)；第四步输出：res个(+ 原 S +ans个)。 错因回溯 1. 想复杂了，以为要用 DP 或栈模拟插入位置；2. 没有理解“最短”意味着只需要补必要 的括号：前面补足够的(来匹配多余的)，后面补足够的)来匹配多余的(；3. 字典序最小：由于(比)字典序小，前面补(是唯一选择，后面补)也是唯一选择。 边界和易错点 1. 空字符串或全是(时，只需末尾补)；2. 全是)时，只需开头补(；3. 已经是合法序列时，输出原串；4.res是补在前面的(数量，ans是补在后面的)数量。 下次看到什么信号，我应该想到这个方法 看到「括号序列 + 插入最少括号使其合法 」，用扫描统计需要补的左括号和右括号数量。
AC 完整代码 # include <iostream> # include <algorithm> # include <cstring> # include <deque> # include <vector> using namespace std; int main ( ) { int n; string s; cin>> n>> s; int ans= 0 , res= 0 ; string result; for ( int i= 0 ; i< n; i++ ) { if ( s[ i] == '(' ) { ans++ ; } else if ( s[ i] == ')' ) { if ( ans> 0 ) ans-- ; else res++ ; } } for ( int i= 0 ; i< res; i++ ) { result+= '(' ; } result+= s; for ( int i= 0 ; i< ans; i++ ) { result+= ')' ; } cout<< result; return 0 ; } AtCoder ABC ：删除 ABC 题解复盘 基本信息 项目 内容 题目编号、来源 AtCoder / 删除 ABC 训练层级 A 栈模拟 知识版块 栈、字符串模拟
解题前・关键信号识别 维度 分析 目标、约束、底层结构 目标 ：反复删除字符串中最左边 的连续子串 “ABC”，直到不存在为止，输出最终字符串；约束 ：|S| ≤ 2×10⁵；底层结构 ：每次删除后，新的 “ABC” 可能在删除位置拼接产生，用栈模拟可以 O(n) 处理。数据规模 |S| ≤ 2×10⁵，O(n) 或 O(n log n) 均可。 候选算法和依据 栈模拟；依据 ：删除 “ABC” 后，新字符会拼接到删除位置的前后，可能形成新的 “ABC”，这类似于括号匹配的消除过程，可以用栈维护。 复杂度预判 时间复杂度 O(n)，每个字符入栈出栈一次；空间复杂度 O(n)。
解题后・外化复盘 维度 内容 实现结构 / 核心思路 第一步初始化空栈st；第二步遍历 S 中每个字符c：将c入栈；第三步检查栈顶三个字符是否为'A'、'B'、'C'，如果是则弹出这三个字符；第四步继续遍历，直到处理完所有字符；第五步输出栈中剩余字符。核心思想 ：每次删除 “ABC” 后，新拼接的位置只有栈顶可能形成新的 “ABC”，因此只需检查栈顶即可。 错因回溯 1. 直接对原字符串用find和erase操作，每次删除 O(n)，总复杂度 O(n²) 会超时；2. 使用栈后忘记检查删除后新栈顶是否形成新的 “ABC”，需要用循环持续检查；3. 边界条件：栈长度小于 3 时不能检查。 边界和易错点 1. 字符串长度小于 3 时，直接输出原串；2. 删除后可能连续形成新的 “ABC”（如AAABC→ 删除中间的 ABC 后变成A，不再有 ABC）；3. 注意 “左移” 删除：用栈模拟时，从左到右扫描，栈顶永远是当前字符串的末尾，检查栈顶三个字符等价于检查当前字符串末尾是否存在 “ABC”。 下次看到什么信号，我应该想到这个方法 看到「反复删除连续子串 + 删除后可能拼接产生新的子串 」，用栈模拟。
AC 完整代码 # include <iostream> # include <string> using namespace std; int main ( ) { string s; cin>> s; string st; for ( char c: s) { st. push_back ( c) ; int len= st. size ( ) ; if ( len>= 3 && st[ len- 3 ] == 'A' && st[ len- 2 ] == 'B' && st[ len- 1 ] == 'C' ) { st. pop_back ( ) ; st. pop_back ( ) ; st. pop_back ( ) ; } } cout<< st<< endl; return 0 ; } AtCoder ABC ：删除连续四个相同元素 题解复盘 基本信息 项目 内容 题目编号、来源 AtCoder / 删除连续四个相同元素 训练层级 B 栈模拟 知识版块 栈、模拟
解题前・关键信号识别 维度 分析 目标、约束、底层结构 目标 ：反复删除连续四个相同的数字，求最终序列的最小长度；约束 ：N ≤ 2×10⁵；底层结构 ：每次删除后，删除位置的前后元素会拼接，可能形成新的连续四个相同数字，用栈模拟可以 O(n) 处理。数据规模 N ≤ 2×10⁵，O(n) 或 O(n log n) 均可。 候选算法和依据 栈模拟；依据 ：删除四个相同数字后，新拼接的位置只有栈顶可能形成新的四个相同数字，因此只需检查栈顶四个元素即可。 复杂度预判 时间复杂度 O(n)，每个元素入栈出栈一次；空间复杂度 O(n)。
解题后・外化复盘 维度 内容 实现结构 / 核心思路 第一步初始化空栈st；第二步遍历 A 中每个元素x：将x入栈；第三步用 while 循环检查栈顶四个元素是否全部相等，如果是则弹出这四个元素并继续检查（因为删除后可能形成新的四个相同元素）；第四步输出栈的大小。核心思想 ：每次删除后，新拼接的位置只有栈顶可能形成新的可删除序列，因此只需检查栈顶即可。 错因回溯 1. 直接对原数组用erase操作，每次删除 O(n)，总复杂度 O(n²) 会超时；2. 用栈模拟时忘记用while循环持续检查删除后是否产生新的四个相同元素；3. 判断条件写错：不能连续== 边界和易错点 1. 栈大小小于 4 时不能检查；2. 删除后可能连续形成新的四个相同元素（如[1,1,1,1,1]→ 删除 4 个 1 后还剩 1 个 1，不会再删）；3. 四个元素相等必须是连续 的，栈顶四个元素天然是连续的；4.A_i的范围是 1 到 N，不需要特殊处理。 下次看到什么信号，我应该想到这个方法 看到「反复删除连续相同元素 + 删除后可能拼接产生新的可删除序列 」，用栈模拟。
AC 完整代码 # include <iostream> # include <algorithm> # include <stack> # include <vector> using namespace std; const int N= 1e6 ; int v[ N] ; int main ( ) { int n; cin>> n; vector< int > st; st. reserve ( n) ; for ( int i= 0 ; i< n; i++ ) { cin>> v[ i] ; } for ( int i= 0 ; i< n; i++ ) { st. push_back ( v[ i] ) ; while ( st. size ( ) >= 4 ) { int len= st. size ( ) ; if ( st[ len- 4 ] == st[ len- 3 ] && st[ len- 3 ] == st[ len- 2 ] && st[ len- 2 ] == st[ len- 1 ] ) { st. pop_back ( ) ; st. pop_back ( ) ; st. pop_back ( ) ; st. pop_back ( ) ; } else { break ; } } } cout<< st. size ( ) << '\n' ; return 0 ; } AtCoder ABC ：圆柱体取球 题解复盘 基本信息 项目 内容 题目编号、来源 AtCoder / 圆柱体取球 训练层级 B 队列模拟 知识版块 队列、贪心、模拟
解题前・关键信号识别 维度 分析 目标、约束、底层结构 目标 ：维护一个队列，支持两种操作：1）在队尾插入 c 个值为 x 的球；2）从队头取出 c 个球，输出它们的和；约束 ：Q ≤ 2×10⁵，c ≤ 1e9；底层结构 ：用队列存储每组相同值的球(值, 数量)，取球时按顺序从队头取出。数据规模 Q ≤ 2×10⁵，总插入次数 ≤ 2×10⁵，每组球用 pair 存储，O(总组数) 可通过。 候选算法和依据 队列 + 贪心；依据 ：球永远保持插入顺序，取球时从左到右取，用队列维护每组相同值的球即可。 复杂度预判 时间复杂度 O(总组数)，空间复杂度 O(总组数)。
解题后・外化复盘 维度 内容 实现结构 / 核心思路 第一步维护一个deque<pair<long long, long long>> dq，存储(值, 数量)；第二步对每个查询：若 op=1，将(x, c)插入队尾；若 op=2，从队头开始取球，每次取当前队头组中min(剩余数量, c)个球，累加贡献，更新数量或弹出空组；第三步输出每次取球的总和。核心思想 ：相同值的球打包存储，按需拆分取出。 错因回溯 1. 一开始用while(c–)储存每个数，成功超时；2. 取球时没有处理组内部分取出的情况；3. 要用auto&x进行取值，不能用auto x不然不能进行修改；4. 数据范围大，需要用long long（答案可达 1e18）。 边界和易错点 1.x可以等于 0，此时取出球的贡献为 0，仍需正常取出；2.c可能大于当前组数量，需要继续取下一组；3. 取完一组后要及时pop_front()释放内存；4. 答案可能超过int，用long long输出。 下次看到什么信号，我应该想到这个方法 看到「插入多个相同元素 + 按顺序取出指定数量 + 求总和 」，用队列存储(值, 数量)分组处理。
AC 完整代码 # include <iostream> # include <algorithm> # include <deque> # include <vector> using namespace std; int main ( ) { int n; cin>> n; deque< pair< long long , long long >> dq; while ( n-- ) { int op; cin>> op; if ( op== 1 ) { long long x, c; cin>> x>> c; dq. push_back ( { x, c} ) ; } else if ( op== 2 ) { long long c; cin>> c; long long ans= 0 ; while ( c> 0 ) { auto & x= dq. front ( ) ; long long a= x. first; long long b= x. second; long long take= min ( b, c) ; ans+= take* a; c-= take; if ( b== take) { dq. pop_front ( ) ; } else { x. second-= take; } } cout<< ans<< endl; } } return 0 ; } 
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
