首页/全部级别/NOI

NOI

21 个知识点

全国青少年信息学奥林匹克竞赛

C++21 个知识点

高级数据结构

4 个知识点

树链剖分、动态树、可持久化数据结构

困难

树链剖分：把大树切成链，轻松找路径

树链剖分是一种将树形结构分解成若干条链，从而用线段树等数据结构高效处理路径查询和修改问题的方法。

困难

动态树（Link-Cut Tree）：会变形的树

动态树（Link-Cut Tree）是一种可以快速连接、切断和查询路径信息的树形数据结构，特别擅长处理动态变化的森林。

困难

可持久化线段树（主席树）：时光倒流的区间查询

可持久化线段树（主席树）可以保留每次修改的历史版本，让我们能随时查询过去某个时刻的区间信息，常用于求区间第K大等问题。

困难

可持久化Trie：能返回过去的字典树

可持久化Trie（前缀树）可以记录每次插入操作的历史版本，用于查询之前任意时刻的字符串或二进制数信息，如最大异或值等。

字符串算法

3 个知识点

AC自动机、后缀数组、后缀自动机SAM

困难

AC自动机——会自我纠错的查词器

用字典树和失败指针，一次性找到所有可能的单词，就像在错别字文章中自动发现正确单词。

困难

后缀数组——把所有尾巴排个队

把字符串的所有后缀按字典序排序，然后就能快速找出重复子串、最长公共前缀等秘密。

困难

后缀自动机——最聪明的压缩大师

用最少的节点和边，记住一个字符串的所有子串，还能告诉我们每个子串出现了多少次。

图论算法

4 个知识点

网络流、费用流、虚树、点分治

困难

最大流（Dinic算法）—— 水管里的水流游戏

想象一个水管网络，水从源点流到汇点，每根管子能通过的水量有限，我们需要找到最多能流多少水。

困难

最小费用最大流 —— 花钱最少的水路

在最大流的基础上，每条管子流每单位水要付运费，我们要在运最多水的前提下，让总运费最少。

困难

虚树 —— 只留重要节点的树

一棵大树上有一些关键节点，我们只保留它们和它们之间的“必要”连接，大幅减少节点数量，方便计算。

困难

点分治 —— 分而治之的树上统计

把一棵大树从重心切开，分别处理每个小部分，再合并结果，适用于统计路径等树上问题。

动态规划

2 个知识点

动态DP、插头DP、轮廓线DP

困难

动态DP（DDP）——快速更新问题的智慧

用游戏角色升级的例子，学会用“魔法线段树”快速重新计算动态规划结果。

困难

插头DP（轮廓线DP）——拼图游戏中的智慧

用“插头”记录拼图边界，像搭积木一样一格一格填满网格。

计算几何

3 个知识点

凸包、旋转卡壳、半平面交

困难

凸包——用Graham扫描法给点群“围栅栏”

就像用一根橡皮筋围住一堆钉子，凸包算法能找到所有点最外层的“凸多边形”。

困难

旋转卡壳——像卡尺一样旋转求最远点对

旋转卡壳是一种在凸包上“旋转标尺”来快速找到最远距离或最大面积的方法。

困难

半平面交——用剪刀裁剪出一个多边形

半平面交就像用无数把“半无限大的剪刀”同时裁剪，最后留下满足所有条件的区域。

数学进阶

5 个知识点

FFT、莫比乌斯反演、斯特林数、线性基

困难

FFT快速傅里叶变换

用“果汁配方”的故事教你如何快速把两种味道的果汁混合起来，再分开找回原来的味道。

困难

莫比乌斯反演

用“数星星”的例子帮你理解如何从一堆数中找出隐藏的规律。

困难

第一类斯特林数

用“分座位”的故事帮你理解把n个人分成m个圆排列的方案数。

困难

第二类斯特林数

用“分盒子”的故事帮你理解把n个不同的球放入m个相同的非空盒子的方案数。

困难

基与线性基

用“数字积木”的方法帮你从一堆数中找出能组合出所有数的最小“基”。