跳至主要內容

2025暑假算法刷题记录（2025.7.20）

Minecraftbucuo2026/1/31大约 9 分钟

2025暑假算法刷题记录（2025.7.20）

前言：

暑假截至到今天我做了很多的算法题，但我发现有些题目，做过的，看了题解会做了，过久了又忘。这样的学习是没有效果的，所以我打算在这里记录一下我做过的比较好的题目，这样我随时可以检验我是否真的会做了，如果忘了我就可以随时复习。另外这个配套我的main.cpp暑假篇一起食用，代码全都写好，只需要 Ctrl+F 查找题目所在位置就行了。——2025.7.20

  1. https://codeforces.com/contest/2117/problem/G G. Omg Graph

    最短路定义为走过的边的最小值和最大值的和，那么应该如何求？

  2. https://codeforces.com/contest/845/problem/G G. Shortest Path Problem?

    最短路定义为走过的边的异或和，那么应该如何求？该定义下的最长路呢？

  3. U81904 【模板】树的直径

    就是题目说的那样，想想你还会不会求树的直径。有两种常见方法，详情请看：树的直径 - OI Wiki

  4. P3805 【模板】manacher

  5. P5091 【模板】扩展欧拉定理

  6. P3846【模板】BSGS

    几个模板放这里，需要时不时想想算法的主要过程，算法的思想

  7. P1368 【模板】最小表示法

  8. G. Maximize the Remaining String Problem - G - Codeforces

    给你一个由小写英文字母组成的字符串 ss，你需要去掉一部分字符，使得操作后得到的字符串 tt 满足在 ss 中出现的字母每种只保留一

    个并且最大化 tt 的字典序。

  9. 战前准备 C-战前准备_牛客练习赛142

    战前准备
    战前准备

  10. 第四次忍界大战 D-第四次忍界大战_牛客练习赛142

    第四次忍界大战
    第四次忍界大战

  11. Problem - C - Codeforces

    给你一棵树，要你删除两个顶点，问删除后最大能得到多少连通分量？

  12. P2261 [CQOI2007] 余数求和 [P2261 CQOI2007] 余数求和 - 洛谷

    求 G(n,k)=∑i=1nk%i1≤n,k≤109G(n,k)=\sum_{i=1}^{n}{k\%i} \quad 1 \le n,k \le 10^9

  13. P2303 [SDOI2012] Longge 的问题 [P2303 SDOI2012] Longge 的问题 - 洛谷

    求 ∑i=1ngcd(i,n)1≤n≤232\sum_{i = 1}^{n}gcd(i, n) \quad 1 \le n \le 2^{32}

  14. CF632D Longest Subsequence - 洛谷

    给定有 nn 个元素的数组 aa 和数字 mm。记 LCMLCM 为 ll 。找出使 l≤ml \le m 的 aa 的最长子序列。

    定义 aa 的子序列为通过删除 aa 中的一些元素得到的数组。允许删除 00 个元素或所有元素。

    空数组的 LCMLCM 等于 11。

  15. CF687B Remainders Game - 洛谷

    给定正整数 n,kn,k 和 nn 个正整数 c1,c2,...cnc_1,c_2,...c_n。如果对于任意正整数 xx，可以通过 x%aix \%a_i 的值推出 x%kx \% k 的值则输出 Yes 否则输出 No。

  16. P6583 回首过去 - 洛谷

    给定正整数 nn，求出有序整数对 (x,y)(x,y) 的个数，满足 1≤x,y≤n1≤x,y≤n 且 xy\frac{x}{y} 可以表示为十进制有限小数。

  17. CF607B Zuma - 洛谷

    Genos 最近在他的手机上下载了祖玛游戏。在祖玛游戏里，存在 nn 个一行的宝石，第 ii 个宝石的颜色是 CiC_i。这个游戏的目标是尽快的消灭一行中所有的宝石。

    在一秒钟，Genos 能很快的挑选出这些有颜色的宝石中的一个回文的、连续的子串，并将这个子串移除。每当一个子串被删除后，剩余的宝石将连接在一起，形成一个新的行列。

    你的任务是：求出把整个宝石串都移除的最短时间。

  18. https://codeforces.com/problemset/problem/2120/D

    题目难以描述，但却是是一道好题，涉及容斥原理，组合数学。

  19. P12021 面包题

    给定 nn, 从 [1,n][1, n] 的自然数中选出若干个数（可以不选），满足以下条件：

    若选择了 xx，则不能选择 kxkx。

    求总共有多少种选法（不考虑顺序）。

  20. https://codeforces.com/problemset/problem/2124/D

    给定 n,kn,k 和一个长度为 nn 的数组，你可以选择任何一个长度大于等于 kk 的区间，在该区间中找到第 kk 小的一个数字，并将其删除。问你是否存在操作使得数组为回文数组？

  21. Problem - 2121H - Codeforces

    最长上升子序列的变种题！有超级美妙的解法，太强了！

  22. CF2113F Two Arrays https://www.luogu.com.cn/problem/CF2113F

    给你两个数组长度为n的数组 an,bna_n, b_n，你可以进行 swap(ai,bi)swap(a_i, b_i) 操作无数次，如何才能使两个数组不同数字的个数的和最大？并求出操作完后的数组 a,ba, b。 (这题目的思路很妙，用图论解决)

  23. CF2112E Tree Colorings https://www.luogu.com.cn/problem/CF2112E

    这题目的解法真的太美妙了！

  24. P1390 公约数的和 P1390 公约数的和 - 洛谷

    求 ∑i=1n∑j=i+1ngcd(i,j)\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{gcd(i, j)}}

  25. n!n! 中 pp 的个数如何求？

  26. Problem - 2124E - Codeforces E. Make it Zero

  27. CF2121G Gangsta - 洛谷

  28. https://codeforces.com/problemset/problem/2114/G

  29. P1950 长方形 P1950 长方形 - 洛谷 P4147 玉蟾宫 - 洛谷

    给你一个 n×mn\times m 的矩阵，里面要么是空格要么是字符，求总共有多少个矩形里面全是空格？最大的满足题意的矩形面积为多少？

  30. CF2071D1 Infinite Sequence (Easy Version) - 洛谷

  31. Problem - 2071C - Codeforces

    这题的解法真是太牛逼了，根本想不到！

  32. Problem - 2069C - Codeforces

    小黄题都做不出，也是真的没话说。。。

  33. CF2069E A, B, AB and BA - 洛谷

  34. Problem - 2126G1 - Codeforces

  35. CF1948D Tandem Repeats? - 洛谷

  36. https://www.acwing.com/problem/content/description/6450/

    给你一个只包含 ( 和 ) 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

  37. https://www.acwing.com/problem/content/3685/

    给定 mm 个不同的整数 a1,a2,…,ama_1,a_2,…,a_m ，每个数都处于 [0,2n−1][0,2^n-1] 的范围内。

    一个图按照如下约束建立：

    如果整数 XX 和 YY 满足 X&Y=0X\&Y=0（&\& 是按位与运算），则 XX 和 YY 由一条无向边连接。

    请计算，图中连通分量的数量。

  38. CF2061C Kevin and Puzzle - 洛谷 小黄题啊

  39. https://www.acwing.com/problem/content/3684/ 小镇购物

    一道 中南大学考研机试题 ，考研题都不会打什么竞赛。。。

  40. [P7073 CSP-J2020] 表达式 - 洛谷

    如何通过后缀表达式建树？还有一定巧妙思维的题。

  41. P2397 yyy loves Maths VI (mode) - 洛谷

    给你一个长度为 n(1≤n≤2×106)n(1 \le n \le 2 \times 10^6) 的数组，其中众数的数量超过长度的一半，请你找出众数是哪个。那么简单是吧，但是内存限制为 55 MB，数组都存不下，如何应对？

  42. CF2085C Serval and The Formula - 洛谷

  43. CF2066B White Magic - 洛谷

  44. P1642 规划 - 洛谷

    一道树形dp结合01分数规划的问题，01分数规划头一次见，第一次做很容易贪心贪死。

  45. [P5662 CSP-J2019] 纪念品 - 洛谷

    一道背包dp问题，转换很巧妙，题目太长难以描述。

  46. CF2067B Two Large Bags - 洛谷

    小橙题啊，思维。。。

  47. CF2107C Maximum Subarray Sum - 洛谷

    1500的小黄题。。。算法思维太菜。

  48. Problem - 2049D - Codeforces

  49. CF2044G2 Medium Demon Problem (hard version) - 洛谷

    依旧是一种建图的思路！

  50. CF2106F Goblin - 洛谷

  51. Problem - J - Codeforces

    智力题，根本想不到。。。

  52. CF2075D Equalization - 洛谷

  53. CF2086D Even String - 洛谷

    以前做过的，还是不会。。。

  54. CF2043D Problem about GCD - 洛谷 [AT_arc137_a ARC137A] Coprime Pair - 洛谷

    给定1≤l≤r≤10181\le l\le r \le 10^{18} ，求范围内最远的两个互质的数，并且小的那个数尽可能小。

  55. [P11233 CSP-S 2024] 染色 - 洛谷

  56. [P7914 CSP-S 2021] 括号序列 - 洛谷

    一个长度为 n 且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个?

  57. CF2042C Competitive Fishing - 洛谷

    1800的小黄题。。。

  58. CF2042D Recommendations - 洛谷

    有 nn 个区间 Si=[li,ri]S_i=[l_i, r_i] ，对于每个区间，找出所有满足 Si⊂SjS_i \subset S_j 且 i≠ji \ne j 的区间 SjS_j ，求它们的并。

  59. CF2026D Sums of Segments - 洛谷

  60. CF2004E Not a Nim Problem - 洛谷

  61. CF1997E Level Up - 洛谷

  62. CF2045B ICPC Square - 洛谷

  63. CF1976D Invertible Bracket Sequences - 洛谷

    看了jiangly的代码，太牛逼了，短短几行就解决了，太巧妙了。太牛逼了！！！

  64. CF1976C Job Interview - 洛谷

  65. CF1923E Count Paths - 洛谷

    这题和 P10 有异曲同工之妙，但是代码还是写了很久才写出来，所以当时还是没有真正理解代码的运行原理。这次我对该题代码的理解更加深刻了，希望下次遇到变种题能快速写出AC代码。

  66. 2552. 统计上升四元组 - 力扣（LeetCode）

    统计 1324 的四元组有多少个，有妙法

  67. CF2109C2 Hacking Numbers (Medium Version) - 洛谷

    交互题，你不知道 xx 的值是多少，只能对 xx 进行不超过 44 次操作， 使其等于给定的 nn ，该如何操作呢？操作有加减乘除还有位相加。具体可以看题目，太妙了我只能说。另外，还有加强版，请问对于任意 xx 最少需要多少次操作能编程 nn ？

  68. CF1913D Array Collapse - 洛谷

  69. CF1901C Add, Divide and Floor - 洛谷

  70. CF1901D Yet Another Monster Fight - 洛谷

    题目翻译有问题，然后题目太长懒得写了，感兴趣可以点进去看看

  71. CF2131F Unjust Binary Life - 洛谷

    好题，和前面的绝对值求和很像，也要巧妙转换！

  72. CF1895D XOR Construction - 洛谷

    虽然做出来了，但是是guess的结果，题解的做法还是值得学习。

  73. CF2122C Manhattan Pairs - 洛谷

    妙啊！

暑假结束了。

最近更新:
贡献者: 杨必胜