洛谷 2025 年度试题推荐选集

部分试题的推荐理由（含因为名额限制无法入选的试题，含仅因为影响力获得提名的试题）： - P10001：本题题面简洁，仅用了贪心等基础算法，但是思维难度不低。总而言之，这是一道不可多得的好题！ - P10002：本题题面简洁，但是思维难度和代码难度都不低。覆盖算法面广，深刻地考察了组合数学、容斥原理、Prufer 序列、动态规划、搜索、自动机等知识点。同时使用了 SPJ 进行评分，有效地提升了本题的区分度。总而言之，这是一道不可多得的好题！郭羽冲 2023 年度最是题奖 (Yuchong Guo Best Problem in 2023 Award)颁发给：树哈希，来自 2023-2024 集训队互测 Round 1 (Oct 28, 2023)，作者为 zhoukangyang - P6837：非常牛的题。首先需要考虑它的交互器该怎么靠谱的使用，然后涉及到很多次优化。我 vp 的时候拿了 80.427 分，赛后发现稍微改一下就可以拿到人均的 92.623 分，从这个到正解的优化简直是惊为天人，非常的牛逼。 - P11695： - 本题是一道广受好评的题目，同时我认为其在 2025 年被公开的所有数据结构题中具有排在前三的质量。比起大量公式化的套路数据结构题，本题需要从一个有趣的角度切入，并且此后的多种维护方法也极具启发性和拓展性。 - "一道题，如果用一棵线段树就能解决，可能是一道题；如果用两棵线段树可以解决，可能是道烂题；但如果用四棵机制各有不同的线段树才能解决，它是一道神题。一道题，如果在时间维度上扫描并维护空间信息，可能是道好题；如果在空间维度上扫描并维护时间信息，也可能是道好题；但如果这两个方法同时出现在同一道题目里，而且必须分别使用的话，它是一道神题。P11695，昼寝，就是这样的一道神题。其由 NOI 金牌选手 critnos 倾力打造，巧妙地融合分治、两种维度的扫描线、四种机制不同的线段树为一体，在思路上具有极大的启发意义，在实现上更是对选手编程水平和心理素质的综合挑战。综上，我认为此题堪称年度好题。" - P12417：这是一个有趣的题，它有趣在它十分有趣。 - P12264："首先需要注意到转括号匹配。注意到之后很轻松就可以想到 dp，但 dp 会写挂，发现是匹配重了顺理成章地想到钦定匹配顺序，然后在这里再搞搞就过了。！！1" - P13336：非常巧妙的折半搜索，对于折半后的复杂度证明也很自然巧妙，很简洁的优雅做法。 - P12546：本题主要考点为 DP，部分分充足且设计合理，很好地对标各种复杂度的解法，引导选手一步步走向正解且区分度良好。从思路上来看，本题最后一步数据结构优化较为新颖，包括其在内的几乎所有优化均需要充分考虑题目的本质。 - P13783：本题部分分设计合理，尤其是 $m=n-1$ 的子任务，突出解题需要的关键的贪心策略。剩下的部分考验选手对最小生成树性质和该贪心策略特性的理解，得出最终只需要修改一些特定区间上下界的结论。而修改过程需要使用树链剖分、ST 表、并查集维护，考察了选手对数据结构的掌握能力。综上，这是一道综合性较强的题目，并且本身的思想具有高度的扩展性（可加强到“强制字典序最小”，再利用霍尔定理解题）。 - P13340：一道有趣的交互题。从 $N=3$ 的部分分开始探索，可以分析出询问答案的等价形式。接下来，子任务 3 & 4 的特殊性质引导选手考虑分治策略。而如果想要得到正解，则需深入挖掘性质，结合对二进制拆位、异或运算的深入理解，充分利用询问结果来求出答案。综上，这是一道非常优美的题目，并且具有优秀的引导性部分分。 - P10856：本题“区间下标异或”的操作非常新颖，但又可以顺畅的通过推理找到性质，使用改造过的普通线段树/主席树来解决。创新而非奇技淫巧，难点在于 observation+构造数据结构，是很有意思的一道题。 - P12477："大火题，胡策无人高于暴力；需要观察大量性质，刻画结构，然后经过大量讨论可得到一个可以计数的方法，形如三个交替转移的函数，都是整除分块形，利用杜教筛技巧可优化复杂度。因此这是一道数论神题，不可多得的好题。" - P10717：先进行树形 DP，需要一些状态设计和分步转移的技巧，设出来每个对象有四个状态，并行转移后是四进制。然后利用张量 CP 分解/高维前缀和的理论优化复杂度，张量秩为 6，也可使用边界秩做子集卷积状物。 - P11983： - 题目本身需要大量转化才能使每一步能完美进行，每一步转化所需的技巧较为平凡却不让人觉得繁琐，多层技巧的叠加使得对熟练度的要求较高，思维链较长却不让人觉得繁琐，在思考结束后同时也需要极强的代码能力来实现，在思维上和代码上都极具挑战力 - 部分分有启发性，没想到正解后面的部分也能获得较高的分数；各部分的算法/trick很好地组合在一起 - P11424："思维链条极长，对问题的刻画奇特且深刻，每一步都巧妙绝伦，具有极强的启示意义。实现难度不低，细节较多，考验选手的实现能力。" - P8120："~~原因首先这是我自己出的．~~ 感觉这个 trick 挺好玩的，这个题目的难点主要在于怎么处理一个信息开头在左边的散块结尾在右边的三块这种情形，但由于这个题目在相同元素的位置上有一定的「可贪心性」（不是很好描述这种神秘性质）总之就是同种颜色一定最左边 / 最右边的最好，可以使用这个方式维护一个 lst 来合并左右散块．而同时这个题目又有一个转化为树的建模：考虑散块和不考虑散块的答案最多相差 2B，于是可以把最优化削弱为判定，i 向 pre i 连边后就变成了一个树上问题．等价于求 k 级祖先．这两种转化都感觉挺有意思的．PS：这个题目能让 22 年的轩神（唐绍轩）想了 40+ min，也算是一个有点难度的题了．" - P9512：不强行拼凑却考察多个知识点，思维链较长且有难度，有一定 Ad-Hoc 程度 - P14471： - 欧拉序上 dp，并将部分物品延后考虑，非常巧妙！ - "把dfs序改成欧拉序这一步很有启发性，把物品分步决策使得契合差分的形态这一步，更是精妙绝伦" - P11696：非常好题，考察了选手多方面能力，代码量小且较为美观。 - P14472： - 不是我出的。但是各种意义上都非常震撼的一道题。不知道有生之年能不能命制出这种题目。 - 前面忘了，中间忘了，总之真是一道需要分析很多性质的不可多得的好题。 - P10383："1、赛时通过人数较少，有难度 2、冷门，需要推广 3、本题取模做法富有想象力，有效解决精度问题，这种手法可以运用到其他题目中（如 Mr Youngs Picture Permutations，出题人正是因为这题而产生思考），压缩并还原信息的方法触及信息学的本质 4、本题做法多种多样，如大步小步算法的应用，exgcd 还原分数，Stern-Brocot 上二分，殊途同归，有教育意义 5、知名选手 Purslane：非常好的题目，学到了很多 6、我爱此题" --- 被推荐提名次数最多的试题： - P11831： - 年度最具备影响力的试题。 - 我常常追忆过去。生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。我该在哪里停留？我问我自己。