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>usingnamespacestd;intmain(){string s;cin>>s;intn=s.length();string s1=s+s;string s2=s,s3=s;for(inti=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;return0;}
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>usingnamespacestd;constintN=1e6;intv[N],a[N];intmain(){intn;cin>>n;for(inti=0;i<n;i++){cin>>v[i];}for(inti=n-1;i>=0;i-=2){cout<<v[i]<<" ";}intk=(n%2==0)?0:1;for(inti=k;i<n;i+=2){cout<<v[i]<<" ";}return0;}
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>usingnamespacestd;intmain(){intn;string s;cin>>n>>s;intans=0,res=0;string result;for(inti=0;i<n;i++){if(s[i]=='('){ans++;}elseif(s[i]==')'){if(ans>0)ans--;elseres++;}}for(inti=0;i<res;i++){result+='(';}result+=s;for(inti=0;i<ans;i++){result+=')';}cout<<result;return0;}
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>usingnamespacestd;intmain(){string s;cin>>s;string st;for(charc:s){st.push_back(c);intlen=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;return0;}
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>usingnamespacestd;constintN=1e6;intv[N];intmain(){intn;cin>>n;vector<int>st;st.reserve(n);for(inti=0;i<n;i++){cin>>v[i];}for(inti=0;i<n;i++){st.push_back(v[i]);while(st.size()>=4){intlen=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';return0;}
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>usingnamespacestd;intmain(){intn;cin>>n;deque<pair<longlong,longlong>>dq;while(n--){intop;cin>>op;if(op==1){longlongx,c;cin>>x>>c;dq.push_back({x,c});}elseif(op==2){longlongc;cin>>c;longlongans=0;while(c>0){auto&x=dq.front();longlonga=x.first;longlongb=x.second;longlongtake=min(b,c);ans+=take*a;c-=take;if(b==take){dq.pop_front();}else{x.second-=take;}}cout<<ans<<endl;}}return0;}
