一、写在前面兄弟们Day 28明天就要上考场了今天把最后几道真题过一遍主要是查漏补缺。这几道题覆盖了二分查找、异或DP、质因数分解、集合运算和字符串处理都是国赛里容易出大题的方向。考前的最后一天心态要稳把该背的模板再默写一遍早点休息明天精神饱满地去考试今天的五道题成绩统计 —— 集合枚举子集2024!的因数 —— 质因数分解组合计数砍木棍 —— 二分查找括号字符串 —— 字符串二分查找选数异或 —— 异或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):bij a.add(b)print(len(a))2.4 踩坑记录集合去重set自动去重不用担心重复分数遍历时要转listfor j in list(a)因为遍历过程中会修改集合直接遍历会报错初始状态a {0}表示什么都不做总分为0数据范围小10道题最多 2^10 1024 种情况暴力完全够用三、第二题2024!的因数难度⭐⭐⭐⭐3.1 题目大意求有多少个不同的正整数 n使得 n^61 能整除 2024!。3.2 解题思路这道题考察唯一分解定理和组合计数。关键观察任何大于1的数都可以唯一分解为质因数的乘积如果 n^61 | 2024!那么 n 的每个质因数在 2024! 中的出现次数至少是 61 次设质数 p 在 2024! 中出现 v 次那么 n 中 p 的指数可以是 0, 1, 2, …, v//61所以算法步骤对 1 到 2024 的每个数分解质因数统计每个质数的总出现次数对于每个质数如果出现次数 v 61那么它在 n 中的指数有v//61 1种选择包括选0个所有质数的选择数相乘就是答案3.3 代码实现fromcollectionsimportCounterdefprime_factor(x):# 分解x的质因数结果存入全局字典di2whilei*ix:ifx%i0:d[i]1x//ielse:i1ifx1:d[x]1# 统计1到2024中每个质因数的出现次数dCounter()foriinrange(1,2025):prime_factor(i)res1forvind.values():curv//61ifcur0:# 出现次数大于61才可作为n的质因数res*(cur1)# 可选0到cur个共cur1种print(res)3.4 踩坑记录质因数分解对于每个数 i要分解到只剩1或一个大于sqrt的质数Counter的使用d Counter()初始化自动处理不存在的keyv//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 整除则减14.3 代码实现n,mmap(int,input().split())Llist(map(int,input().split()))defcheck(x):# 检查是否能把每根木棍都切成最长为x的小段且切割次数不超过mcnt0forainL:ifax:# 需要切成的段数 ceil(a / x)# 切割次数 段数 - 1cnt(a//x)ifa%x0:cnt-1# 正好整除少切一次returncntm# 二分查找l,r1,int(1e9)ansrwhilelr:mid(lr)1# 等价于 (l r) // 2ifcheck(mid):# mid可行尝试更小的值rmid-1ansmidelse:# mid不可行需要更大的值lmid1print(ans)4.4 二分查找模板这道题的二分模板非常经典建议背下来l,r最小值,最大值 ans最大值# 或最小值根据题意whilelr:mid(lr)1ifcheck(mid):ansmid rmid-1# 找更优解else:lmid1# 扩大范围4.5 踩坑记录check函数的逻辑切割次数 ceil(a / x) - 1不是a // x整除的情况如果a % x 0a // x就是段数切割次数要减1二分边界l从1开始长度至少为1r可以设一个足够大的值ans的更新只有check(mid)为True时才更新ans五、第四题括号字符串难度⭐⭐⭐⭐⭐5.1 题目大意给定一个字符串 S包含小写字母和括号。括号内的字母在查询时会被复制若干次。有 Q 个查询每个查询问某个字母在字符串的某个前缀中出现了多少次考虑括号扩展。5.2 解题思路这道题比较复杂涉及栈预处理二分查找。核心思想用栈处理括号匹配记录每个左括号对应的位置预处理每个字母出现的位置不考虑括号对于每个右括号计算它对应的左括号区间内每个字母被复制了多少次查询时用二分查找定位到前缀位置累加所有贡献5.3 代码实现importbisect Sinput().strip()Qint(input())# fa[j]字母j0-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]):pstack.pop()# 匹配的左括号位置forjinrange(26):iffa[j]andfa[j][-1]p:# 在括号区间内出现了该字母tbisect.bisect_left(fa[j],p)fb[j].append(fc[j]-t)else:# 普通字母numord(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):arrinput().strip()xint(arr[2:])# 查询的前缀长度numord(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 代码实现二维DPn,xmap(int,input().split())a[0]list(map(int,input().split()))# dp[i][j]前i个数异或得到j的方案数dp[[0]*64for_inrange(n1)]dp[0][0]1# 前0个数异或和为0有1种方案什么都不选mod998244353foriinrange(1,n1):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,xmap(int,input().split())a[0]list(map(int,input().split()))# 滚动数组只需要两行dp[[0]*64for_inrange(2)]dp[0][0]1mod998244353foriinrange(1,n1):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天我们覆盖了专题天数核心内容DFS专题Day 21, 24, 25回溯、环检测、连通块、双指针数论专题Day 22, 25, 26素数筛、逆元、约数、GCD、欧拉函数动态规划Day 23, 27, 28LIS、LCS、背包、线性DP、异或DP字符串Day 24, 25回文串、拼接、括号匹配二分查找Day 28二分答案、二分查找考前 checklist素数筛代码能默写出来LIS和LCS的DP模板记得二分查找的check函数会写滚动数组优化会套费马小定理求逆元的公式记得输入输出格式注意特别是多组数据带模运算的题每一步都取模考试策略先易后难填空题先做大题先拿暴力分注意时间不要在一道题上死磕超过30分钟检查边界数组越界、下标从0还是从1开始保持冷静遇到不会的题先跳过回头再做最后祝所有兄弟明天考试顺利都能拿到理想的成绩我们国赛见八、附录考前必背模板素数筛模板defselect(n):primes[True]*(n1)primes[0]primes[1]Falsei2whilei*in:ifprimes[i]:forainrange(i*i,n1,i):primes[a]Falsei1return[ifori,binenumerate(primes)ifb]LIS模板dp[1]*(n1)foriinrange(1,n1):forjinrange(1,i):ifa[j]a[i]:dp[i]max(dp[i],dp[j]1)二分答案模板l,r1,max_val ansmax_valwhilelr:mid(lr)1ifcheck(mid):ansmid rmid-1else:lmid1滚动数组模板dp[[0]*mfor_inrange(2)]dp[0][0]1foriinrange(1,n1):forjinrange(m):dp[i%2][j]...# 从 dp[(i-1)%2] 转移28天备战终成正果。兄弟们冲