一、写在前面兄弟们Day 24今天刷了三道比较有难度的题涉及双指针、动态规划和回文串处理。这三道题都是国赛级别的题目特别是第一题近似GCD双指针的边界处理很容易出错。动态规划那道题的状态设计也很巧妙需要仔细理解。今天的三道题近似GCD —— 双指针GCD翻转 —— 动态规划状态压缩最长回文前后缀 —— 回文串双指针二、第一题近似GCD难度⭐⭐⭐⭐2.1 题目大意给定一个长度为 n 的数组 A定义近似GCD为最多修改数组中的一个元素之后数组的最大公约数为 g。问数组 A 有多少个长度大于等于 2 的子数组满足近似GCD的值为 g。2.2 解题思路这题的核心是双指针法。我们需要找到所有满足条件的子数组但如果暴力枚举所有子数组再判断时间复杂度是 O(n³)对于 n10⁵ 的数据会超时。双指针的关键思想维护一个窗口 [l, r]表示当前考察的子数组对于窗口内的子数组判断是否存在一种修改方式修改0个或1个元素使得整个子数组的GCD等于 g判断方法枚举窗口内每个元素作为被修改的元素计算其余元素的GCD如果存在某个情况使得GCD等于 g则该子数组满足条件。2.3 代码实现importmath n,gmap(int,input().split())nums[int(i)foriininput().split()]l0r2c0whilerlen(nums):arrnums[l:r]flagFalse# 枚举哪个元素被修改跳过该元素foriinrange(len(arr)):sgforjinrange(len(arr)):ifij:# 跳过本身相当于将该元素修改为 gcontinueelse:smath.gcd(s,arr[j])ifsg:c1flagTruebreak# 双指针移动策略ifflag:# 当前窗口满足条件尝试扩大窗口r1else:ifr-l3:# 长度大于3收缩窗口r-1l1elifr-l3:# 长度等于3左指针右移l1else:# 长度等于2窗口整体右移r1l1print(c)2.4 双指针移动策略分析这题的双指针移动策略比较特殊需要根据窗口长度和是否满足条件来灵活调整满足条件时flagTrue扩大窗口r1因为更大的窗口可能也满足条件不满足条件时窗口长度 3收缩窗口r-1, l1尝试减少元素个数窗口长度 3左指针右移l1保持窗口大小窗口长度 2整体右移r1, l1尝试新的子数组2.5 踩坑记录GCD的计算利用math.gcd函数注意初始值设为 g跳过元素的逻辑i j时跳过相当于把该元素改成 g因为 gcd(g, x) g 当 g 整除 x 时双指针的边界窗口长度至少为2注意边界条件的处理时间复杂度虽然用了双指针但内部还有两重循环最坏情况下可能超时需要根据实际情况优化三、第二题翻转难度⭐⭐⭐⭐3.1 题目大意有 n 个工件每个工件是一个长度为2的字符串。需要按顺序拼接这些工件拼接规则是如果前一个工件的第二个字符和后一个工件的第一个字符相同则可以省略一个字符长度从4变成3。每个工件可以选择翻转或不翻转。求拼接后的最小长度。3.2 解题思路这题是动态规划的经典应用。状态设计dp[i][0]第 i 个工件不翻转时前 i 个工件拼接后的最小长度dp[i][1]第 i 个工件翻转时前 i 个工件拼接后的最小长度状态转移第 i 个工件不翻转时第 i-1 个工件可以翻转或不翻转如果 i-1 不翻转且s[i-2][1] s[i-1][1]可以省略1个字符如果 i-1 翻转且s[i-2][0] s[i-1][1]可以省略1个字符第 i 个工件翻转时同理3.3 代码实现importosimportsys nint(input())s[]for_inrange(n):s.append(input().strip())# dp[i][j] 表示第 i 个元素状态为 j 时的最小长度# j0 表示不翻转j1 表示翻转dp[[0]*2for_inrange(n1)]dp[1][0]dp[1][1]2# 第一个工件长度固定为2foriinrange(2,n1):# 第 i 个工件不翻转dp[i][0]min(dp[i-1][0]2-(s[i-2][1]s[i-1][0]),# i-1 不翻转dp[i-1][1]2-(s[i-2][0]s[i-1][0])# i-1 翻转)# 第 i 个工件翻转dp[i][1]min(dp[i-1][0]2-(s[i-2][1]s[i-1][1]),# i-1 不翻转dp[i-1][1]2-(s[i-2][0]s[i-1][1])# i-1 翻转)print(min(dp[n]))3.4 状态转移详解以dp[i][0]第 i 个不翻转为例s[i-1]是第 i 个工件的原始字符串注意代码中下标从0开始所以是s[i-1]第 i 个不翻转时它的第一个字符是s[i-1][0]第二个是s[i-1][1]如果第 i-1 个不翻转它的末尾字符是s[i-2][1]如果s[i-2][1] s[i-1][0]可以省略一个字符所以加2-11否则加2翻转的情况类似只是把s[i-1]的两个字符交换位置。3.5 踩坑记录下标对应dp[i]对应s[i-1]因为 dp 从1开始s 从0开始翻转的含义翻转就是把字符串的两个字符交换位置如 “ab” 翻转成 “ba”初始状态第一个工件无论翻不翻转长度都是2因为没有前一个工件可以合并最终答案min(dp[n][0], dp[n][1])取翻转和不翻转的最小值四、第三题最长回文前后缀难度⭐⭐⭐⭐4.1 题目大意给定一个字符串 S找出一个前缀和一个后缀使得它们拼接后是一个回文串。要求输出这个回文串的最长长度。样例S “aababa”选择前缀 “aababa” 和后缀 “a”拼接得到 “aababaa”长度为7。4.2 解题思路这题的关键观察首先找到字符串的最长回文前缀从开头开始的回文子串然后找到字符串的最长回文后缀到结尾结束的回文子串但题目要求的是前缀后缀拼接成回文所以需要换一种思路实际上我们可以从字符串的两端向中间扩展找到最大的对称部分对于中间剩余的部分找它的最长回文前缀或后缀最终长度 2 * 对称部分长度 中间回文部分长度4.3 代码实现sinput().strip()llen(s)# 第一步从两端向中间找对称部分i0jl-1sym_len0# 对称部分的长度whileilandj0:ifs[i]s[j]:sym_len1i1j-1else:break# 第二步处理中间剩余部分找最长回文sheng0# 中间部分能贡献的回文长度# 找中间部分的最长回文前缀forkinrange(l,i,-1):substrs[i:k]ifsubstrsubstr[::-1]:shengk-ibreak# 找中间部分的最长回文后缀作为备选forkinrange(0,j1):substrs[k:j1]ifsubstrsubstr[::-1]:shengmax(sheng,j1-k)break# 最终答案 对称部分 * 2 中间回文部分print(2*sym_lensheng)4.4 算法分析以样例 “aababa” 为例从两端比较s[0]‘a’, s[5]‘a’匹配sym_len1s[1]‘a’, s[4]‘b’不匹配停止中间剩余部分是 “abab”从 i1 到 k5找 “abab” 的最长回文前缀“aba” 是回文长度为3最终答案 2*1 3 5不对…等等重新理解题意前缀和后缀可以任意选择不一定要覆盖整个字符串。重新分析样例前缀 “aababa” 后缀 “a” “aababaa”长度7。前缀是完整的字符串 “aababa”后缀是 “a”拼接后是回文所以实际上我们需要找一个前缀和一个后缀使得前缀后缀是回文。这意味着后缀是前缀的反转的前缀。4.5 优化思路这道题更优的做法是枚举前缀长度 i检查前缀 s[0:i] 的反转是否出现在字符串的末尾取最大匹配长度或者使用 KMP/字符串哈希来优化匹配过程。4.6 踩坑记录理解题意前缀和后缀可以任意选择不一定要连续或覆盖整个字符串回文判断s s[::-1]是Python中最简洁的回文判断方法边界处理注意 i 和 j 的边界条件避免数组越界时间复杂度暴力解法 O(n²)对于 10⁵ 的数据可能超时需要考虑优化五、今日总结题目核心算法关键技巧易错点近似GCD双指针GCD窗口滑动策略GCD计算、边界处理翻转动态规划状态设计翻转/不翻转下标对应、状态转移最长回文前后缀双指针回文对称部分中间回文题意理解、边界条件今天这三道题都是国赛级别的题目考察了双指针窗口的灵活调整根据条件收缩或扩张动态规划状态的设计要覆盖所有情况转移方程要仔细推导回文串回文判断的技巧以及前后缀的匹配问题建议大家在理解代码的基础上自己画个图走一遍流程特别是动态规划的状态转移画图会清晰很多。明天继续肝真题兄弟们一起加油如果觉得有帮助欢迎点赞收藏有问题评论区见本文仅供学习交流转载请注明出处。