知识点征集速报!!!! 第二期（2025.11.12-11.16） - 星语社Σ*

CommonAnts · 2025-11-30 16:43:47 · 算法·理论

知识点征集速报 !!!!

第二期（统计范围 2025.11.12-11.16） - 星语社Σ*

投稿数 \colorbox{firebrick}{\color{white}{\textbf{504}}}\color{firebrick}{\textbf{ (+369)}}

不含完全重复 \colorbox{slategray}{\color{white}{\textbf{92}}}\color{slategray}{\textbf{ (+92)}}

本期速报撰稿人：刘承奥（CommonAnts）

本文网址：https://www.luogu.com.cn/article/iddgejd7

投稿数显示截至本期速报统计范围的稿件的内容总项数，以及本期新增数。不含内容与之前基本完全重复的投稿。

来参与征集！有奖征集 OI 小知识点，思考题和科普

投稿：阅读规则 www.luogu.com.cn/article/v25cxsdj 并发送至邮箱 [email protected]

本期推荐内容

难度分区	内容	投稿人	类型	编者锐评
\colorbox{firebrick}{\color{white}{\textrm{\textbf{大众}}}}	欢迎投稿原创	OI 相关	优质大众科普	视频/文章
\colorbox{goldenrod}{\color{white}{\textrm{\textbf{普及}}}}	01 序列邻位奇偶性	caca	\colorbox{firebrick}{\color{white}{\textrm{\textbf{推荐}}}}	文中的其它 - 第 9 条。
\colorbox{darkgreen}{\color{white}{\textrm{\textbf{提高}}}}	区间 \mathrm{mex} 的结构	mrdyg	\colorbox{goldenrod}{\color{white}{\textrm{\textbf{原创}}}}	建议添加平面嵌入和几何直观（把区间 [l,r] 的 \mathrm{mex} 值视为平面点 (l,r) 的颜色刻画色块形状和结构）。
\colorbox{darkgreen}{\color{white}{\textrm{\textbf{提高}}}}	DP 延迟决策入门	FLY_lai	\colorbox{goldenrod}{\color{white}{\textrm{\textbf{原创}}}}	可以多看一些不同例子。
\colorbox{darkviolet}{\color{white}{\textrm{\textbf{省选}}}}	BSGS 应用和离散对数扩展	HaHeHyt	\colorbox{goldenrod}{\color{white}{\textrm{\textbf{原创}}}}	重点是复杂度平衡。
\colorbox{darkviolet}{\color{white}{\textrm{\textbf{省选}}}}	小波树和小波矩阵	staring	\colorbox{goldenrod}{\color{white}{\textrm{\textbf{原创}}}}	cascading 思想。压位划分树。
\colorbox{midnightblue}{\color{white}{\textrm{\textbf{集训队}}}}	格基约化 LLL 算法卡散列和补充	cancan123456 ← 恶魔妹妹	\colorbox{firebrick}{\color{white}{\textrm{\textbf{推荐}}}}	格基约化是整数上线性代数的基础性算法。

注：“大众”难度征集本人创作的 OI 相关知识优质大众科普视频/文章，可以涉及较难内容。

注：不会推荐低质量投稿，但并非只推荐质量最高的。

注：每期推荐有数量限制，本期投稿未被推荐的，仍会进入将来推荐的队列。

星尘[积分]累计排行榜

星尘[积分]达到 300 欢迎加入研讨群 QQ 1061507046

排名	星尘[积分]	投稿人
\mathbf{0}	\color{red}{\mathbf{2}}\color{black}{\mathbf{3680}}	\color{Teal}{\text{♛}} nzhtl1477 \color{Teal}{\text{♛}}
\mathbf{1}	\color{black}{\mathbf{5}}\color{red}{\mathbf{824}}	「佚名」（多人总和）
\mathbf{2}	\color{red}{\mathbf{5760}}	joke3579
\mathbf{3}	\color{red}{\mathbf{4896}}	FLY_lai
\mathbf{4}	\color{orange}{\mathbf{4384}}	autumoon
\mathbf{5}	\color{orange}{\mathbf{4128}}	wjyppm1403
\mathbf{6}	\color{limegreen}{\mathbf{3904}}	astrainfinita
\mathbf{7}	\color{limegreen}{\mathbf{3776}}	liaoz123
\mathbf{8}	\color{royalblue}{\mathbf{3584}}	UT
\mathbf{9}	\color{royalblue}{\mathbf{3328}}	murder_drones
\mathbf{10}	\color{royalblue}{\mathbf{2720}}	HaHeHyt

星尘[积分]本期新增排行榜

排名	星尘[积分]	投稿人
\mathbf{0}	\color{red}{\mathbf{+2}}\color{black}{\mathbf{1312}}	\color{Teal}{\text{♛}} nzhtl1477 \color{Teal}{\text{♛}}
\mathbf{1}	\color{black}{\mathbf{+5}}\color{red}{\mathbf{760}}	joke3579
\mathbf{2}	\color{red}{\mathbf{+4736}}	FLY_lai
\mathbf{3}	\color{red}{\mathbf{+4384}}	autumoon
\mathbf{4}	\color{orange}{\mathbf{+3904}}	astrainfinita
\mathbf{5}	\color{orange}{\mathbf{+3776}}	liaoz123

内容公开

↓↓↓点此查看整理后的投稿文档↓↓↓

【腾讯文档】小知识和思考题投稿（展示版）

更新：为投稿添加了编号 ID，格式为 \color{red}{\textbf{R+数字}} 的唯一标号！

鉴于腾讯文档不稳定、卡顿等问题，大家可以提议更好的展示方式。以及文件的展示方式。

↑↑↑点此查看整理后的投稿文档↑↑↑

本期稿件统计

前 10 专题	数
\colorbox{darkviolet}{\color{white}{\textrm{\textbf{数据结构}}}}	\color{darkviolet}{\mathbf{110}}	\colorbox{darkviolet}{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
\colorbox{MediumSlateBlue}{\color{white}{\textrm{\textbf{代数-分析}}}}\color{MediumSlateBlue}{↑↑↑↑}	\color{MediumSlateBlue}{\mathbf{65}}	\colorbox{MediumSlateBlue}{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
\colorbox{YellowGreen}{\color{white}{\textrm{\textbf{图}}}}	\color{YellowGreen}{\mathbf{47}}	\colorbox{YellowGreen}{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
\colorbox{CornflowerBlue}{\color{white}{\textrm{\textbf{序列}}}} \color{CornflowerBlue}{↓↓}	\color{CornflowerBlue}{\mathbf{36}}	\colorbox{CornflowerBlue}{~~~~~~~~~~~~~~~~~~~~~~~~}
\colorbox{Darkorange}{\color{white}{\textrm{\textbf{数论}}}}\color{Darkorange}{↑↑↑↑↑}	\color{Darkorange}{\mathbf{31}}	\colorbox{Darkorange}{~~~~~~~~~~~~~~~~~~~~~}
\colorbox{Tomato}{\color{white}{\textrm{\textbf{组合计数}}}}\color{Tomato}{↑↑↑↑↑↑↑}	\color{Tomato}{\mathbf{31}}	\colorbox{Tomato}{~~~~~~~~~~~~~~~~~~~~~}
\colorbox{violet}{\color{white}{\textrm{\textbf{枚举-状态-递推}}}} \color{violet}{↓↓↓}	\color{violet}{\mathbf{28}}	\colorbox{violet}{~~~~~~~~~~~~~~~~~~~}
\colorbox{deepskyblue}{\color{white}{\textrm{\textbf{优化-构造}}}}\color{deepskyblue}{↓}	\color{deepskyblue}{\mathbf{27}}	\colorbox{deepskyblue}{~~~~~~~~~~~~~~~~~~}
\colorbox{SkyBlue}{\color{white}{\textrm{\textbf{树}}}}\color{SkyBlue}{↓}	\color{SkyBlue}{\mathbf{27}}	\colorbox{SkyBlue}{~~~~~~~~~~~~~~~~~~}
\colorbox{SandyBrown}{\color{white}{\textrm{\textbf{字符串}}}} \color{SandyBrown}{↓↓↓↓↓}	\color{SandyBrown}{\mathbf{16}}	\colorbox{SandyBrown}{~~~~~~~~~~~}

统计范围为截至本期的累计有效投稿，不含完全重复的。

题外话

本期投稿中 NOIP2025 T4 序列询问 / query 的技巧内容：

R183. 带长度限制的区间统计（条状/梯形分治） - Guoyh ← liaoz123
R276. 定长分块（定距采样法） - nzhtl1477
R528. 倍增值域分块（倍增采样法） - 「佚名」

题目强度的向度 - 星语闲话第二期

\color{ForestGreen}{\text{欢迎来到魔法的世界。}}

\color{ForestGreen}{\text{你问你的契约和吉祥物去哪里了？不，不，不必藉由它们。}}

\color{ForestGreen}{\text{任何 OIer 都蕴藏着魔法的潜能。}}

\color{Crimson}{\text{◕\_◕ 萌新的眼神}}

\color{ForestGreen}{\text{…魔法只取决于两点：}}

\color{ForestGreen}{\text{第一是\textbf{世界的规律}，第二是\textbf{你内心的愿望}。}}

\color{ForestGreen}{\text{接下来，我将要向各位演示魔法的\textbf{世界体系。}}}

\color{Crimson}{\text{◕\_◕}}

\color{ForestGreen}{\text{…}}

\color{Crimson}{\text{◕\_◕}}

\color{ForestGreen}{\text{… …}}

\color{Crimson}{\text{「从题目难度讲起」，每次都是这么说的喔。}}

\color{ForestGreen}{\text{…对，对啦！魔法的基础是单一的法术，也就是题目。}}

\color{Crimson}{\text{「我们最关心题目的\textbf{强度}，度量题目的强度即是魔法理论的起点。」}}

\color{ForestGreen}{\text{你也许觉得，这不就是\textbf{难度}高低的简单问题吗？}}

\color{Crimson}{\text{「但怎样区分科技题，推导题，结论题和代码题呢？」}}

\color{ForestGreen}{\text{可见，单一的\textbf{难度}不足以评价问题。}}

\color{Crimson}{\text{「就像\textbf{运动}的世界中有能量、动量、角动量种种度量那样。」}}

\color{ForestGreen}{\text{魔法的世界中，\textbf{难度}也并不单一。}}

\color{Crimson}{\text{「然而，魔法学和运动学有一项最重要的区别。」}}

\color{ForestGreen}{\text{那就是\textbf{社会性}。}}

第一，所有的强度都是社会属性，而不决定于题目自身。
- 对于不同的社会群体，乃至同一群体的不同时间而言，难度是不同的。如果一道题是入门必修课的习题，它便是常规的，难度也会降低；如果从未学过，便是科技的，难度也会提高。对于数学专业组合设计背景的学生，组合设计是一种常规，反之则可能是 Ad-Hoc 的代名词。十年前的特异可能随文明发展变为某个更普遍理论的常规。百米外的同学可能有着完全不同的交流范围和知识偏向。
- 一言以蔽之，只有对于个别具体的时间、地点、人群（或个人），难度和所有其它强度才是确定的。
- 题目内容本身是强度的根基，但却不足以确定强度。
- 当我们不加描述地讨论时，时间是现在，地点和人群是 OIer 社群的总体。
第二，所有的强度都是社会需要，而不回答于题目自身。
- 只有在社会中，具体是在教学活动中，强度才会被讨论。
- 个人在学习和研究中，教育工作者在教学研究中，以至认知科学研究或让 AI 做算法题的工作中，为了分析和设计学习过程，才关注了题目的强度。
- 国家的教育计划，团体的办比赛计划，个人的分享，才会对自己的题目提出强度要求。好题具体是怎样的？我需要简单还是难，科技还是特异？
- 因此，强度不是题目内容本身，不是一个语言片段，不是一个数学理论。题目是人类社会的教学和研究中，形成理论和解决问题所必须经由其中介的例子，题目强度是人类社会的教学活动提出的认识需要，而不是题目本身自洽的一部分。当然，这里的题目可以推广到所有学习中使用的「例子」。
- 题目本身内容，大致就是 题意，题目描述，题解，标程，测试数据（分布） 的集合和它们表达的数学对象。
  - 注意，这里题目描述形式也是题目的一部分。“输出：非负整数个 a,b 求和不能得到的最大自然数”和“输出：ab-a-b”显然不是同一个题。

\color{Crimson}{\text{就是这样！}}

\color{ForestGreen}{\text{因此，只要回答一个问题：学习或办比赛时，如何刻画\textbf{需要}的题？}}

\color{Crimson}{\text{「要区分思维难度和代码难度？」}}

\color{ForestGreen}{\text{「要体现重点是理论视角还是细节推导。」}}

\color{Crimson}{\text{「要判断在同学中是不是广为人知？」}}

\color{ForestGreen}{\text{「要强调问题描述是否自然不刻意。」}}

\color{Crimson}{\text{「要看是个别问题，还是某个普适理论的起点？」}}

\color{ForestGreen}{\text{就是这样！}}

题目强度的向度

度量	教育学术概念	同类名词	含义	社会易变性
\colorbox{Tomato}{\color{white}{\textrm{\textbf{难度}}}}	\color{Tomato} \mathbf D\mathrm{ifficulty}	等级难题	自主解题者的总体成绩是否高。	较高
\colorbox{Darkorange}{\color{white}{\textrm{\textbf{冷度}}}}	\color{Darkorange} \mathbf O\mathrm{bscurity}	普及度流行度偏题①	该问题和解决方法/理论是否鲜为人知，是否少有原题或类似题目。	极高
\colorbox{#f8d000}{\color{white}{\textrm{\textbf{科技度}}}}	\color{#f8d000} \mathbf S\mathrm{ophistication}	前置知识偏题②	该问题典型研究方法/解法难点是否需求专门数学理论基础或其它理论基础。	中
\colorbox{LimeGreen}{\color{white}{\textrm{\textbf{特异度}}}}	\color{LimeGreen} \mathbf I\mathrm{diosyncrasy}	奇异度反常度常规度普适度可推广性怪题①	该问题典型研究方法/解法是否很难被推广，很难成为解决多种问题的泛用理论。	中
\colorbox{LightSeaGreen}{\color{white}{\textrm{\textbf{刻意度}}}}	\color{LightSeaGreen} \mathbf C\mathrm{ontrivance}	自然度怪题②	该问题描述是否冗长，复杂且刻意。	低
\colorbox{DodgerBlue}{\color{white}{\textrm{\textbf{硬度}}}}	\color{DodgerBlue} \mathbf T\mathrm{echnicality}	推导复杂度繁题①	该问题是否在找到正确的理论刻画、思考方向之后仍然要进行大量细节推导。	低
\colorbox{Violet}{\color{white}{\textrm{\textbf{码度}}}}	\color{Violet} \begin{aligned} \mathbf M & \tiny \mathrm{~= Implementation~Complexity, } \\ & \tiny \mathrm{Coding~Overhead} \\ \end{aligned}	实现细节繁题②	该问题是否实现细节复杂困难，代码冗长。	中

社会易变性：指的是具体问题的这一度量，受社会具体环境变化的影响高低。易变性高的度量可以被少数人轻易改变，在不同的人群看来也有极大差异。易变性低的度量只有在全学科乃至全人类文明整体发生大变化的时候才会被改变，并且天南海北的认识也更加一致。当然，问题本身内容没有变是前提。如果对一个原本认为困难的问题突然发现了新的简单做法，那么问题本身的内容已经被改变了，它的全部当然都要变化。

对于我们的默认讨论环境，即 OI 社群来说，冷度可以在出题的几个星期（如果是热门平台如正式比赛的题，甚至是几天）内就发生变化。大部分题目的难度评价也会在三四年内发生显著偏移。随着对问题认识的深入，特异问题变为科技问题——其本身被推广，或者引入了可刻画之的大理论，也是屡见不鲜的。

这是 OI 教学研究对问题强度的基本度量。教学和学习时对题目的要求，「怎样的题是好题？」，「我想要怎样的题？」，基本可以由这些属性来刻画。当然，这里的题目仍然可以推广到所有学习中使用的「例子」，比如小理论也可视为大研究方法或理论的例子，并适用这些度量。

这些度量全部按照强度从低到高的方向设置，也就是说当两道题拼接在一起时，合成题的每一项强度都是取大值而不是取小。因此我们用冷度而不是热度，用特异度而不是普适度，尽管后者听起来顺口。

更多的细节属性和度量，通常也可统领在这些之内。例如，“码度”可以继续细分为代码长度，琐碎细节[Fiddliness]，代码层面的常数优化需求等。“科技度”也可以细分为算法和数学上的“高级”或冷门理论需求，和外部知识需求（如多边形下海）等——不过通常科技指的是前者，而后者被认为不该出 OI 题。

现在，我们来看看如何用这一体系描述那些我们耳熟能详的话语。

OI 社群用语

Ad-Hoc Ad-Hoc 原本在数学上的核心含义就等同于特异度。然而，在 OI 使用中该词衍生出了更多含义，可以刻画为高冷度 + 低科技度 + 中高硬度 + 中高特异度。
套路套路在 OI 中有很大的歧义，不同人在不同地方使用“套路题”表达低冷度，高科技度，低特异度这些截然不同的概念，这是很多争论的根源。

Competitive Programming 社群用语

知识密集型、推理密集型、观察密集型 分别对应问题科技度、硬度、特异度的相对大小。部分算法竞赛教研相关项目例如大语言模型测试集 LiveCodeBench Pro 使用此表述。

教师习惯中文用语

偏，难，怪，繁：这七个度量中除了总括的难度之外，其余六点对应偏，怪，繁分为三对，详细解释了它们在 OI 的具体结构。因此，这三对概念内部是有较强内在联系的。科技度高的问题通常不太可能普及，冷度不会低。刻意度较强的问题通常很难推广普遍理论，特异度也不太可能低——或者说能作为经典理论起点的问题，不可能被人类视为刻意不自然的。
区分度，信度，效度：区分度，信度[reliability]和效度[validity]是刻画题目是否适用于评价性，选拔性考试的统计有效性度量，其基本假设为选手水平是先验的，而将考试成绩视为测量工具进行分析。然而，OI 现实中用于反映它们的主要统计指标只有单次测试中选手成绩分布的离散程度以及多次测试中高低分的选手的一致性。然而，实际上，区分度主要取决于比赛组题以及部分分设置而非题目的核心内容，而信度和效度在 OI 同样不是主要问题。不同测试之间同一选手排名的波动，仅能反映统计学信度，并不能实际反映效度乃至任何 OI 真正关心的内容。 基本上说，特异度和硬度高的题目，会显著增大偏差（降低信度），而冷度低的题目（套路题和原题），会显著降低偏差（增加信度）。这几个统计学指标在 OI 题目缺乏实际作用，不应重点关注。

评测强度

以上度量均针对题目内容，不包括评测强度，即实际评测和预期的评测数据范围分布之间的误差。

不能简单认为全卡掉就是好。“差一点边界情况正确”的程序应该多少分并非共识，无法数学定义的概念也不可能在题目里说明。
渐进误差 指问题本想考察渐进复杂度，和实际运行结果的误差。例如多 \log 水过和卡常数。渐进误差按照多造数据是否能卡掉，也可分为可去的——数据弱，和不可去的——数据范围内常数问题。
- 但实际上很难证明一个程序不会因为缓存等被卡。通常我们认为还没人能卡掉就等于对。
环境误差 在不同评测环境，同一评测环境的不同次数运行的波动误差，主要影响因素有缓存等。
- 交互题直接计操作次数。（最常用）
- 操作系统消除同环境误差（评测鸭等）
- 用指令开销代替实际运行时间（wasm，ebpf 等）（但不推荐在非专门设计的题上直接用此方式代替实际时间）
数据误差 数据太弱了，被错误算法过了，存在确定的数据可以高概率卡掉。即乱搞过题。
- 有些乱搞可能实际上是对的，只是我们不会证明或者很多年后才会证明。
- 通常我们认为测试数据组数不能太多。例如禁止通过添加 10^4 组数据打包测试卡掉一个错误率约为 0.03\% 的随机算法
- 通常正式比赛中我们会将程序中的伪随机数，以及一些可以替换为随机的常数视为随机的，而禁止针对特定模数卡散列等，因为 C++ 生成真随机数或者在编译期生成随机数会变慢或者难写等。

\color{Crimson}{\text{所以说啦，我们谈论的是魔法的\textbf{世界体系。}}}

\color{ForestGreen}{\text{\textbf{世界体系}，就是刻画世界的基本图景，是研究魔法世界的起点。}}

\color{Crimson}{\text{「那么，你心目中的好题\textbf{具体}是什么呢？」}}

\color{ForestGreen}{\text{「… …秘密。」}}

\color{Crimson}{\text{「…『USsR：\textbf{O↑↑ S↓↓ C↓ T↑}』…」}}

\color{ForestGreen}{\text{「喂！把我的魔法书还我！」}}

\color{Crimson}{\text{… … … …}}

也许此时，在另一个世界里，有人正写下自己出毒瘤题的愿景，有人正因对自己视为生命的艾德豪克的真身惊鸿一瞥，而虚无着颤抖。

\color{ForestGreen}{\text{… … … …}}

\color{Crimson}{\text{「一切如常，结末的钟声响了。」}}