rui_er 的出题日志

rui_er · 2025-01-27 23:29:51 · 算法·理论

本博客用于锐评我过去/现在/将来出的所有原创题，可能会包含对烂题的吐槽、对好题的推销、对出题过程的介绍等。

质量评价包含极差、差、较差、常规、较好、好、极好共七档。特别地，若题目仅涉及语言入门，而不涉及算法或思维，质量评价为 N/A。我认为除非因特殊情况（如模拟赛等）刻意为之，否则 Rated 比赛所有题的题目质量不应低于“常规”，且至少一半题的题目质量不应低于“较好”。题目本身的质量、题目对选手/出题人的启发性、题目在比赛中的定位等都会影响题目质量评价。也就是说，一道题目本身质量不一定很高，但如果它被放在了合适的位置，或者提出了一个新的思路/出题方向，我依然可能给出很高的质量评价。

本博客可能包含少量关于题目解法的剧透内容。

我的原创题见题单 尺子的原创题。

所有题目按公开时间顺序收录，时间相同的按比赛中题目排列顺序收录。

「RdOI」Radiant OI Round 2

P7579 「RdOI R2」称重(weigh)

• 题目雏形时间：N/A（无法考证）。
• 题目完工时间：2021 年 4 月 9 日。
• 题目公开时间：2021 年 5 月 2 日。
• 题目位置：Unrated 团队公开赛，B 题。
• 质量评价：差。
• 分类：交互题、二分、三分。

初二不懂事乱出的题，似乎小学奥数气氛非常浓。二分/三分交互题太典了，好像 CF 上面也一堆这种一眼二分/三分交互题。不过既然是 Unrated 公开赛，感觉质量也勉强符合要求。

【LGR-135-Div.2】 小猴编程 4 月月赛 I & GMOI Round 2

P9199 「GMOI R2-T2」猫耳小 与 P9202 「GMOI R2-T2」猫耳小（加强版）

• 题目雏形时间：2023 年 3 月 20 日。
• 题目完工时间：2023 年 3 月 21 日。
• 题目公开时间：2023 年 4 月 5 日。
• 题目位置：赞助洛谷月赛 Div.2，B 题。
• 质量评价：较好。
• 分类：贪心、构造。

当时月赛 ddl 前发现原 B 题有锅，紧急赶工出来的一道题，但是感觉题目质量还不错，我比较喜欢。原本准备月赛放加强版，但是团队成员认为有些难，通过率容易达不到要求，于是便弱化成了最终版本，结果通过率还是没达到要求，被扣了点工资。

Codeforces Round 864 (Div. 2)

CF1797A Li Hua and Maze

• 题目雏形时间：2022 年 10 月 4 日。
• 题目完工时间：2023 年 1 月 14 日。
• 题目公开时间：2023 年 4 月 8 日。
• 题目位置：CodeForces Div.2，A 题。
• 质量评价：较好。
• 分类：（无）。

感觉是道不错的签到题，同时通过保证 n,m\ge 4 把繁琐的讨论规避掉了。但是写题解证明的时候遇到了一些麻烦，第一反应是使用最大流最小割定理，显然 2A 放这个不合适，于是写了一些分类讨论上去。感觉出了一道有 flows 标签的 *800 有点太乐了。

CF1797B Li Hua and Pattern

• 题目雏形时间：2022 年 4 月 5 日。
• 题目完工时间：2023 年 1 月 14 日。
• 题目公开时间：2023 年 4 月 8 日。
• 题目位置：CodeForces Div.2，B 题。
• 质量评价：常规。
• 分类：（无）。

结论很简单，虽然需要分奇偶讨论，但并不繁琐，算是比较正常的 2B。

CF1797C Li Hua and Chess

• 题目雏形时间：2022 年 7 月 2 日。
• 题目完工时间：2023 年 1 月 14 日。
• 题目公开时间：2023 年 4 月 8 日。
• 题目位置：CodeForces Div.2，C 题。
• 质量评价：较好。
• 分类：交互题、数学。

奇怪国际象棋交互题，原来的标算比较弱智，被 coordinator 爆标了，改成了现在的版本。

CF1797D Li Hua and Tree

• 题目雏形时间：2022 年 4 月 27 日。
• 题目完工时间：2023 年 1 月 14 日。
• 题目公开时间：2023 年 4 月 8 日。
• 题目位置：CodeForces Div.2，D 题。
• 质量评价：较差。
• 分类：暴力、数据结构。

其实是想考察注意到旋转操作对树形态影响不大，然后随便暴力维护，结果似乎变成了纯暴力题，实际出出来效果并不好。

CF1797E Li Hua and Array

• 题目雏形时间：2022 年 4 月 30 日。
• 题目完工时间：2023 年 1 月 14 日。
• 题目公开时间：2023 年 4 月 8 日。
• 题目位置：CodeForces Div.2，E 题。
• 质量评价：常规。
• 分类：势能线段树、数学。

注意到欧拉函数的一些性质，然后使用势能线段树维护，维护的东西比较难写。

不知道当时怎么想的，竟然把 D 和 E 放在同一场里，神秘。

CF1797F Li Hua and Path

• 题目雏形时间：2022 年 12 月 30 日。
• 题目完工时间：2023 年 1 月 14 日。
• 题目公开时间：2023 年 4 月 8 日。
• 题目位置：CodeForces Div.2，F 题。
• 质量评价：好。
• 分类：树状数组、并查集、重构树。

当时发明出来了这个重构树，无论是同学、coordinator 还是 tester 好像都觉得非常厉害，而且验题也只有一个人通过，但是赛后发现好像是 well-known in China 的东西被我重复造轮子了……

「NnOI」Round 1

P9412 「NnOI R1-T1」购物

• 题目雏形时间：2023 年 5 月 29 日。
• 题目完工时间：2023 年 6 月 5 日。
• 题目公开时间：2023 年 6 月 11 日。
• 题目位置：Unrated 团队公开赛，A 题。
• 质量评价：较好。
• 分类：贪心。

萌萌贪心签到，非常符合本题的定位。

【LGR-162-Div.3】洛谷基础赛 #5 & QFOI Round 1

P9712 「QFOI R1」贴贴

• 题目雏形时间：2023 年 8 月 4 日。
• 题目完工时间：2023 年 8 月 6 日。
• 题目公开时间：2023 年 10 月 5 日。
• 题目位置：洛谷基础赛，A 题。
• 质量评价：N/A。
• 分类：（无）。

萌萌签到题。

P9713 「QFOI R1」抱抱

• 题目雏形时间：2023 年 9 月 16 日。
• 题目完工时间：2023 年 9 月 16 日。
• 题目公开时间：2023 年 10 月 5 日。
• 题目位置：洛谷基础赛，B 题。
• 质量评价：常规。
• 分类：（无）。

萌萌签到题。

P9714 「QFOI R1」摸摸

• 题目雏形时间：2023 年 9 月 17 日。
• 题目完工时间：2023 年 9 月 17 日。
• 题目公开时间：2023 年 10 月 5 日。
• 题目位置：洛谷基础赛，C 题。
• 质量评价：较好。
• 分类：数学。

考察了选手对操作进行分析的能力、数学直觉和注意力。存在 O(n) 的数学解法，但对基础赛来讲太难了，因此采用 O(nw) 解法作为标算。

【LGR-181-Div.2】洛谷 4 月月赛 I & Cfz Round 2

P10309 「Cfz Round 2」Max of Distance

• 题目雏形时间：2023 年 12 月 8 日。
• 题目完工时间：2024 年 1 月 9 日。
• 题目公开时间：2024 年 4 月 4 日。
• 题目位置：洛谷月赛 Div.2 六题场，D 题。
• 质量评价：好。
• 分类：构造。

构造题十分好玩，又不太喜欢那种人类只能想出来唯一解法、需要和出题人对脑电波的构造，于是就出了这么一个十分自由的构造题。

最最有趣的是，有验题人搞出了一种错误解法：

假设所有边权均为 1，求出一个期望值，再等比例放缩。

注意到，若所有边权均为 1 时期望值为 0，则上述解法会被 Hack。于是我便构造数据把这个解法叉掉了。这也是本题完工时间如此靠后的原因。

Codeforces Round 942 (Div. 1, Div. 2)

CF1972A Contest Proposal

• 题目雏形时间：2024 年 3 月 30 日。
• 题目完工时间：2024 年 4 月 2 日。
• 题目公开时间：2024 年 4 月 30 日。
• 题目位置：CodeForces Div.2，A 题。
• 质量评价：常规。
• 分类：贪心。

瞎捏的一道签到题。

CF1972B Coin Games

• 题目雏形时间：2024 年 3 月 9 日。
• 题目完工时间：2024 年 3 月 14 日。
• 题目公开时间：2024 年 4 月 30 日。
• 题目位置：CodeForces Div.2，B 题。
• 质量评价：好。
• 分类：博弈论。

自我感觉这题还挺有意思的，玩几组就能发现奇偶性，作为 B 题也不算难。

CF1967C Fenwick Tree

• 题目雏形时间：2024 年 1 月 31 日。
• 题目完工时间：2024 年 4 月 24 日。
• 题目公开时间：2024 年 4 月 30 日。
• 题目位置：CodeForces Div.1，C 题。
• 质量评价：好。
• 分类：组合数学。

比较简单的组合数学题，发现多次前缀和的贡献系数是组合数，然后在树状数组的路径上算贡献。感觉可能有一定启发性？

【LGR-183-Div.3】复旦勰码基础赛 #10 & QFOI Round 2

P10409 「QFOI R2」水落溪流浅浅

• 题目雏形时间：2024 年 4 月 2 日。
• 题目完工时间：2024 年 4 月 2 日。
• 题目公开时间：2024 年 5 月 4 日。
• 题目位置：赞助洛谷基础赛，A 题。
• 质量评价：N/A。
• 分类：（无）。

萌萌签到题。

P10410 「QFOI R2」寺秋山霭苍苍

• 题目雏形时间：2024 年 4 月 1 日。
• 题目完工时间：2024 年 4 月 2 日。
• 题目公开时间：2024 年 5 月 4 日。
• 题目位置：赞助洛谷基础赛，B 题。
• 质量评价：较差。
• 分类：初中几何、初中代数。

在发现大纲里有初中几何、初中代数之后，我决定硬把三角形面积和二次函数捏到一起出一道题，于是就有了这题。这道题的题目质量确实不高，但那又怎么样呢，反正入门级的正式比赛也会有东拼西凑出来的数学题。

P10411 「QFOI R2」树色尤含残雨

• 题目雏形时间：2024 年 4 月 1 日。
• 题目完工时间：2024 年 4 月 3 日。
• 题目公开时间：2024 年 5 月 4 日。
• 题目位置：赞助洛谷基础赛，C 题。
• 质量评价：较好。
• 分类：数学、分解质因数、贪心。

萌萌贪心题。为了防止这题对入门级选手来说过难，在部分分的特殊性质里几乎把所有要分类讨论的东西都明示出来了，所以做起来应该没啥难度。

P10412 「QFOI R2」钟声远带斜阳

• 题目雏形时间：2024 年 3 月 31 日。
• 题目完工时间：2024 年 4 月 3 日。
• 题目公开时间：2024 年 5 月 4 日。
• 题目位置：赞助洛谷基础赛，D 题。
• 质量评价：常规。
• 分类：贪心、思维。

思维题，类似北京高考数学 21 题的风格，不是很 OI。

由于某些原因，这一场比赛被我刻意地放了大量数学题，且题目质量不一定很高。

【MX-X2】梦熊周赛 · 未来组 2 & Cfz Round 4

P10856 【MX-X2-T5】「Cfz Round 4」Xor-Forces

• 题目雏形时间：2022 年 11 月（具体日期无法考证）。
• 题目完工时间：2022 年 12 月（具体日期无法考证）。
• 题目公开时间：2024 年 8 月 10 日。
• 题目位置：梦熊周赛未来组，E 题。
• 质量评价：较好。
• 分类：线段树。

是的这个题被我放了将近两年才用上。

至少在 2022 年出题时这个 trick 似乎在 CNOI 并不普及，于是就把它出了出来。

【LGR-212-Div.2】洛谷 12 月月赛 II & Cfz Round 5

P11486 「Cfz Round 5」Mata rainen

• 题目雏形时间：2024 年 6 月 28 日。
• 题目完工时间：2024 年 7 月 2 日。
• 题目公开时间：2024 年 12 月 29 日。
• 题目位置：洛谷月赛 Div.2，B 题。
• 质量评价：极好。
• 分类：构造。

常规的构造题都是让你构造一些数值或者操作方法，我希望出一些不常规的构造题，于是就出了这道构造树形态的题，感觉比较新颖。

PAIO 2025

P14038 [PAIO 2025] Adventure Plan

• 题目雏形时间：2025 年 8 月 13 日。
• 题目完工时间：2025 年 8 月 24 日。
• 题目公开时间：2025 年 9 月 14 日。
• 题目位置：PAIO day2，最难题。
• 质量评价：好。
• 分类：差分约束、构造。

第一次给官方比赛投题，成功被选上了。

质量评价好像出现了个人差。我问了一些人的评价，有几个觉得非常妙的，也有觉得无聊的，但我自我感觉挺好（？）。

感觉这题也有一定启发性：差分约束不要只想着 Bellman-Ford 算法，我们 Floyd-Warshall 也是可以正确处理负权边以及判断负环的。

【MX-X23】梦熊 X 组 · 月亮赛（同步赛） & 【MX-J26】梦熊 J 组 · 月亮赛（同步赛）

P14171 【MX-X23-T1】丢手绢

• 题目雏形时间：2025 年 6 月 16 日。
• 题目完工时间：2025 年 7 月 7 日。
• 题目公开时间：2025 年 10 月 6 日。
• 题目位置：梦熊周赛入门+未来组，A 题。
• 质量评价：N/A。
• 分类：（无）。

萌萌签到题。

P14172 【MX-X23-T2】括号串

• 题目雏形时间：2025 年 6 月 16 日。
• 题目完工时间：2025 年 7 月 7 日。
• 题目公开时间：2025 年 10 月 6 日。
• 题目位置：梦熊周赛入门+未来组，B 题。
• 质量评价：常规。
• 分类：（无）。

比较经典的括号序列 \pm 1 前缀和。

P14173 【MX-X23-T3】猜拳游戏

• 题目雏形时间：2025 年 7 月 1 日。
• 题目完工时间：2025 年 7 月 2 日。
• 题目公开时间：2025 年 10 月 6 日。
• 题目位置：梦熊周赛入门+未来组，C 题。
• 质量评价：较好。
• 分类：贪心。

观察出 \gcd(n,m) 的结论，然后随便贪心。

我本来给这场比赛投了一道质量评价为“极好”的紫题，可惜的是在审核期间查出了一道小众原题，于是就不能用了，导致我最终只给这场比赛出了三道签到题，十分可惜。

【LGR-256-Div.3】洛谷基础赛 #29 & QFOI Round 3

P14913 「QFOI R3」难度评分

• 题目雏形时间：2025 年 7 月 5 日。
• 题目完工时间：2025 年 7 月 5 日。
• 题目公开时间：2025 年 12 月 28 日。
• 题目位置：洛谷基础赛，A 题。
• 质量评价：N/A。
• 分类：（无）。

萌萌签到题。

P14914 「QFOI R3」航线交汇

• 题目雏形时间：2025 年 8 月 2 日。
• 题目完工时间：2025 年 8 月 10 日。
• 题目公开时间：2025 年 12 月 28 日。
• 题目位置：洛谷基础赛，B 题。
• 质量评价：常规。
• 分类：数学。

简单解方程。

P14915 「QFOI R3」算法竞赛

• 题目雏形时间：2025 年 7 月 5 日。
• 题目完工时间：2025 年 7 月 7 日。
• 题目公开时间：2025 年 12 月 28 日。
• 题目位置：洛谷基础赛，C 题。
• 质量评价：较好。
• 分类：排序、贪心、双指针。

萌萌贪心题。有一个不少人中招的坑点是要开 long long。

P14916 「QFOI R3」数状树组

• 题目雏形时间：2025 年 6 月 30 日。
• 题目完工时间：2025 年 7 月 7 日。
• 题目公开时间：2025 年 12 月 28 日。
• 题目位置：洛谷基础赛，D 题。
• 质量评价：较好。
• 分类：树、二叉树、分类讨论。

考察完全二叉树各种性质的题，感觉作为基础赛 D 题挺合适的。分讨情况有点多，不过样例应该给了一些易漏情况的提示（比如样例三的第三次询问，赛时答疑有三个人问我），代码写出来也不长。部分分给得应该挺足，也不难拿到，但是没人写，基本都是要么 100 分，要么正解漏情况挂到 0/10/20 分，导致区分度不够。但也没办法，部分分显然不能保证不需要分讨某些情况，不然所有人都知道要讨论啥了。