上一期：2022 下半年周赛题目总结
大家好，又到了半年一度的周赛总结时间！
周赛包含大量算法套路题，我从上半年的 场周赛，共计 道题目中，精选了一些「能学到技巧」的题目，供各位练习。
列出的题目已按照难度分排序，大家可以结合自己的薄弱之处针对练习。
一、技巧类题目
技巧指一些比较套路的算法，包括双指针、滑动窗口、二分答案、前缀和、差分、回溯、前后缀分解、二进制枚举、贡献法等。
这些技巧相对容易掌握，无论是求职面试还是周赛，都是经常考察的，可以优先学习这些内容。
注：常见于周赛第二题（约占 ）和第三题（约占 ）。
| 题目 | 难度 | 备注 |
|---|---|---|
| 2730. 找到最长的半重复子字符串 | 1502 | 双指针 |
| 2698. 求一个整数的惩罚数 | 1679 | 回溯 |
| 2563. 统计公平数对的数目 | 1721 | 排序+二分查找 |
| 2653. 滑动子数组的美丽值 | 1785 | 滑动窗口 |
| 2718. 查询后矩阵的和 | 1769 | 倒序处理 |
| 2576. 求出最多标记下标 | 1843 | 二分答案/双指针 |
| 2537. 统计好子数组的数目 | 1892 | 双指针 |
| 2602. 使数组元素全部相等的最少操作次数 | 1903 | 排序+前缀和+二分查找 |
| 2594. 修车的最少时间 | 1915 | 二分答案 |
| 2681. 英雄的力量 | 2060 | 贡献法 |
| 2555. 两个线段获得的最多奖品 | 2081 | 双指针 |
| 2560. 打家劫舍 IV | 2081 | 二分答案+DP/贪心 |
| 2616. 最小化数对的最大差值 | 2155 | 二分答案+贪心 |
| 2528. 最大化城市的最小供电站数目 | 2236 | 二分答案+前缀和+差分+贪心 |
| 2565. 最少得分子序列 | 2432 | 前后缀分解 |
| 2552. 统计上升四元组 | 2433 | 有技巧的枚举 |
二、动态规划
周赛常客。
如果你很难想出状态转移方程，以及递推的顺序，可以先从记忆化搜索开始思考，然后转换到递推上。具体请看 动态规划入门：从记忆化搜索到递推【基础算法精讲 17】。
记忆化搜索像是自动挡，无需思考递推顺序，边界条件也容易确认；而递推像是手动挡，需要仔细确认递推的顺序以及初始值。但记忆化搜索并不是万能的，某些题目递推的写法可以结合数据结构等来优化时间复杂度。
注：常见于周赛第四题（约占 ）。
| 题目 | 难度 | 备注 |
|---|---|---|
| 2606. 找到最大开销的子字符串 | 1422 | 最大子数组和 |
| 2707. 字符串中的额外字符 | 1736 | 线性 DP |
| 2585. 获得分数的方法数 | 1910 | 背包 |
| 2547. 拆分数组的最小代价 | 2020 | 划分型 DP |
| 2597. 美丽子集的数目 | 2023 | 回溯/动态规划 |
| 2581. 统计可能的树根数目 | 2228 | 换根 DP |
| 2646. 最小化旅行的价格总和 | 2238 | 树形 DP |
| 2719. 统计整数数目 | 2355 | 数位 DP |
| 2713. 矩阵中严格递增的单元格数 | 2387 | DP+优化 |
| 2538. 最大价值和与最小价值和的差值 | 2398 | 树形 DP |
| 2572. 无平方子集计数 | 2420 | 0-1背包/子集状压DP |
| 2742. 给墙壁刷油漆 | 2425 | 线性DP/0-1背包 |
| 2617. 网格图中最少访问的格子数 | 2581 | 线段树/单调栈优化DP |
三、图论
包含 DFS、BFS、拓扑排序、最短路等。
注：周赛第三题约占 ，第四题约占 。
| 题目 | 难度 | 备注 |
|---|---|---|
| 2641. 二叉树的堂兄弟节点 II | 1677 | BFS |
| 2684. 矩阵中移动的最大次数 | 1626 | BFS |
| 2685. 统计完全连通分量的数量 | 1769 | DFS |
| 2642. 设计可以求最短路径的图类 | 1811 | Dijkstra/Floyd 模板 |
| 2608. 图中的最短环 | 1904 | BFS |
| 2662. 前往目标的最小代价 | 2154 | Dijkstra |
| 2577. 在网格图中访问一个格子的最少时间 | 2382 | Dijkstra/二分答案+BFS |
| 2603. 收集树中金币 | 2712 | 拓扑排序 |
| 2699. 修改图中的边权 | 2874 | Dijkstra |
四、数据结构
包括堆（优先队列）、单调栈、并查集、树状数组、线段树等。
学习这些只是开始，能否灵活运用才是关键。
注：周赛第四题约占 。
| 题目 | 难度 | 备注 |
|---|---|---|
| 2542. 最大子序列的分数 | 2056 | 排序+最小堆 |
| 2659. 将数组清空 | 2282 | 树状数组/转换 |
| 2569. 更新数组后处理求和查询 | 2398 | lazy 线段树 |
| 2736. 最大和查询 | 2533 | 离线+单调栈 |
| 2532. 过桥的时间 | 2589 | 堆+复杂模拟 |
| 2612. 最少翻转操作数 | 2824 | BFS+平衡树/并查集 |
五、数学
主要考察数论相关内容。
注：周赛第二题约占 ，第四题约占 。
| 题目 | 难度 | 备注 |
|---|---|---|
| 2521. 数组乘积中的不同质因数数目 | 1413 | 质因数分解 |
| 2523. 范围内最接近的两个质数 | 1650 | 质数筛法 |
| 2601. 质数减法运算 | 1779 | 质数筛法+二分查找 |
| 2598. 执行操作后的最大 MEX | 1846 | 同余 |
| 2654. 使数组所有元素变成 1 的最少操作次数 | 1929 | GCD |
| 2607. 使子数组元素和相等 | 2071 | 裴蜀定理+中位数贪心 |
| 2584. 分割数组使乘积互质 | 2159 | 质因数分解+跳跃游戏 |
| 2543. 判断一个点是否可以到达 | 2221 | GCD |
六、思维题
包含贪心、位运算、脑筋急转弯、构造等，挑选一些比较有趣的题目。
注：常见于周赛第二题（约占 ）、第三题（约占 ）和第四题（约占 ）。
| 题目 | 难度 | 备注 |
|---|---|---|
| 2527. 查询数组 Xor 美丽值 | 1550 | 位运算化简 |
| 2546. 执行逐位运算使字符串相等 | 1605 | 脑筋急转弯 |
| 2571. 将整数减少到零需要的最少操作数 | 1649 | 贪心/位运算 |
| 2550. 猴子碰撞的方法数 | 1663 | 正难则反 |
| 2611. 老鼠和奶酪 | 1663 | 贪心 |
| 2588. 统计美丽子数组数目 | 1697 | 转换+前缀异或和 |
| 2568. 最小无法得到的或值 | 1754 | 脑筋急转弯 |
| 2712. 使所有字符相等的最小成本 | 1791 | 贪心 |
| 2680. 最大或值 | 1912 | 贪心+前后缀分解 |
| 2731. 移动机器人 | 1923 | 脑筋急转弯 |
| 2564. 子字符串异或查询 | 1959 | 转换 |
| 2561. 重排水果 | 2222 | 贪心 |
| 2659. 将数组清空 | 2282 | 树状数组/转换 |
| 2556. 二进制矩阵中翻转最多一次使路径不连通 | 2369 | 转换 |
| 2589. 完成所有任务的最少时间 | 2380 | 贪心 |
| 2573. 找出对应 LCP 矩阵的字符串 | 2682 | 构造+DP验证 |
总结
相比去年，数据结构题变少了，但仍然有 2532. 过桥的时间 这道让人“印象深刻”的模拟题。
思维题的比重增加不少（尤其是第三题中的），个人喜欢的题目是 2568. 最小无法得到的或值 和 2556. 二进制矩阵中翻转最多一次使路径不连通。
四五月出了不少图论题，尤其是最短路，可以针对练习下。
附
致谢
- 感谢 @zerotrac2 的 周赛难度分统计。
- 感谢 @huxulm 的 周赛难度分可视化。
- 感谢 @runonline 的 周赛难度分油猴脚本。
