归档 - NOI Blog

2025-07-24

#图论 #笔记 #平衡树

前置二叉搜索树 BST BST 有以下两个性质：二叉树节点的权值始终为 left<root<right。堆 Heap 所有父亲的值都不大于两个儿子的值的完全二叉树，叫做堆。即 root \leq left 且 root \leq right。树堆 Treap Treap 的节点维护两个信

抽象线段树理论

2025-07-23

可能更好的阅读体验 0.前言侧重于理论以及做题大方向，方法论的指导。本博客若没有特殊说明，所有变量默认取值范围为 \mathbb{Z}。 1.半群线段树 1.1 定义我们都说，线段树能维护具有结合律的信息，不能维护没有结合律的信息，那么为什么线段树只能维护有结合律的信息呢？这里我们可以利用半群

浅学竞赛图

2025-07-17

#图论

可能更好的阅读体验翘课写笔记。 1. 定义竞赛图，即任意两点之前有且仅有一条边的有向图。即有向完全图，有 \dbinom{n}{2} 条边。至于为什么叫竞赛图，就是赢得点向输的点连边，一个边代表的是胜负关系。 2. 性质兰道定理（竞赛图判定）我们定义比分序列为将每个点的出度 s_{i} 从

根号分治——平衡规划思想的应用

2025-07-16

1. 介绍与引入没有前言，懒得写了。根号分治，本质是平衡规划思想（大纲 9 级），在预处理和询问复杂度中寻找平衡，我们通常用根号作为问题规模的分界线。我们确定一个界限 B，小于 B 的暴力预处理，大于的回答一次时间只需要 \dfrac{n}{B}\le \sqrt{n} ，那么整个题目就可以做到

7.16 神秘课程

2025-07-16

P3773 [CTSC2017] 吉夫特 - 洛谷昨天的残存内容，一道非常优雅且神奇的卢卡斯定理的应用。它告诉了我们，卢卡斯定理除了屎以外，还有一个和 OI 关联性很高的用法，即将组合数转化为和 p 进制相关的内容： \begin{aligned} \dbinom{n}{m} \bmod p &

整体二分

2025-07-15

本来感觉挺神秘的一个东西，学完了似乎没有多难，放几个板子随便写写吧（今天数学不想做题）从最最最最人尽皆知的区间第 k 大问题开始吧引入如果我想问你一个序列中的区间的第 k 大，你会如何？显然我们直接二分就行（主席树学傻的滚）时间复杂度为 O(nlogn) 感觉挺不错的呢但是如果我们有

2025.7.15模拟赛赛后

2025-07-15

#题解 #笔记

0.前言省流：\text{Rk } 1 \to \text{Rk 3},305 \to 255。 T1 虎爷ywk 判断是否存在正整数 n，使得 k|n^2，但 k 不能整除 n，若存在输出最小的 n，否则输出 -1。 1\le k \le 10^{12}

图论优化建图

2025-07-12

0. 前言会添加的吧，会添加的吧？一定会添加的吧！水文章？ 1. 线段树优化建图 CF786B Legacy 区间向区间连边，我们可以利用线段树的优秀区间特性来进行连边。具体来说，我们建立两颗线段树，一颗专门管入边，一颗管出边入边的树父节点向子节点连边（如果子节点向父节点连边，会导致本来只连向该

2-SAT 学习笔记

2025-07-05

#图论

才发现自己之前看的 2-SAT 模板题题解赤到石了，到最后不过是背过了板子题的代码罢了。做了一些题之后渐渐懂了一些，有了一些自己的见解。它能解决一类问题类似一个序列，每个位置只有两个取值，然后取值间有一些限制，求解其是否有解以及求一个可行解。考虑每个位置拆分为两个点，分别为 i 和 \neg

后缀数组全家桶-从哈希乱搞到入门

2025-07-03

#字符串 #笔记 #题解

可能更好的阅读体验 0. 前言后缀数组是信息学竞赛中解决字符串匹配的一大利器，其思想和实现非常简单。虽然倍增加排序的思想很简单，但是它的拓展 ht 数组功能及其强大并且适用性广，在 OI 范围内广泛应用。以下应用魏老师的一句话：几乎所有字符串算法都存在一个共性：基于所求信息的特殊性质与已经求出

菜单