前言

北方之家开启啦！首先，对于想贡献力量的你，北方之家的题目都有哪些规则要遵循呢？
当然，如果你发现某一道题目不符合这个规范，也可以向我提出哦！ \(\text{qwq}\).

\(\text{Idea}\)

首先，这个题目的 \(\text{Idea}\) 不应该是以下内容：（ 这只是原创题的要求哦 ）

• 与大型网站出现重题，这包括完全相同、思路相同、思路基本相同几种。
• 广为人知的模板题 / 硬性拼合模板 / 大型数据结构现场。
• 题目不难但过度卡常。

题面

题面和题的关系好比是人脸和人的关系，一看就知道你这道题的外在怎么样。

如果不会 \(\text{Latex}\) 的萌新可以参考 这里.所有公式、字符、常数等均因使用 \(\text{Latex}\) 公式；当然也不能滥用。

题目背景

题目背景应力争 简短，哪怕只是故事情节，也要做到简明扼要；并且较长时应当与题目正文分开，绝对不能让题目背景影响了对题目的理解。可以不写。

题目描述

题目描述应力争 清晰易懂，字数最好少一点，概括起来。字数比较多最好分段。这里有个反面例子：

洛谷 P1829 [国家集训队]Crash的数字表格 / JZPTAB，题目描述说了一大段，实际上都不如这一行来的更简明：

给定 \(n,m\)，求 \(\sum_{i=1}^n \sum_{j=1}^m \operatorname{lcm}(i,j)\).

输入 / 输出格式

输入输出格式应力争 完整无误：多个并列变量合并为一个公式；用作序号的数字建议使用中文；特定字符串用 行内代码块 标出。

样例

样例应力争 完整有强度，每个特殊的 \(\text{Subtask}\) 都应该对应一个样例，多种操作时每个样例应当出现；并且 样例能让读错题意的人发现错误，杜绝给一些非常简单的样例。反例如下：

---

题意：求 \(\sum_{i=1}^n (i^2 + i + 1)\) 的值，对 \(10^9+7\) 取模。

样例输入： \(0\).

样例输出： \(0\).

---

毫无价值的样例不应当出现。

样例说明

样例说明应力争 简明无误，在简短的情况下让大家知道答案的来由。

数据范围

数据范围应力争 科学多元，分层清晰，\(\geq 10^3\) 的数最好使用科学计数法；如果有捆绑测试应 加粗体说明；公式与公式用全角字符隔开；应说清楚层次；并且最后应说明对于 \(100 \%\) 的数据情况。

数据

数据应力争 全面，考虑到各种算法的不同得分和反例。不毒瘤，按照层次即可。一个 \(\text{Subtask}\) 一般 \(5 - 10\) 个数据，送分的可以只有 \(1\) 个。

时空限制

时空限制应力争 正常，卡掉复杂度不对的算法，并且应在 \(\text{std}\) 最坏情况下的 \(1.5\) 倍（如果是卡常题则可以另外考虑）。

题目标注

三部分：标签、分类和难度。

• 标签：来源，所属赛事等。
• 分类：算法，数据结构等。

• 难度：本域难度均为管理指定。详细内容如下：

• \(1\)：入门难度，只需要用顺序结构 / 分支结构即可解决的问题。如 \(\text{A+B Problem}\).

• \(2\)：普及 \(-\) 难度，即稍加思索即可解决的题，包括简单递归、简单循环（分支）等，如 \(\text{格雷码}\).

• \(3\): 正统普及难度，对应基础搜索、初级数据结构（如并查集，前缀和，差分）、线性动态规划、简单贪心、简单树，基础博弈论等，其难度大致为 \(\text{PJT2}\).

• \(4\)：提高 \(-\) 难度，对应有简单优化的搜索，简单的数学推导，较难贪心，二维或较难动态规划，较有难度的博弈论等，其难度大致为 \(\text{PJT4}\)$.

• \(5\)：正统提高难度，对应中级数据结构（如 \(\text{ST}\) 表，线段树，树状数组等），数学推导与贪心更上一层，动态规划的简单优化，较难的剪枝搜索，图论的一些模板，其难度大致为 \(\text{TG Day2T1}\).

• \(6\)：省选 \(-\) 难度，包括杂烩搜索优化，各种模板，数学进入推式子阶段，贪心与动态规划的结合，动态规划的各类高级优化，以及各种数据结构与算法的混合运用，甚至是图论的极难模板（割点），其难度大致为 \(\text{TG Day2T2}\).

• \(7\)：正统省选难度，对应高级数据结构（如平衡树等），各类更难一层的模板，数学进入莫反基础的阶段，贪心极难思考，动态规划高级优化进入炉火纯青的境界，图论建模与模板均属上乘难度，且题目性质不易被发现，其难度大致为 \(\text{SX Day2T1}\).

• \(8\)：难度直至上乘，应保证通过率不高于 \(10^{-5}\). 这里有的，是非常难的模板，数学进入高等数学模块，函数推导、莫反结合、推论卷积、甚至是与图论相结合的境界。动态规划一般是在 \(6 - 7\) 的模板题上再经高难优化，各种高级数据结构的混合运用提升了码量。在这里，你可以见到很多大赛的压轴题目，码量一般在 \(3k\) 以上，其难度大致为 \(\text{SX Day2T3}\).

• \(9\)：最终的难度，应保证通过率不高于 \(10^{-7}\)，数学变成了大量理论的堆积，比方说是 “\(\text{gcd}\) 性质 + 莫比乌斯反演 + 卷积 + 建模 + 大型图论模板 + 卡常”的一道思博题。动态规划基本无法到达这样的高度，一些大力模拟题，码量若在 \(5k\) 起步，可以到这个难度。树上问题也有的是 “换根 \(\text{dp}\) + 推式子（又是莫反，卷积，线筛）+ 高级动态规划优化 + 码量”。该类问题的部分分可以到 \(6 - 8\) 难度，并且一档部分分往往是一个新的算法，需要进行不断的改进与优化才能得到正解。其难度不封顶。