备战蓝桥杯国赛【Day 24】

一、写在前面

兄弟们，Day 24！今天刷了三道比较有难度的题，涉及双指针、动态规划和回文串处理。这三道题都是国赛级别的题目，特别是第一题近似GCD，双指针的边界处理很容易出错。动态规划那道题的状态设计也很巧妙，需要仔细理解。

今天的三道题：

1. 近似GCD —— 双指针+GCD
2. 翻转 —— 动态规划+状态压缩
3. 最长回文前后缀 —— 回文串+双指针

二、第一题：近似GCD（难度：⭐⭐⭐⭐）

2.1 题目大意

给定一个长度为 n 的数组 A，定义"近似GCD"为：最多修改数组中的一个元素之后，数组的最大公约数为 g。问数组 A 有多少个长度大于等于 2 的子数组满足近似GCD的值为 g。

2.2 解题思路

这题的核心是双指针法。我们需要找到所有满足条件的子数组，但如果暴力枚举所有子数组再判断，时间复杂度是 O(n³)，对于 n=10⁵ 的数据会超时。

双指针的关键思想：

• 维护一个窗口 [l, r]，表示当前考察的子数组
• 对于窗口内的子数组，判断是否存在一种修改方式（修改0个或1个元素），使得整个子数组的GCD等于 g

判断方法：枚举窗口内每个元素作为"被修改的元素"，计算其余元素的GCD，如果存在某个情况使得GCD等于 g，则该子数组满足条件。

2.3 代码实现

importmath n,g=map(int,input().split())nums=[int(i)foriininput().split()]l=0r=2c=0whiler<=len(nums):arr=nums[l:r]flag=False# 枚举哪个元素被修改（跳过该元素）foriinrange(len(arr)):s=gforjinrange(len(arr)):ifi==j:# 跳过本身，相当于将该元素修改为 gcontinueelse:s=math.gcd(s,arr[j])ifs==g:c+=1flag=Truebreak# 双指针移动策略ifflag:# 当前窗口满足条件，尝试扩大窗口r+=1else:ifr-l>3:# 长度大于3，收缩窗口r-=1l+=1elifr-l==3:# 长度等于3，左指针右移l+=1else:# 长度等于2，窗口整体右移r+=1l+=1print(c)

2.4 双指针移动策略分析

这题的双指针移动策略比较特殊，需要根据窗口长度和是否满足条件来灵活调整：

1. 满足条件时（flag=True）：扩大窗口（r+=1），因为更大的窗口可能也满足条件
2. 不满足条件时：
   • 窗口长度 > 3：收缩窗口（r-=1, l+=1），尝试减少元素个数
   • 窗口长度 == 3：左指针右移（l+=1），保持窗口大小
   • 窗口长度 == 2：整体右移（r+=1, l+=1），尝试新的子数组

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 n=int(input())s=[]for_inrange(n):s.append(input().strip())# dp[i][j] 表示第 i 个元素状态为 j 时的最小长度# j=0 表示不翻转，j=1 表示翻转dp=[[0]*2for_inrange(n+1)]dp[1][0]=dp[1][1]=2# 第一个工件长度固定为2foriinrange(2,n+1):# 第 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-1=1，否则加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 解题思路

这题的关键观察：

1. 首先找到字符串的最长回文前缀（从开头开始的回文子串）
2. 然后找到字符串的最长回文后缀（到结尾结束的回文子串）
3. 但题目要求的是前缀+后缀拼接成回文，所以需要换一种思路

实际上，我们可以：

1. 从字符串的两端向中间扩展，找到最大的对称部分
2. 对于中间剩余的部分，找它的最长回文前缀或后缀
3. 最终长度 = 2 * 对称部分长度 + 中间回文部分长度

4.3 代码实现

s=input().strip()l=len(s)# 第一步：从两端向中间找对称部分i=0j=l-1sym_len=0# 对称部分的长度whilei<landj>=0:ifs[i]==s[j]:sym_len+=1i+=1j-=1else:break# 第二步：处理中间剩余部分，找最长回文sheng=0# 中间部分能贡献的回文长度# 找中间部分的最长回文前缀forkinrange(l,i,-1):substr=s[i:k]ifsubstr==substr[::-1]:sheng=k-ibreak# 找中间部分的最长回文后缀（作为备选）forkinrange(0,j+1):substr=s[k:j+1]ifsubstr==substr[::-1]:sheng=max(sheng,j+1-k)break# 最终答案 = 对称部分 * 2 + 中间回文部分print(2*sym_len+sheng)

4.4 算法分析

以样例 “aababa” 为例：

• 从两端比较：s[0]=‘a’, s[5]=‘a’，匹配，sym_len=1
• s[1]=‘a’, s[4]=‘b’，不匹配，停止
• 中间剩余部分是 “abab”（从 i=1 到 k=5）
• 找 “abab” 的最长回文前缀：“aba” 是回文，长度为3
• 最终答案 = 2*1 + 3 = 5？不对…

等等，重新理解题意：前缀和后缀可以任意选择，不一定要覆盖整个字符串。

重新分析样例：前缀 “aababa” + 后缀 “a” = “aababaa”，长度7。

• 前缀是完整的字符串 “aababa”
• 后缀是 “a”
• 拼接后是回文

所以实际上，我们需要找一个前缀和一个后缀，使得前缀+后缀是回文。这意味着后缀是前缀的反转的前缀。

4.5 优化思路

这道题更优的做法是：

1. 枚举前缀长度 i
2. 检查前缀 s[0:i] 的反转是否出现在字符串的末尾
3. 取最大匹配长度

或者使用 KMP/字符串哈希来优化匹配过程。

4.6 踩坑记录

• 理解题意：前缀和后缀可以任意选择，不一定要连续或覆盖整个字符串
• 回文判断：s == s[::-1]是Python中最简洁的回文判断方法
• 边界处理：注意 i 和 j 的边界条件，避免数组越界
• 时间复杂度：暴力解法 O(n²)，对于 10⁵ 的数据可能超时，需要考虑优化

五、今日总结

今天这三道题都是国赛级别的题目，考察了：

• 双指针：窗口的灵活调整，根据条件收缩或扩张
• 动态规划：状态的设计要覆盖所有情况，转移方程要仔细推导
• 回文串：回文判断的技巧，以及前后缀的匹配问题

建议大家在理解代码的基础上，自己画个图走一遍流程，特别是动态规划的状态转移，画图会清晰很多。

明天继续肝真题，兄弟们一起加油！💪

如果觉得有帮助，欢迎点赞收藏，有问题评论区见！

本文仅供学习交流，转载请注明出处。