上一期：2023 上半年周赛题目总结

大家好，又到了半年一度的周赛总结时间！

我从下半年的 $40$ 场周赛，共计 $160$ 道题目中，整理出了「能学到算法套路」的题目，大家可以针对练习。

一、技巧类题目

包含滑动窗口、二分答案等比较套路的算法。

这些技巧相对容易掌握，也是周赛常客，推荐优先训练。

常见于周赛第二题（约占 $20\%$）、第三题（约占 $33\%$）和第四题（约占 $20\%$）。

题目	难度	知识点
2799. 统计完全子数组的数目	1398	滑动窗口
2825. 循环增长使字符串子序列等于另一个字符串	1415	双指针
2760. 最长奇偶子数组	1420	分组循环
2909. 元素和最小的山形三元组 II	1479	前后缀分解
2958. 最多 K 个重复元素的最长子数组	1535	滑动窗口
2841. 几乎唯一子数组的最大和	1546	滑动窗口
2874. 有序三元组中的最大值 II	1583	前后缀分解
2779. 数组的最大美丽值	1638	滑动窗口
2943. 最大化网格图中正方形空洞的面积	1677	分组循环
2962. 统计最大元素出现至少 K 次的子数组	1701	滑动窗口
2905. 找出满足差值条件的下标 II	1764	双变量问题
2875. 无限数组的最短子数组	1914	滑动窗口
2762. 不间断子数组	1940	滑动窗口
2831. 找出最长等值子数组	1976	滑动窗口
2861. 最大合金数	1981	二分答案
2772. 使数组中的所有元素都等于零	2029	差分数组
2948. 交换得到字典序最小的数组	2047	分组循环
2845. 统计趣味子数组的数目	2073	哈希表
2906. 构造乘积矩阵	2075	前后缀分解
2781. 最长合法子字符串的长度	2204	滑动窗口
2949. 统计美丽子字符串 II	2445	前缀和、哈希表
2953. 统计完全子字符串	2449	分组循环、滑动窗口
2791. 树中可以形成回文的路径数	2677	哈希表、位运算

相关文章

• 【题单】滑动窗口（定长/不定长/多指针）
• 【题单】二分算法（二分答案/最小化最大值/最大化最小值/第K小）
• 分组循环：教你一次性把代码写对
• 差分数组
• 如何科学上分：利用难度分科学训练

二、动态规划

周赛常客。

• 上半年有 $14$ 道，几乎只在第四题出现（占比 $24\%$），第三题仅占 $8\%$。
• 下半年有 $26$ 道，第四题占比 $33\%$，第三题占比增至 $30\%$。

注：线性 DP 是指，从数组前缀（后缀）转移到另一个前缀（后缀）的 DP。像最长递增子序列、最长公共子序列都属于这一类。

题目	难度	知识点
2770. 达到末尾下标所需的最大跳跃次数	1533	线性 DP
2915. 和为目标值的最长子序列的长度	1659	0-1 背包
2826. 将三个组排序	1721	状态机 DP
2786. 访问数组中的位置使分数最大	1733	线性 DP
2944. 购买水果需要的最少金币数	1709	线性 DP/单调队列优化 DP
2771. 构造最长非递减子数组	1792	线性 DP
2787. 将一个数字表示成幂的和的方案数	1818	0-1 背包
2830. 销售利润最大化	1851	线性 DP
2767. 将字符串分割为最少的美丽子字符串	1865	划分型 DP
2901. 最长相邻不相等子序列 II	1899	子序列 DP 的思考套路
2925. 在树上执行操作以后得到的最大分数	1940	树形 DP
2919. 使数组变美的最小增量运算数	2031	线性 DP
2896. 执行操作使两个字符串相等	2172	线性 DP
2930. 重新排列后包含指定子字符串的字符串数目	2227	背包
2858. 可以到达每一个节点的最少边反转次数	2295	换根 DP
2827. 范围中美丽整数的数目	2324	数位 DP
2920. 收集所有金币可获得的最大积分	2351	树形 DP
2801. 统计范围内的步进数字数目	2367	数位 DP
2926. 平衡子序列的最大和	2448	树状数组优化 DP
2911. 得到 K 个半回文串的最少修改次数	2608	划分型 DP
2902. 和带限制的子多重集合的数目	2759	多重背包方案数、前缀和优化 DP
2851. 字符串转换	2858	KMP、矩阵快速幂优化 DP
2945. 找到最大非递减数组的长度	2943	单调队列优化 DP
2809. 使数组和小于等于 x 的最少时间	2979	贪心+DP

相关文章

在之前的每日一题中，我写了大量「教你一步步思考 DP」的题解，请看 往期题解精选 中的动态规划。

三、图论

周赛第四题约占 $10\%$。

题目	难度	知识点
2976. 转换字符串的最小成本 I	待定	Floyd
2959. 关闭分部的可行集合数目	2077	二进制枚举、Floyd
2812. 找出最安全路径	2154	多源 BFS
2876. 有向图访问计数	2210	基环树
2846. 边权重均等查询	2508	最近公共祖先
2836. 在传球游戏中最大化函数值	2769	倍增/基环树

相关文章

• 带你发明 Floyd 算法：从记忆化搜索到递推
• 树上倍增、最近公共祖先 LCA

四、数据结构

周赛第四题约占 $10\%$。

题目	难度	知识点
2810. 故障键盘	1193	$\mathcal{O}(n)$ 做法
2866. 美丽塔 II	2072	单调栈、前后缀分解
2940. 找到 Alice 和 Bob 可以相遇的建筑	2327	最小堆/线段树二分
2935. 找出强数对的最大异或值 II	2349	0-1 字典树/哈希表
2818. 操作使得分最大	2397	单调栈、贡献法
2916. 子数组不同元素数目的平方和 II	2816	线段树

相关文章

带你发明树状数组，用数学证明算法正确性

五、数学

主要考察数论、组合数学相关内容。

周赛第二题约占 $15\%$，第四题约占 $18\%$。

题目	难度	知识点
2761. 和等于目标值的质数对	1505	埃氏筛、线性筛
2929. 给小朋友们分糖果 II	1701	容斥原理
2842. 统计一个字符串的 k 子序列美丽值最大的数目	2092	组合数学
2930. 重新排列后包含指定子字符串的字符串数目	2227	容斥原理
2862. 完全子集的最大元素和	2292	因子
2867. 统计树中的合法路径数目	2428	树上计数
2949. 统计美丽子字符串 II	2445	因子
2954. 统计感冒序列的数目	2645	组合数学

六、思维题

包含贪心、脑筋急转弯等。

常见于周赛第二题（约占 $35\%$）和第三题（约占 $23\%$）。

题目	难度	知识点
2938. 区分黑球与白球	1423	贪心
2914. 使二进制字符串变美丽的最少修改次数	1480	脑筋急转弯
2789. 合并后数组中的最大元素	1485	贪心
2840. 判断通过操作能否让字符串相等 II	1486	结论
2918. 数组的最小相等和	1526	贪心、分类讨论
2811. 判断是否能拆分数组	1543	脑筋急转弯
2856. 删除数对后的最小数组长度	1750	$\mathcal{O}(\log n)$ 做法
2871. 将数组分割成最多数目的子数组	1750	贪心、位运算
2952. 需要添加的硬币的最小数量	1784	贪心
2934. 最大化数组末位元素的最少操作次数	1803	分类讨论
2931. 购买物品的最大开销	1822	贪心、排序不等式
2808. 使循环数组所有元素相等的最少秒数	1875	贪心
2939. 最大异或乘积	2128	贪心、位运算
2910. 合法分组的最少组数	2132	贪心
2835. 使子序列的和等于目标的最少操作次数	2207	贪心、位运算
2897. 对数组执行操作使平方和最大	2301	贪心、位运算
2813. 子序列最大优雅度	2582	反悔贪心
2790. 长度递增组的最大数目	2620	贪心、构造

相关文章

• 从集合论到位运算，常见位运算技巧分类总结！

总结

	上半年中位数	下半年中位数	变化量	全年中位数	全年平均值
第一题	$1259$	$1248$	$-11$	$1256$	$1265$
第二题	$1428$	$1485$	$57$	$1468$	$1480$
第三题	$1791$	$1899$	$108$	$1889$	$1887$
第四题	$2281$	$2337$	$56$	$2327$	$2318$

欲穷千里目，更上一层楼。最后祝大家新年快乐，在新的一年能实现自己的目标，不断变强！