备战蓝桥杯国赛【Day 23】

一、写在前面

兄弟们，Day 23！今天刷了一套第十四届蓝桥杯省赛的真题，感觉整体难度比第十三届稍微友好一点，但考察的知识点依然很全面。特别是填空题涉及到01背包，虽然是经典题型，但在考场上能不能快速想到建模方式，还是很考验功底的。

今天的四道题：

1. 弹珠堆放 —— 前缀和+找规律
2. 替换字符 —— 字符串切片+替换
3. 偶串 —— 字符计数+奇偶判断
4. 划分 —— 01背包变形

二、第一题：弹珠堆放（难度：⭐⭐）

2.1 题目大意

小蓝有 20230610 颗磁力弹珠，他对金字塔形状尤其感兴趣，如下图所示：

高度为 1 的金字塔需要 1 颗弹珠；
高度为 2 的金字塔需要 4 颗弹珠；
高度为 3 的金字塔需要 10 颗弹珠；
高度为 4 的金字塔需要 20 颗弹珠。

小蓝想要知道用他手里的弹珠可以摆出的最高的金字塔的高度是多少？

实际上题目简化后就是求：

1 1+3 1+3+6 1+3+6+10 1+3+6+10+15

这种形式的和。也就是先求自然数列，再求前缀和，再求前缀和的前缀和。

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)]b=list(accumulate(a))# 第一层前缀和c=list(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 代码实现

s=input().strip()m=int(input())for_inrange(m):op=input().split()l=int(op[0])r=int(op[1])x=op[2]y=op[3]# 切片替换s=s[:l-1]+s[l-1:r].replace(x,y)+s[r:]print(s)

3.4 踩坑记录

• 下标转换：题目给的是1-based下标，Python字符串是0-based，所以l要减1，r不用减（因为切片s[a:b]是左闭右开的）。
• 字符串不可变：Python字符串是不可变的，每次操作都会生成新字符串。如果数据量很大可能会有性能问题，但这题数据范围不大，直接写就行。
• replace是全局替换：s[l-1:r].replace(x, y)只会替换区间内的 x，不会影响区间外。

四、第三题：偶串（难度：⭐⭐）

4.1 题目大意

小蓝特别喜欢偶数，当他看到字符串时，他总数要检查一下是不是每种字符都是出现偶数次。给定一个字符串，请帮助小蓝检查一下该字符串是否满足要求。

4.2 解题思路

通过 defaultdict 创建默认字段，字符出现奇数次则输出NO，偶数输出YES

4.3 代码实现

fromcollectionsimportdefaultdict dic=defaultdict(int)s=input().strip()foriins:dic[i]+=1flag=Trueforvindic.values():ifv&1==1:# 出现奇数次flag=Falsebreakifflag: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]bag=sum(nums)//2n=40# dp[i][j] 表示前i个数，能否组成和为j# 这里优化为求最大价值dp=[[0]*(bag+1)for_inrange(n+1)]foriinrange(1,n+1):cur=nums[i-1]forjinrange(1,bag+1):ifj-cur>=0:dp[i][j]=max(dp[i-1][j-cur]+cur,dp[i-1][j])else:dp[i][j]=dp[i-1][j]a=max(dp[n])# 一组的最大和b=sum(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]bag=sum(nums)//2dp=[0]*(bag+1)fornuminnums:forjinrange(bag,num-1,-1):dp[j]=max(dp[j],dp[j-num]+num)a=dp[bag]b=sum(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)。

六、今日总结

省赛的题目相比国赛更"套路"一些，很多题都是经典算法的直接应用。关键是看到题目能快速对应到算法，这需要大量的刷题积累。

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