一、写在前面兄弟们Day 25今天刷的四道题覆盖了数论、矩阵运算、字符串处理和动态规划都是蓝桥杯常考的基础题型。特别是第一题既约分数虽然是填空题但考察了欧拉函数的核心思想矩阵乘法那道题是模板题考场上直接默写就行回文串那道题用了一个很巧妙的技巧值得学习。今天的四道题既约分数 – 欧拉函数/互质计数矩阵相乘 – 矩阵乘法模板最长回文前后缀 – 回文串双指针优化翻转 – 动态规划状态压缩二、第一题既约分数难度⭐⭐2.1 题目大意求 1 到 2020 中满足分子分母互质最大公约数为1的分数有多少个。其实就是求有多少对 (i,j)其中 1 i,j 2020且 gcd(i,j) 1。2.2 解题思路这道题直接暴力枚举也能过因为 2020^2 大概是400万在Python里几秒钟就能跑完。但如果数据范围更大就需要用到欧拉函数优化。暴力思路双重循环枚举 i 和 j用math.gcd判断是否互质。2.3 代码实现importmath ans0foriinrange(1,2021):forjinrange(1,2021):ifmath.gcd(i,j)1:ans1print(ans)2.4 欧拉函数优化进阶如果数据范围更大比如 10^5 或 10^6暴力 O(n^2) 会超时。这时可以用欧拉函数 phi(i) 优化对于每个 i1 到 i 中与 i 互质的数有 phi(i) 个。而 i1 到 2020 中与 i 互质的数可以通过容斥原理计算。不过对于 2020 的数据范围暴力完全够用考场上怎么快怎么来。2.5 踩坑记录范围是1到2020注意range(1, 2021)才是1到2020math.gcd的用法Python 3.5 内置math.gcd不用自己写时间复杂度O(n^2 log n)对于小数据可以接受三、第二题矩阵相乘难度⭐⭐⭐3.1 题目大意给定两个矩阵 A 和 B求它们的乘积 C A x B。矩阵乘法的定义是C[i][j] sum(A[i][k] x B[k][j])。3.2 解题思路这题是矩阵乘法的模板题直接按照定义实现三重循环即可。需要注意矩阵 A 的列数必须等于矩阵 B 的行数否则无法相乘结果矩阵 C 的行数等于 A 的行数列数等于 B 的列数3.3 代码实现definputt(a,n):# 输入 n 行矩阵数据for_inrange(n):a.append(list(map(int,input().split())))defoutput(a):# 输出矩阵forxina:print(*x)defmul(a,b):# 矩阵乘法 C A x BNlen(a)# A的行数Mlen(a[0])# A的列数也是B的行数_Mlen(b)# B的行数Klen(b[0])# B的列数# 检查能否相乘ifM!_M:returnNone# 初始化结果矩阵c[[0]*Kfor_inrange(N)]# 三重循环计算foriinrange(N):forjinrange(K):forkinrange(M):c[i][j]a[i][k]*b[k][j]returnc# 主程序a[]b[]n,m,kmap(int,input().split())inputt(a,n)# 输入矩阵An行inputt(b,m)# 输入矩阵Bm行cmul(a,b)output(c)3.4 踩坑记录矩阵维度A 是 n x mB 是 m x k结果 C 是 n x k初始化结果矩阵[[0] * K for _ in range(N)]不能用[[0]*K]*N会导致引用问题输入顺序先输入 n, m, k然后输入 n 行 A 的数据再输入 m 行 B 的数据print(*x)用解包操作符*可以方便地输出列表元素用空格分隔四、第三题最长回文前后缀难度⭐⭐⭐⭐4.1 题目大意给定一个字符串 S找出一个前缀和一个后缀使得它们拼接后是一个回文串。要求输出这个回文串的最长长度。样例S “aababa”选择前缀 “aababa” 和后缀 “a”拼接得到 “aababaa”长度为7。4.2 解题思路这道题有一个非常巧妙的解法先求原字符串 S 和它的反转 S1 的最长公共前缀长度 i从两端向中间匹配中间剩余的部分分别求原字符串和反转字符串的最长回文子串长度最终答案 2*i max(原串中间部分的回文长度, 反转串中间部分的回文长度)核心思想前缀和后缀拼接成回文意味着前缀的反转等于后缀。所以从两端向中间找对称部分中间不匹配的部分再找最长回文。4.3 代码实现sinput().strip()s1s[::-1]# 反转字符串deffun(s):# 求字符串s的最长回文前缀长度# 从最大可能长度len(s)开始递减遍历到0foriinrange(len(s),-1,-1):# 奇偶长度字符串统一处理# 判断前i个字符是否为回文ifs[:i//2]s[i-1:(i-1)//2:-1]:returni# 第一步从两端找对称部分i0whileilen(s)ands[i]s1[i]:i1# 第二步首尾对称部分*2 中间部分的最长回文# max(原串中间部分的最长回文前缀, 反转串中间部分的最长回文前缀)print(2*imax(fun(s[i:]),fun(s1[i:])))4.4 关键技巧解析fun函数的实现很精妙枚举长度 i 从大到小s[:i//2]是前半部分s[i-1:(i-1)//2:-1]是后半部分的反转如果两者相等说明前 i 个字符构成回文这个写法统一处理了奇数和偶数长度的情况不需要分类讨论。4.5 踩坑记录反转字符串s[::-1]是Python最简洁的反转方式切片步长s[i-1:(i-1)//2:-1]表示从 i-1 开始到 (i-1)//2 结束不包含步长-1倒序对称部分计算2*i是因为前缀和后缀各贡献了 i 个字符max的使用要比较原串中间部分和反转串中间部分的回文长度取较大者五、第四题翻转难度⭐⭐⭐⭐5.1 题目大意有 n 个工件每个工件是一个长度为2的字符串。需要按顺序拼接这些工件拼接规则是如果前一个工件的尾部字符和后一个工件的首部字符相同则可以省略一个字符。每个工件可以选择翻转或不翻转。求拼接后的最小长度。5.2 解题思路这题是动态规划的经典应用与Day 24的翻转题是同一道题但状态转移的写法更简洁。状态设计dp[i][0]第 i 个工件不翻转时前 i 个工件拼接后的最小长度dp[i][1]第 i 个工件翻转时前 i 个工件拼接后的最小长度状态转移的核心计算当前工件与前一个工件的重叠长度然后取最小值。5.3 代码实现nint(input())s[]# 下标从1开始s[0]占位for_inrange(n):s.append(input().strip())# dp[i][j]前i个工件第i个工件状态为j的最小长度# j0表示不翻转j1表示翻转dp[[0]*2for_inrange(n1)]dp[1][0],dp[1][1]2,2# 第一个工件长度固定为2foriinrange(2,n1):forjinrange(2):# j表示当前工件的状态l0,l10,0# 重叠长度# 前一个工件不翻转尾部字符是 s[i-1][1]# 当前工件状态为j首部字符是 s[i][j]j0时不翻转j1时翻转ifs[i-1][1]s[i][j]:l01# 前一个工件翻转尾部字符是 s[i-1][0]ifs[i-1][0]s[i][j]:l11# 状态转移取两种情况的最小值# dp[i-1][0] - l0前一个工件不翻转减去重叠长度# dp[i-1][1] - l1前一个工件翻转减去重叠长度# 2当前工件的长度dp[i][j]min(dp[i-1][0]-l0,dp[i-1][1]-l1)2print(min(dp[n]))5.4 状态转移详解以dp[i][0]第 i 个不翻转为例当前工件不翻转首部字符是s[i][0]尾部是s[i][1]前一个工件不翻转时尾部是s[i-1][1]如果等于s[i][0]重叠1个字符前一个工件翻转时尾部是s[i-1][0]如果等于s[i][0]重叠1个字符取两种情况的最小值加上当前工件的2个字符5.5 两种写法的对比Day 24的写法dp[i][0]min(dp[i-1][0]2-(s[i-2][1]s[i-1][0]),dp[i-1][1]2-(s[i-2][0]s[i-1][0]))今天的写法l01ifs[i-1][1]s[i][j]else0l11ifs[i-1][0]s[i][j]else0dp[i][j]min(dp[i-1][0]-l0,dp[i-1][1]-l1)2两种写法等价但今天的写法更直观把重叠长度单独提取出来逻辑更清晰。5.6 踩坑记录下标从1开始s[0]是空字符串占位实际数据从s[1]开始翻转的含义s[i][0]和s[i][1]交换位置如 “ab” 翻转成 “ba”重叠长度只能是0或1因为每个工件长度为2最多重叠1个字符初始状态第一个工件无论翻不翻转长度都是2六、今日总结题目核心算法关键技巧易错点既约分数数论/GCD暴力枚举/欧拉函数数据范围、math.gcd矩阵相乘矩阵运算三重循环模板维度检查、初始化最长回文前后缀回文串对称部分中间回文切片技巧、反转字符串翻转动态规划状态设计重叠计算下标对应、翻转含义今天这四道题覆盖了数论基础GCD、互质、欧拉函数进阶矩阵运算模板题考场上直接默写字符串处理回文判断、切片技巧、反转动态规划状态设计、状态转移方程推导建议大家在理解的基础上把矩阵乘法和动态规划的代码背下来考场上直接套用可以节省大量时间。明天继续肝真题兄弟们一起加油如果觉得有帮助欢迎点赞收藏有问题评论区见
