一、写在前面兄弟们Day 23今天刷了一套第十四届蓝桥杯省赛的真题感觉整体难度比第十三届稍微友好一点但考察的知识点依然很全面。特别是填空题涉及到01背包虽然是经典题型但在考场上能不能快速想到建模方式还是很考验功底的。今天的四道题弹珠堆放 —— 前缀和找规律替换字符 —— 字符串切片替换偶串 —— 字符计数奇偶判断划分 —— 01背包变形二、第一题弹珠堆放难度⭐⭐2.1 题目大意小蓝有 20230610 颗磁力弹珠他对金字塔形状尤其感兴趣如下图所示高度为 1 的金字塔需要 1 颗弹珠高度为 2 的金字塔需要 4 颗弹珠高度为 3 的金字塔需要 10 颗弹珠高度为 4 的金字塔需要 20 颗弹珠。小蓝想要知道用他手里的弹珠可以摆出的最高的金字塔的高度是多少实际上题目简化后就是求1 13 136 13610 1361015这种形式的和。也就是先求自然数列再求前缀和再求前缀和的前缀和。2.2 解题思路这题数据范围是到 20230610直接暴力三重循环肯定超时。但观察规律发现第一层a [1, 2, 3, 4, 5, ...]—— 自然数列第二层b [1, 3, 6, 10, 15, ...]—— 自然数列的前缀和三角数第三层c [1, 4, 10, 20, 35, ...]—— 三角数的前缀和2.3 代码实现fromitertoolsimportaccumulate a[iforiinrange(1,2023)]blist(accumulate(a))# 第一层前缀和clist(accumulate(b))# 第二层前缀和# 验证一下规律# c[493] 20214480# c[494] 20337240print(494)2.4 踩坑记录accumulate的用法itertools.accumulate返回迭代器记得用list()转成列表。下标从0开始range(1, 2023)生成的是 1 到 2022共 2022 个数下标 0 到 2021。所以c[2021]才是第 2022 项。不用手写前缀和Python 内置的accumulate很方便不用自己写循环。三、第二题替换字符难度⭐⭐⭐3.1 题目大意给定一个字符串 s进行 m 次操作。每次操作给定区间 [l, r]把区间内所有的字符 x 替换成字符 y。3.2 解题思路这题是字符串切片替换的直接应用。Python 的字符串切片非常灵活s[:l-1]区间左边的部分s[l-1:r]区间内的部分注意题目下标从1开始Python从0开始s[r:]区间右边的部分区间内的替换直接用replace(x, y)即可。3.3 代码实现sinput().strip()mint(input())for_inrange(m):opinput().split()lint(op[0])rint(op[1])xop[2]yop[3]# 切片替换ss[:l-1]s[l-1:r].replace(x,y)s[r:]print(s)3.4 踩坑记录下标转换题目给的是1-based下标Python字符串是0-based所以l要减1r不用减因为切片s[a:b]是左闭右开的。字符串不可变Python字符串是不可变的每次操作都会生成新字符串。如果数据量很大可能会有性能问题但这题数据范围不大直接写就行。replace是全局替换s[l-1:r].replace(x, y)只会替换区间内的 x不会影响区间外。四、第三题偶串难度⭐⭐4.1 题目大意小蓝特别喜欢偶数当他看到字符串时他总数要检查一下是不是每种字符都是出现偶数次。给定一个字符串请帮助小蓝检查一下该字符串是否满足要求。4.2 解题思路通过 defaultdict 创建默认字段字符出现奇数次则输出NO偶数输出YES4.3 代码实现fromcollectionsimportdefaultdict dicdefaultdict(int)sinput().strip()foriins:dic[i]1flagTrueforvindic.values():ifv11:# 出现奇数次flagFalsebreakifflag:print(YES)else:print(NO)4.4 踩坑记录位运算判断奇偶v 1 1等价于v % 2 1位运算更快。defaultdict的用法不用先判断key是否存在直接dic[i] 1就行。注意输出格式题目要求输出 YES/NO不是 Yes/No。五、第四题划分难度⭐⭐⭐⭐5.1 题目大意给定 40 个数要把它们分成两个集合使得两个集合的权值差最小。权值定义为集合内所有数的乘积。最后输出两个集合权值的乘积。等等重新看题目——实际上是要求把数分成两组使得两组的和的差最小然后输出两组的和的乘积。5.2 解题思路这题是01背包的经典变形。假设所有数的总和为total我们要把数分成两组和分别为sum1和sum2满足sum1 sum2 total且|sum1 - sum2|最小。等价于找一个子集使其和尽量接近total / 2。这就是01背包问题背包容量为total // 2每个物品的体积和价值都是nums[i]求背包能装的最大价值最后答案 sum1 * sum2 max_sum * (total - max_sum)5.3 代码实现nums[5160,9191,6410,4657,7492,1531,8854,1253,4520,9231,1266,4801,3484,4323,5070,1789,2744,5959,9426,4433,4404,5291,2470,8533,7608,2935,8922,5273,8364,8819,7374,8077,5336,8495,5602,6553,3548,5267,9150,3309]bagsum(nums)//2n40# dp[i][j] 表示前i个数能否组成和为j# 这里优化为求最大价值dp[[0]*(bag1)for_inrange(n1)]foriinrange(1,n1):curnums[i-1]forjinrange(1,bag1):ifj-cur0:dp[i][j]max(dp[i-1][j-cur]cur,dp[i-1][j])else:dp[i][j]dp[i-1][j]amax(dp[n])# 一组的最大和bsum(nums)-a# 另一组的和print(a*b)5.4 优化版本滚动数组上面的代码用了二维DP其实可以优化成一维nums[5160,9191,6410,4657,7492,1531,8854,1253,4520,9231,1266,4801,3484,4323,5070,1789,2744,5959,9426,4433,4404,5291,2470,8533,7608,2935,8922,5273,8364,8819,7374,8077,5336,8495,5602,6553,3548,5267,9150,3309]bagsum(nums)//2dp[0]*(bag1)fornuminnums:forjinrange(bag,num-1,-1):dp[j]max(dp[j],dp[j-num]num)adp[bag]bsum(nums)-aprint(a*b)5.5 踩坑记录背包容量bag sum(nums) // 2不是sum(nums)。01背包 vs 完全背包这题每个数只能用一次是01背包内层循环要倒序遍历。dp数组初始化dp[0] 0其他初始化为0求最大值。答案计算最后输出的是a * b不是a b或abs(a - b)。六、今日总结题目核心算法关键技巧易错点弹珠堆放前缀和accumulate函数下标从0开始替换字符字符串切片replace切片拼接1-based转0-based偶串字符计数位运算判断奇偶输出格式YES/NO划分01背包滚动数组优化背包容量、倒序遍历省赛的题目相比国赛更套路一些很多题都是经典算法的直接应用。关键是看到题目能快速对应到算法这需要大量的刷题积累。明天继续肝真题兄弟们一起加油
备战蓝桥杯国赛【Day 23】
发布时间：2026/6/2 5:16:18
一、写在前面兄弟们Day 23今天刷了一套第十四届蓝桥杯省赛的真题感觉整体难度比第十三届稍微友好一点但考察的知识点依然很全面。特别是填空题涉及到01背包虽然是经典题型但在考场上能不能快速想到建模方式还是很考验功底的。今天的四道题弹珠堆放 —— 前缀和找规律替换字符 —— 字符串切片替换偶串 —— 字符计数奇偶判断划分 —— 01背包变形二、第一题弹珠堆放难度⭐⭐2.1 题目大意小蓝有 20230610 颗磁力弹珠他对金字塔形状尤其感兴趣如下图所示高度为 1 的金字塔需要 1 颗弹珠高度为 2 的金字塔需要 4 颗弹珠高度为 3 的金字塔需要 10 颗弹珠高度为 4 的金字塔需要 20 颗弹珠。小蓝想要知道用他手里的弹珠可以摆出的最高的金字塔的高度是多少实际上题目简化后就是求1 13 136 13610 1361015这种形式的和。也就是先求自然数列再求前缀和再求前缀和的前缀和。2.2 解题思路这题数据范围是到 20230610直接暴力三重循环肯定超时。但观察规律发现第一层a [1, 2, 3, 4, 5, ...]—— 自然数列第二层b [1, 3, 6, 10, 15, ...]—— 自然数列的前缀和三角数第三层c [1, 4, 10, 20, 35, ...]—— 三角数的前缀和2.3 代码实现fromitertoolsimportaccumulate a[iforiinrange(1,2023)]blist(accumulate(a))# 第一层前缀和clist(accumulate(b))# 第二层前缀和# 验证一下规律# c[493] 20214480# c[494] 20337240print(494)2.4 踩坑记录accumulate的用法itertools.accumulate返回迭代器记得用list()转成列表。下标从0开始range(1, 2023)生成的是 1 到 2022共 2022 个数下标 0 到 2021。所以c[2021]才是第 2022 项。不用手写前缀和Python 内置的accumulate很方便不用自己写循环。三、第二题替换字符难度⭐⭐⭐3.1 题目大意给定一个字符串 s进行 m 次操作。每次操作给定区间 [l, r]把区间内所有的字符 x 替换成字符 y。3.2 解题思路这题是字符串切片替换的直接应用。Python 的字符串切片非常灵活s[:l-1]区间左边的部分s[l-1:r]区间内的部分注意题目下标从1开始Python从0开始s[r:]区间右边的部分区间内的替换直接用replace(x, y)即可。3.3 代码实现sinput().strip()mint(input())for_inrange(m):opinput().split()lint(op[0])rint(op[1])xop[2]yop[3]# 切片替换ss[:l-1]s[l-1:r].replace(x,y)s[r:]print(s)3.4 踩坑记录下标转换题目给的是1-based下标Python字符串是0-based所以l要减1r不用减因为切片s[a:b]是左闭右开的。字符串不可变Python字符串是不可变的每次操作都会生成新字符串。如果数据量很大可能会有性能问题但这题数据范围不大直接写就行。replace是全局替换s[l-1:r].replace(x, y)只会替换区间内的 x不会影响区间外。四、第三题偶串难度⭐⭐4.1 题目大意小蓝特别喜欢偶数当他看到字符串时他总数要检查一下是不是每种字符都是出现偶数次。给定一个字符串请帮助小蓝检查一下该字符串是否满足要求。4.2 解题思路通过 defaultdict 创建默认字段字符出现奇数次则输出NO偶数输出YES4.3 代码实现fromcollectionsimportdefaultdict dicdefaultdict(int)sinput().strip()foriins:dic[i]1flagTrueforvindic.values():ifv11:# 出现奇数次flagFalsebreakifflag:print(YES)else:print(NO)4.4 踩坑记录位运算判断奇偶v 1 1等价于v % 2 1位运算更快。defaultdict的用法不用先判断key是否存在直接dic[i] 1就行。注意输出格式题目要求输出 YES/NO不是 Yes/No。五、第四题划分难度⭐⭐⭐⭐5.1 题目大意给定 40 个数要把它们分成两个集合使得两个集合的权值差最小。权值定义为集合内所有数的乘积。最后输出两个集合权值的乘积。等等重新看题目——实际上是要求把数分成两组使得两组的和的差最小然后输出两组的和的乘积。5.2 解题思路这题是01背包的经典变形。假设所有数的总和为total我们要把数分成两组和分别为sum1和sum2满足sum1 sum2 total且|sum1 - sum2|最小。等价于找一个子集使其和尽量接近total / 2。这就是01背包问题背包容量为total // 2每个物品的体积和价值都是nums[i]求背包能装的最大价值最后答案 sum1 * sum2 max_sum * (total - max_sum)5.3 代码实现nums[5160,9191,6410,4657,7492,1531,8854,1253,4520,9231,1266,4801,3484,4323,5070,1789,2744,5959,9426,4433,4404,5291,2470,8533,7608,2935,8922,5273,8364,8819,7374,8077,5336,8495,5602,6553,3548,5267,9150,3309]bagsum(nums)//2n40# dp[i][j] 表示前i个数能否组成和为j# 这里优化为求最大价值dp[[0]*(bag1)for_inrange(n1)]foriinrange(1,n1):curnums[i-1]forjinrange(1,bag1):ifj-cur0:dp[i][j]max(dp[i-1][j-cur]cur,dp[i-1][j])else:dp[i][j]dp[i-1][j]amax(dp[n])# 一组的最大和bsum(nums)-a# 另一组的和print(a*b)5.4 优化版本滚动数组上面的代码用了二维DP其实可以优化成一维nums[5160,9191,6410,4657,7492,1531,8854,1253,4520,9231,1266,4801,3484,4323,5070,1789,2744,5959,9426,4433,4404,5291,2470,8533,7608,2935,8922,5273,8364,8819,7374,8077,5336,8495,5602,6553,3548,5267,9150,3309]bagsum(nums)//2dp[0]*(bag1)fornuminnums:forjinrange(bag,num-1,-1):dp[j]max(dp[j],dp[j-num]num)adp[bag]bsum(nums)-aprint(a*b)5.5 踩坑记录背包容量bag sum(nums) // 2不是sum(nums)。01背包 vs 完全背包这题每个数只能用一次是01背包内层循环要倒序遍历。dp数组初始化dp[0] 0其他初始化为0求最大值。答案计算最后输出的是a * b不是a b或abs(a - b)。六、今日总结题目核心算法关键技巧易错点弹珠堆放前缀和accumulate函数下标从0开始替换字符字符串切片replace切片拼接1-based转0-based偶串字符计数位运算判断奇偶输出格式YES/NO划分01背包滚动数组优化背包容量、倒序遍历省赛的题目相比国赛更套路一些很多题都是经典算法的直接应用。关键是看到题目能快速对应到算法这需要大量的刷题积累。明天继续肝真题兄弟们一起加油
