备战蓝桥杯国赛【最终篇】

一、写在前面

兄弟们，Day 28，明天就要上考场了！

今天把最后几道真题过一遍，主要是查漏补缺。这几道题覆盖了二分查找、异或DP、质因数分解、集合运算和字符串处理，都是国赛里容易出大题的方向。考前的最后一天，心态要稳，把该背的模板再默写一遍，早点休息，明天精神饱满地去考试！

今天的五道题：

1. 成绩统计 —— 集合+枚举子集
2. 2024!的因数 —— 质因数分解+组合计数
3. 砍木棍 —— 二分查找
4. 括号字符串 —— 字符串+二分查找
5. 选数异或 —— 异或DP+滚动数组

二、第一题：成绩统计（难度：⭐⭐）

2.1 题目大意

有10道题，分值分别是 5,5,10,10,15,15,20,20,25,25。问能组成多少种不同的总分。

2.2 解题思路

这道题数据范围很小，直接枚举所有子集即可。用集合set来存储所有可能的总分，自动去重。

核心思想：对于每道题，可以选择"做"或"不做"，然后累加到总分中。用集合记录所有可能的总分，最后输出集合的大小。

2.3 代码实现

scores=[5,5,10,10,15,15,20,20,25,25]# 用集合存储所有可能的总分a={0}foriinscores:# 对于当前分数i，可以选择加或不加# 遍历当前集合中的所有分数，加上i后形成新的分数forjinlist(a):b=i+j a.add(b)print(len(a))

2.4 踩坑记录

• 集合去重：set自动去重，不用担心重复分数
• 遍历时要转list：for j in list(a)，因为遍历过程中会修改集合，直接遍历会报错
• 初始状态：a = {0}，表示什么都不做，总分为0
• 数据范围小：10道题，最多 2^10 = 1024 种情况，暴力完全够用

三、第二题：2024!的因数（难度：⭐⭐⭐⭐）

3.1 题目大意

求有多少个不同的正整数 n，使得 n^61 能整除 2024!。

3.2 解题思路

这道题考察唯一分解定理和组合计数。

关键观察：

1. 任何大于1的数都可以唯一分解为质因数的乘积
2. 如果 n^61 | 2024!，那么 n 的每个质因数在 2024! 中的出现次数至少是 61 次
3. 设质数 p 在 2024! 中出现 v 次，那么 n 中 p 的指数可以是 0, 1, 2, …, v//61

所以算法步骤：

1. 对 1 到 2024 的每个数分解质因数，统计每个质数的总出现次数
2. 对于每个质数，如果出现次数 v >= 61，那么它在 n 中的指数有v//61 + 1种选择（包括选0个）
3. 所有质数的选择数相乘，就是答案

3.3 代码实现

fromcollectionsimportCounterdefprime_factor(x):# 分解x的质因数，结果存入全局字典di=2whilei*i<=x:ifx%i==0:d[i]+=1x//=ielse:i+=1ifx>1:d[x]+=1# 统计1到2024中每个质因数的出现次数d=Counter()foriinrange(1,2025):prime_factor(i)res=1forvind.values():cur=v//61ifcur>0:# 出现次数大于61才可作为n的质因数res*=(cur+1)# 可选0到cur个，共cur+1种print(res)

3.4 踩坑记录

• 质因数分解：对于每个数 i，要分解到只剩1或一个大于sqrt的质数
• Counter的使用：d = Counter()初始化，自动处理不存在的key
• v//61 + 1：包括选0个的情况，所以是cur + 1不是cur
• 数据范围：2024! 的质因数很多，但大部分质数的出现次数不到61，只有小部分需要计算

四、第三题：砍木棍（难度：⭐⭐⭐⭐）

4.1 题目大意

有 n 根木棍，长度分别为 L[i]。可以把任意一根木棍切成两段（整数长度），最多切 m 次。要求切完后，最长的那根木棍尽可能短。求这个最短的最大长度。

4.2 解题思路

这是典型的二分答案问题。

“最长的最短”、"最大的最小"这类问题，通常都可以用二分查找解决。

二分查找的对象：最终每根木棍的最大长度 x。

check函数：判断是否能通过不超过 m 次切割，使得所有木棍的长度都不超过 x。

• 对于长度为 a 的木棍，要切成每段不超过 x，需要的切割次数 =ceil(a / x) - 1
• 等价于：a // x（如果 a 能被 x 整除则减1）

4.3 代码实现

n,m=map(int,input().split())L=list(map(int,input().split()))defcheck(x):# 检查是否能把每根木棍都切成最长为x的小段，且切割次数不超过mcnt=0forainL:ifa>x:# 需要切成的段数 = ceil(a / x)# 切割次数 = 段数 - 1cnt+=(a//x)ifa%x==0:cnt-=1# 正好整除，少切一次returncnt<=m# 二分查找l,r=1,int(1e9)ans=rwhilel<=r:mid=(l+r)>>1# 等价于 (l + r) // 2ifcheck(mid):# mid可行，尝试更小的值r=mid-1ans=midelse:# mid不可行，需要更大的值l=mid+1print(ans)

4.4 二分查找模板

这道题的二分模板非常经典，建议背下来：

l,r=最小值,最大值 ans=最大值# 或最小值，根据题意whilel<=r:mid=(l+r)>>1ifcheck(mid):ans=mid r=mid-1# 找更优解else:l=mid+1# 扩大范围

4.5 踩坑记录

• check函数的逻辑：切割次数 =ceil(a / x) - 1，不是a // x
• 整除的情况：如果a % x == 0，a // x就是段数，切割次数要减1
• 二分边界：l从1开始（长度至少为1），r可以设一个足够大的值
• ans的更新：只有check(mid)为True时才更新ans

五、第四题：括号字符串（难度：⭐⭐⭐⭐⭐）

5.1 题目大意

给定一个字符串 S，包含小写字母和括号。括号内的字母在查询时会被"复制"若干次。有 Q 个查询，每个查询问某个字母在字符串的某个前缀中出现了多少次（考虑括号扩展）。

5.2 解题思路

这道题比较复杂，涉及栈+预处理+二分查找。

核心思想：

1. 用栈处理括号匹配，记录每个左括号对应的位置
2. 预处理每个字母出现的位置（不考虑括号）
3. 对于每个右括号，计算它对应的左括号区间内每个字母被"复制"了多少次
4. 查询时，用二分查找定位到前缀位置，累加所有贡献

5.3 代码实现

importbisect S=input().strip()Q=int(input())# fa[j]：字母j（0-25对应a-z）出现的所有位置（不考虑括号）fa=[[]for_inrange(26)]# fb[j]：字母j在每个括号区间内的出现次数fb=[[]for_inrange(26)]# fc[j]：字母j到目前为止的总出现次数（不考虑括号）fc=[0]*26# fd[j]：字母j的括号区间个数fd=[0]*26stack=[]# 栈，存储左括号的位置foriinrange(len(S)):ifS[i]=='(':stack.append(i)elifS[i]==')':p=stack.pop()# 匹配的左括号位置forjinrange(26):iffa[j]andfa[j][-1]>p:# 在括号区间内出现了该字母t=bisect.bisect_left(fa[j],p)fb[j].append(fc[j]-t)else:# 普通字母num=ord(S[i])-ord('a')fa[num].append(i)fc[num]+=1# 对fb排序，方便二分查询foriinrange(26):fb[i].sort()fd[i]=len(fb[i])# 处理查询for_inrange(Q):arr=input().strip()x=int(arr[2:])# 查询的前缀长度num=ord(arr[0])-ord('a')# 查询的字母# 总次数 = 括号区间内的次数 + 括号外的次数print(fd[num]-bisect.bisect_left(fb[num],x))

5.4 踩坑记录

• 栈处理括号：遇到(入栈，遇到)出栈，匹配最近的左括号
• bisect_left：找到第一个大于等于目标值的位置
• ord转换：ord('a') = 97，所以ord(S[i]) - 97得到 0-25
• 预处理排序：fb[i].sort()必须在查询前完成

六、第五题：选数异或（难度：⭐⭐⭐⭐）

6.1 题目大意

给定 n 个数和一个目标值 x，问有多少种选法（每个数可选可不选），使得选出的数的异或和等于 x。

6.2 解题思路

这道题是异或DP的经典模型。

状态定义：dp[i][j]表示前 i 个数，异或和为 j 的方案数。

状态转移：对于第 i 个数 a[i]，有两种选择：

• 不选：异或和保持 j，方案数dp[i-1][j]
• 选：异或和变成j ^ a[i]，方案数dp[i-1][j ^ a[i]]

所以：dp[i][j] = dp[i-1][j] + dp[i-1][j ^ a[i]]

注意：异或和的范围是 0 到 63（因为数字范围限制），所以第二维只需要开64。

6.3 代码实现（二维DP）

n,x=map(int,input().split())a=[0]+list(map(int,input().split()))# dp[i][j]：前i个数异或得到j的方案数dp=[[0]*64for_inrange(n+1)]dp[0][0]=1# 前0个数，异或和为0，有1种方案（什么都不选）mod=998244353foriinrange(1,n+1):forjinrange(64):# 不选a[i]：方案数dp[i-1][j]# 选a[i]：方案数dp[i-1][j ^ a[i]]dp[i][j]=(dp[i-1][j]+dp[i-1][j^a[i]])%modprint(dp[n][x])

6.4 代码实现（滚动数组优化）

因为dp[i]只依赖dp[i-1]，可以用滚动数组把空间从 O(n64) 降到 O(264)：

n,x=map(int,input().split())a=[0]+list(map(int,input().split()))# 滚动数组，只需要两行dp=[[0]*64for_inrange(2)]dp[0][0]=1mod=998244353foriinrange(1,n+1):forjinrange(64):dp[i%2][j]=(dp[(i-1)%2][j]+dp[(i-1)%2][j^a[i]])%modprint(dp[n%2][x])

6.5 状态转移详解

以dp[i][j]为例：

• 不选第 i 个数：异或和还是 j，方案数 =dp[i-1][j]
• 选第 i 个数：原来的异或和应该是j ^ a[i]（因为j ^ a[i] ^ a[i] = j），方案数 =dp[i-1][j ^ a[i]]

两者相加，就是dp[i][j]。

6.6 踩坑记录

• 异或的性质：j ^ a[i] ^ a[i] = j，所以选 a[i] 时，原来的异或和应该是j ^ a[i]
• 滚动数组下标：i % 2在 0 和 1 之间交替
• 初始状态：dp[0][0] = 1，前0个数异或为0有1种方案
• 取模：998244353是常见的模数

七、考前最后的话

兄弟们，28天的备战日记到今天就要告一段落了。回顾一下这28天，我们覆盖了：

考前 checklist：

• 素数筛代码能默写出来
• LIS和LCS的DP模板记得
• 二分查找的check函数会写
• 滚动数组优化会套
• 费马小定理求逆元的公式记得
• 输入输出格式注意（特别是多组数据）
• 带模运算的题，每一步都取模

考试策略：

1. 先易后难：填空题先做，大题先拿暴力分
2. 注意时间：不要在一道题上死磕超过30分钟
3. 检查边界：数组越界、下标从0还是从1开始
4. 保持冷静：遇到不会的题先跳过，回头再做

最后，祝所有兄弟明天考试顺利，都能拿到理想的成绩！我们国赛见！

八、附录：考前必背模板

素数筛模板

defselect(n):primes=[True]*(n+1)primes[0]=primes[1]=Falsei=2whilei*i<=n:ifprimes[i]:forainrange(i*i,n+1,i):primes[a]=Falsei+=1return[ifori,binenumerate(primes)ifb]

LIS模板

dp=[1]*(n+1)foriinrange(1,n+1):forjinrange(1,i):ifa[j]<a[i]:dp[i]=max(dp[i],dp[j]+1)

二分答案模板

l,r=1,max_val ans=max_valwhilel<=r:mid=(l+r)>>1ifcheck(mid):ans=mid r=mid-1else:l=mid+1

滚动数组模板

dp=[[0]*mfor_inrange(2)]dp[0][0]=1foriinrange(1,n+1):forjinrange(m):dp[i%2][j]=...# 从 dp[(i-1)%2] 转移

28天备战，终成正果。兄弟们，冲！