AtCoder ABC 字符串循环移位 题解复盘基本信息项目内容题目编号、来源AtCoder / 字符串循环移位训练层级A 字符串处理知识版块字符串、循环移位、字典序解题前・关键信号识别维度分析目标、约束、底层结构目标对字符串 S 进行任意次左移或右移找出能得到的字典序最小和最大的字符串约束|S| ≤ 1000底层结构所有可能的移位结果就是 S 的所有循环同构串共 n 种。数据规模n ≤ 1000O(n²) 暴力枚举即可。候选算法和依据字符串拼接 substr依据将 S 复制一份拼接成 SS则所有长度为 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。核心思想循环移位 在 SS 中取长度为 n 的连续子串。错因回溯1. 忘记考虑 0 次移位即原字符串本身但枚举 i0 时已经包含2. 左右移位本质相同都是循环移位不需要分别处理边界和易错点1. n1 时只有一个结果min 和 max 相同2. 字典序比较直接用 string 的和运算符即可3. 字符串长度 ≤ 1000O(n²) 不会超时。下次看到什么信号我应该想到这个方法看到「字符串循环移位 求字典序最值」用 SS 枚举所有长度为 n 的子串。AC 完整代码#includeiostream#includealgorithm#includecstring#includequeue#includevectorusingnamespacestd;intmain(){string s;cins;intns.length();string s1ss;string s2s,s3s;for(inti0;in;i){string temps1.substr(i,n);if(temps2){s2temp;}if(temps3){s3temp;}}couts2endl;couts3endl;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. n1 时只输出一个数2. 奇数和偶数长度的处理不同n 为偶数时第二段从 0 开始n 为奇数时第二段从 1 开始3. 使用deque模拟也是一种可行方法但找规律代码更短。下次看到什么信号我应该想到这个方法看到「每次追加 反转 n 很大」先手动模拟小数据找规律不要直接模拟。AC 完整代码#includeiostream#includealgorithm#includecstring#includedeque#includevectorusingnamespacestd;constintN1e6;intv[N],a[N];intmain(){intn;cinn;for(inti0;in;i){cinv[i];}for(intin-1;i0;i-2){coutv[i] ;}intk(n%20)?0:1;for(intik;in;i2){coutv[i] ;}return0;}AtCoder ABC 括号序列补全 题解复盘基本信息项目内容题目编号、来源AtCoder / 括号序列补全训练层级A 括号匹配知识版块括号匹配、贪心解题前・关键信号识别维度分析目标、约束、底层结构目标在字符串 S 中插入最少数量的(和)使其成为合法括号序列若有多个最短结果输出字典序最小的约束N ≤ 100底层结构统计无法匹配的)数量需要前面补(和多余的(数量需要后面补)。数据规模N ≤ 100O(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 完整代码#includeiostream#includealgorithm#includecstring#includedeque#includevectorusingnamespacestd;intmain(){intn;string s;cinns;intans0,res0;string result;for(inti0;in;i){if(s[i](){ans;}elseif(s[i])){if(ans0)ans--;elseres;}}for(inti0;ires;i){result(;}results;for(inti0;ians;i){result);}coutresult;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不再有 ABC3. 注意 “左移” 删除用栈模拟时从左到右扫描栈顶永远是当前字符串的末尾检查栈顶三个字符等价于检查当前字符串末尾是否存在 “ABC”。下次看到什么信号我应该想到这个方法看到「反复删除连续子串 删除后可能拼接产生新的子串」用栈模拟。AC 完整代码#includeiostream#includestringusingnamespacestd;intmain(){string s;cins;string st;for(charc:s){st.push_back(c);intlenst.size();if(len3st[len-3]Ast[len-2]Bst[len-1]C){st.pop_back();st.pop_back();st.pop_back();}}coutstendl;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 完整代码#includeiostream#includealgorithm#includestack#includevectorusingnamespacestd;constintN1e6;intv[N];intmain(){intn;cinn;vectorintst;st.reserve(n);for(inti0;in;i){cinv[i];}for(inti0;in;i){st.push_back(v[i]);while(st.size()4){intlenst.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;}}}coutst.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(总组数)。解题后・外化复盘维度内容实现结构 / 核心思路第一步维护一个dequepairlong long, long long dq存储(值, 数量)第二步对每个查询若 op1将(x, c)插入队尾若 op2从队头开始取球每次取当前队头组中min(剩余数量, c)个球累加贡献更新数量或弹出空组第三步输出每次取球的总和。核心思想相同值的球打包存储按需拆分取出。错因回溯1. 一开始用while(c–)储存每个数成功超时2. 取球时没有处理组内部分取出的情况3. 要用autox进行取值不能用auto x不然不能进行修改4. 数据范围大需要用long long答案可达 1e18。边界和易错点1.x可以等于 0此时取出球的贡献为 0仍需正常取出2.c可能大于当前组数量需要继续取下一组3. 取完一组后要及时pop_front()释放内存4. 答案可能超过int用long long输出。下次看到什么信号我应该想到这个方法看到「插入多个相同元素 按顺序取出指定数量 求总和」用队列存储(值, 数量)分组处理。AC 完整代码#includeiostream#includealgorithm#includedeque#includevectorusingnamespacestd;intmain(){intn;cinn;dequepairlonglong,longlongdq;while(n--){intop;cinop;if(op1){longlongx,c;cinxc;dq.push_back({x,c});}elseif(op2){longlongc;cinc;longlongans0;while(c0){autoxdq.front();longlongax.first;longlongbx.second;longlongtakemin(b,c);anstake*a;c-take;if(btake){dq.pop_front();}else{x.second-take;}}coutansendl;}}return0;}