在文章《《洛谷 - 梦回考场》发布——题目页面致郁美化》发表评论：

不是哥们怎么提交（虽然不忍打破114条评论）

# 条件概率 - 条件概率$P(A|B)$，表示时间A发生时B发生的概率。 - $P(A|B)$表示$A,B$同时发生的概率 $$P(A|B) = P(A|B)=\frac{P(AB)}{A}$$ # 条件概率公式 - 指将一个复杂事件的概率分解为在不同情况下发生的简单事件的概率的总和。 - 具体来说，如果有一个复杂事…

# pre - 加法原理 - 减法原理 # 排列 A $P^m_n=A^m_n=n(n-1)(n-2)...(n-m+1)=\frac{n!}{(n-m)!}$ # 组合 C $C^m_n=\frac{A_n^m}{A_m^m}=\frac{n!}{m!(n-m)!}$ # 二项式定理 $(x+y)^n=\begin{…

# 2-SAT ## 定义 - 搞出 $N$个集合，每个集合2个元素 - 若干个$ $表示$a, b$矛盾（$a, b$属于不同集合） - 然后从每个集合选择一个元素，一共选$n$个两两不矛盾的元素 - 有多钟方案 ## 布尔可满足性 - 给定一条真值表达式，包括逻辑变量，逻辑与，或，非 - 是否存在一组对这些变量的赋…

# 双指针 - 对撞指针 - 龟兔指针 ## 对撞指针 - 一般用于顺序结构 - 从两端向中间移动，一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。 - 终止条件一般是两个指针相遇或错开（也可能在循环内部找到结果直接跳出环） - left == right（两个指针指向同一个位置） - left > ri…

# ~~滚回莫队~~ ## 引入: 普通莫队在查询转移时，会出现无法快速实现删除或增加操作的情况。 分为增加型，减少型 复杂度一样 ## 增加型 专门解决只能快速增加元素，不能高效删除元素 通过分块，排序和回滚操作，避免了删除操作，优化到 $O(n\sqrt n)$ ### 使用场景 - 仅支持快速增加（如添加元素时$…

# 根号分治与莫队 ## 根号分治是一种奇怪的分块 - 根号分治算法是一种用于优化数据结构和算法复杂度的技术。 - 对于题目中的某两个约束，它们总是相互制约的，并且这种制约是“乘积”关系——步长和项数，总有一个不能太大。 - 针对这两个情况分别设计算法，然后将两种算法结合起来，就能获得一个完整的解决问题的算法。 - 大…

## 扩展kmp(Z Algorithm) ### 引入 移除字符串的一部分，加上一部分，问多少步能变回原样(移除几个加上几个) ### 定义 是一种字符串算法。 核心：z数组 可以在O(n + m)的时间复杂度内，在给定的文本串T和一个模式串P中，找到所有匹配的位置。 ### Z函数 **核心是z(i)** 定义为：…

## manacher ### 相关定义：回文字符串 问题：求最长回文子串 ### __1.暴力__ 找出所有子串，遍历每个子串判断它们是否为回文串 复杂度：$ O(n^2) $ ### __2.manacher__ p[i]：第i个节点的回文半径 方法：加入没有的字符，如 # 等。 用p[i]表示第i个节点回文的半径…

在文章《题解 P1164 【小A点菜】》发表评论：

@W_Galaxy

在文章《题解 P1164 【小A点菜】》发表评论：

题解讨论区没关

算法步骤： - 第一个元素进队，队头队尾指针指向第一个元素 - 对于其他的N-1个未入队的元素，执行以下操作 ```cpp for(int i = 1 ; i > c[i] >> w[i] >> num[i];//c, w, num分别对应 体积 价值 个数 if(V / c[i] < num[i]) num[i] =…

# 插头DP ## 特点 是状压DP的一种，不是一行一行的压，而是一条一条向轮廓一样压。 用于解决有限宽度棋盘上的复杂操作问题。  例题 [P10975](https://www.luogu.com.cn/problem/P109…

# ~~动态动态规划~~ ## 四边形不等式的优化 ```cpp for(int i = 1 ; i dp[i][k] + dp[k + 1][j] + w[i][j]){//是否更优 dp[i][j] = dp[i][k] + dp[k + 1][j] + w[i][j]; s[i][j] = k;//更新最佳分割点…

# ~~科比~~可并堆 ## 概念 - 是一种抽象数据类型，支持优先队列的三个基本操作，还支持合并操作 - 主要用于快速合并堆的操作 - 结合了堆和并查集的特性，使得凉的堆合并时保持高效的性能 ## 用途 - 如果不需要合并，二叉堆就是最常用理想的优先队列 - 合并两个二叉堆要O(n)，直接朴素的使用二叉堆，合并的时间…

# 我勒个范浩强啊 ## FHQ-Treap定义 - 是无旋Treap - 用split 和 merge 维护 ## Treap的简介 - 随机化数据结构 - 二叉搜索树 + 二叉堆（小根大根皆可） - **用键值维护** 给每个键值一个随机附加的优先级，让键值满足二叉查找树的结构，让优先级满足二叉堆的结构。 ## T…

# 树上倍增 ## 豪用 ### 求第Y个祖先 N个节点的树，M次询问第X个节点的第Y个祖先 $$ n, m 0 && F[F[j][j - 1]][j - 1] > 0) F[j][i] = F[F[j][i - 1]][i - 1]; } } int f(int x, int n){ for(int i = 20;…

# ~~鼠上差分~~ ## 前言 树上差分可以理解为对树上的某一段路径进行差分操作，这里的路径可以类比一维数组的区间进行理解。例如在对树上的一些路径进行频繁操作，并且询问某条边或者某个点在经过操作后的值的时候，就可以运用树上差分思想了。 树上差分通常会结合 **树基础** 和 **最近公共祖先** 来进行考察。树上差分…

# 好用的树剖 ## part 1 前置芝士 - 树形结构 - 链式前向星 - 线段树 - DFS序 - LCA ### DFS序 小定义：对树执行DFS遍历时的顺序 应用：Tarjan 性质（维护信息的基础）： 1.一颗子树内，根的DFS序一定小于他的任意儿子的DFS序 2.一颗子树内，他的DFS序的范围就$[dfn…

在文章《分块》发表评论：

66666666666666666666666666666666666666666666666666666666666666666666666

在文章《分块》发表评论：

y6666666666666666666666

在文章《分块》发表评论：

6666666666666666666666666666666666

在讨论《如何学OI（玄关）》回复：

。。。红名绿√问这个

在讨论《CSP-J刷题策略》回复：

@[xzh_2013](/user/1235819) 今天早点洗洗睡吧，红名要相信自己

在讨论《CSP-J刷题策略》回复：

@[xzh_2013](/user/1235819)

在讨论《CSP-J刷题策略》回复：

666最后一天了问这个

在讨论《【玄2关】洛谷SCP-J的B题只得了五分，求助！》回复：

666为什么不直接发题目讨论区呢？？？

在讨论《CSP-S考SPFA吗？》回复：

@[rnf5114](/user/917683) qwq

在讨论《即将执刑，What can I do?》回复：

AKAK

在讨论《CSP-S考SPFA吗？》回复：

@[xyf007](/user/68273) 没有，比较优化~~实惠~~