wjyppm's Blog

0. 前言 抽象代数警告！ 你需要有： 集合论芝士 一颗清醒不头痛的大脑 1. 群 1.1 群的定义 设 GGG 是非空集合，其上有二元运算 ×\times× （这不是单纯的乘号，这里是抽象代数你应当有这种意识）。若这个运算满足以下四个性质，我们称其为一个群，记为：(G,×)(G,\times)(G,×)。 封闭性 若存在 aaa 和 bbb 满足 a∈G,b∈Ga\in G,b\in Ga∈G,b∈G，则有 a×b∈Ga\times b \in Ga×b∈G。 结合律 对于任意 a,b,c∈G,有(a×b)×c=a×(b×c)a,b,c \in G,\text{有}(a\times b)\times c=a\times (b\times c)a,b,c∈G,有(a×b)×c=a×(b×c)。 单位元 ∃e∈G\exists e\in G∃e∈G，满足对于任意 a∈Ga\in Ga∈G，有：a×e=e×a=aa\times e=e\times a=aa×e=e×a=a。 这样的 eee 称为单位元，并且单位元唯一（如果有多个很容易看出来矛盾） ...

0. 引入 你需要的前置： 一颗清醒的大脑（因为这是抽象的东西） 概念基础辨析 集合（高一数学必修一） 1. 序理论 1.1 定义与二元关系 序理论是研究捕获数学排序的直觉概念的各种二元关系的数学分支。——百度百科 数学排序？这个我会啊，不就是排序吗…？ 其实这里并不指的是单独的排序。 既然有不同的点，那么特殊在哪里？ 先来一个小定义： 笛卡尔积：设 X,YX,YX,Y 两个集合，那么存在一个集合，它的元素是用 XXX 中元素为第一元素，YYY 中元素为第二元素组成的有序二元组，称它为集合X,YX,YX,Y的笛卡尔积集，记为 X×YX\times YX×Y。 X×Y={(a,b)∣a∈X,b∈Y}X\times Y=\left\{ (a,b)|a\in X,b\in Y \right\}X×Y={(a,b)∣a∈X,b∈Y} 怎么理解？类比一下C++中的pair容器吗。 例如 X={1,2},Y={a,b,c}X=\left\{ 1,2 \right\},Y=\left\{ a,b,c \right\}X={1,2},Y={a,b,c}，那么有X×Y={(1,a...

0. 前言 因为之前一篇写的太烂了，没有搞清楚主次关系导致云里雾里，以至于后人（没错就是我自己）根本看不懂，所以本篇于2025.4.22重写。 你需要知道芝士： Tarjan求有向图强联通分量 基础图论建模芝士 命题的概念及反命题（初中内容） 1. 2-SAT概念及求法 1.1 概念 这个我们需要好好说这个概念，所以我们对于 “2-SAT” 这个名词我们做一下辨析。 SAT 是适定性（Satisfiability）问题的简称。一般形式为 k - 适定性问题，即 k-SAT。 什么，看不懂？没关系因为这个k-SAT问题当 k>2k>2k>2 的时候是NP完全问题，只能暴力求解，但是当 k=2k=2k=2 的2-SAT问题我们可以好好玩。 对于2-SAT问题通俗的说，就是给你 nnn 个变量 XiX_iXi​，每个变量只能取 0或1，同时给定若干条件，形如： (¬)Xi⊕(¬)Xj=0/1(\neg) X_{i}\oplus (\neg)X_{j}=0 /1 (¬)Xi​⊕(¬)Xj​=0/1 其中 ¬Xi\neg X_i¬Xi​ 表示 XiX_iXi...

0. 前言 你需要知道： SPFA 图论基础建模 不等式基础 1. 负环 为什么先讲负环啦？是因为差分约束是要用负环的。 给定一张有向图（无向图看作两条等权边），每条边有权值。若一个边权值是负数，那么我们称这个边为负权边。 若图中存在一个环，如果环上的边有负权边，那么我们称这个为负环。 例如4,5,7构成负环，而5,8,1构成正环 我们可以用最短路算法来跑判断负环，什么你跟我说拓扑排序？如果一张图既有正环也有负环那判断不出来啊，拓扑只能判环不能判是哪个类型的。 但是不是所有都能用… 算法 适用条件 时间复杂度 Dijkstra 不可以，负边权会对之后结果造成影响不一定最小。 O(n2)→O(mlog⁡n)O(n^2)\rightarrow O(m \log n)O(n2)→O(mlogn) Bellman-Ford 可以，无负环的时候最短路边数一定小于 nnn ，无负环的情况下走n−1n-1n−1 次后一定收敛。 O(nmO(nmO(nm) SPFA 同Bellman-Ford O(nm)→O(km)O(nm)\rightarrow O(km)O(...

0. 前言 你需要的知识点： 图的遍历与存储（这都会吧。。。） 树的直径与树上最大独立集（没有上司的舞会）等树形DP基础芝士 环的认识 1. 基环树基本芝士 1.1 概念 想必都知道树结构的特点吧。 给定一张 nnn 个点，n−1n-1n−1 条边的无向图，… 这个就是树的特点，有 n−1n-1n−1 条边。而基环树呢？就是在原先树的情况上加了一条边，于是基环树的特点就是： 给定一张 nnn 个点，nnn 条边的无向（或有向）图，… 那长什么样？ 那有人就会说链，这根本就不是树啊，这有环怎么能叫树呢？事实上也是这样的，人家是个图吗。 比一般的树多一条边，这导致这个基环树图上出现了一个唯一的环，这个的前提是图联通。如果不联通，就会出现多个环，例如下图： 当然，基环树也有有向图的版本，这个版本有2个，一个叫内向基环树，一个叫外向基环树。 1.2 找环 我们对于基环树的处理一般是找到他最特殊的地方，也就是他的环。 怎么找环呢？其实也很简单，我们分无向的和有向的来分别说。 1.2.1 并查集（无向图） 复杂度均摊O(1)O(1)O(1)。 无向图我们可以使用并...

0.前言 你需要的必备芝士： 图的存储与遍历。 DFS序。 线段树的基础应用。 LCA的概念与性质。 准备好了？Let’s GO! 1.重链剖分 什么是树链剖分？他是干什么的？ 树链剖分，字面意思就是将树剖成一条一条链，让后我们利用这些链来维护树上路径的信息。 那我们举个例子吧。 nnn 个点的树，有 mmm 次操作，每一次操作将树上 x→yx\rightarrow yx→y 的路径都加 111 的权值 ，求树所有节点的权值之和。 不难发现树上差分。直接差分做一做就可以了，不知道的可以看我的博客。 但是如果我想求路径的值呢？ nnn 个点的树，有 mmm 次操作，每一次操作将树上 x→yx\rightarrow yx→y 的路径都加 111 的权值 。 给定 qqq 次询问，询问最短路径 u→vu\rightarrow vu→v上的权值之和 这个时候问题就不一样了，仅靠差分的话复杂度会炸成 O(nq)O(nq)O(nq)，怎么办？如果这个问题我们不放到树上，我们就是一个数组的操作，很简单对吧，线段树和树状数组都可以轻轻松松的做到，但是放到树上怎么做我们肯定是不会的...

换根DP 树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。 他相比于相比与一般的树形dp拥有以下特点 以树上不同点作为根，他的解不同 求解答案，不能单求解某点的信息，需要求解每个节点的信息。 无法用一次搜索完成答案求解。 难度不算太高 1.例题引入 P3478 [POI 2008] STA-Station 给定一个 nnn 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。 一个结点的深度之定义为该节点到根的简单路径上边的数量。 我们先假设某个节点为根（例如1为根），将无根树转换为有根树，再通过一次DFS搜索出以该节点的深度和，时间复杂度O(n)O(n)O(n) 但问题是我们无法确定以该点为根时一定能得到最优解，如果可以的话可以拿样例推推，可以显然发现以任意点为根无法确定是最优解（例如从1开始） 没错这个树长得很奇怪。 我们可以在第二次搜索时完成对答案的统计。 我们假设第一次搜索我们从1号节点出发，通过一次搜索我们就可以获得所有节点子树的大小与节点深度，...

0.前言 位运算记不记得？ (n>>k)&1 取出非负数n的第k位 n&((1<<K)-1) 取出非负数n的后k位 n^(1<<k)把非负数n的第k位取反 n^(1<<k)把非负数的第k位取反 1.定义与例题引入 状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。 ——oiwiki 那么怎么个状态压缩法呢？ 例如这个题： P1896 [SCOI2005] 互不侵犯 在 N×NN \times NN×N 的棋盘里面放 KKK 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 888 个格子。(1≤N≤9,0≤K≤N×N1\le N \le 9,0\le K \le N\times N1≤N≤9,0≤K≤N×N) 这里我们发现好像我们可以设几个状态，分别是放到第几行，放了多少个国王，和如何放置的。前两个都好说，但是第三个却让我们很头疼。如果按照常规思路来想，我们肯定会开一个非常非常大的数组来表示这个放置...

0.引入 我们在写KMP的时候会求出来长度为nnn的字符串的前缀最长border的长度为Next[n]Next[n]Next[n]，接下来先介绍一个border 定义：对于一字符串SSS，用∣S∣|S|∣S∣表示其长度，后面我们简化用lenSlen_SlenS​来表示，那么SSS串的一个Border一定是SSS串的一个前缀，并且他前缀和后缀都能够相互匹配。举个例子，比如说“BeckyBe”的一个border就是Be,一个字符串的border可能有多个，但在这里我们要求的是最长的border 对于任意一个字符串SSS，一个Border的长度就对应一个Border（比如说上面的长度为2各border只能是“Be”），我们可以求出他所有border的长度分别为ne[ne[ne[lenSlen_SlenS​]，ne[ne[ne[ne[ne[ne[lenSlen_SlenS​]]]]]] 以此类推直到为0。根据上面的结论，我们可以知道，对一个字符串S求解next数组之后，我们就知道了S所有前缀（包括S自身）的所有Border了。 1.Fail树 fail树就是把所有next[i]n...

数论——从入门到入坟 注：线性代数并不算于这篇文章 0.前言 数论应该算是oi里面一个比较算是重要的章节了吧，他在大纲内标得难度居然比平衡树还简单？听老师说这个难度其实是按学起来的难度表的。应用起来和平衡树的区间操作一样难。 故借一个下午，整理数论笔记，重新思考思考一下吧。 数论研究的是整数的性质，但是性质要好多啊啊啊。一个一个慢慢学吧. 1.扬帆启航——整除 整除应该早就在小学中学过他的概念了。这里我们添加几个符号来表示整除，并且重新复述一遍定义。 若aaa和bbb为整数，aaa整除bbb。则b是a的倍数，a是b的约数（或者也可以叫做因数），我们记为a∣ba|ba∣b。整除的大部分性质都是显而易见的，如下 1.任意性 若a∣ba|ba∣b，则对于任意非零整数mmm，有am∣bmam|bmam∣bm。 2.传递性 若a∣ba|ba∣b且b∣cb|cb∣c，则a∣ca|ca∣c。 3.可消性 若a∣bca|bca∣bc且aaa与ccc互素，则a∣ba|ba∣b 4.组合性 若c∣ac|ac∣a且c∣bc|bc∣b，对于任意整数m,nm,nm,n，有c∣(ma+nb...