[例题](https://www.luogu.com.cn/problem/P15352)。 首先考虑暴力怎么写，对于每一次 $2$ 操作，直接暴力加边，时间复杂度为 $O(nq\alpha{(n)})$。 瓶颈在于 $2$ 操作，考虑如何优化。 对于一次 $2$ 操作，可以看成若干次 $2$ 操作的结合体，具体可以看下面两张图：...

 帅

# 矩阵基础知识 ## 一、矩阵是什么 矩阵可以简单理解成一个“按行和列排列的数字表”。 例如： $$ A= \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix} $$ 这个矩阵有 $2$ 行、$3$ 列，所以它是一个 $2\times 3$ 的矩阵。 矩阵中的每一个数叫作矩阵的元素。通常用 $A_{ij}$ 表示矩阵...

Slope Trick 是一种 DP 优化方法，它通过存储斜率变化以存储凸包优化转移。下面我们通过三个题理解这个神奇的 trick。 ## [洛谷P4597 序列 sequence](https://www.luogu.com.cn/problem/P4597) 这题是 CF13C 的数据加强版。 ### 题面大意 给定一个序列，每次操作可以把某个数 +1...

# `__int128` 基础与使用 ## 一、为什么需要 `__int128` 在 C++ 竞赛代码中，我们最常用的大整数类型通常是 `long long`。它的范围大约是： $$ -9\times 10^{18}\sim 9\times 10^{18} $$ 更准确地说，`long long` 最大值是： $$ 9223372036854775807...

# 和式的操作：从分配律到多重求和，一篇讲清常见变形技巧 很多同学一见到和式，就习惯“直接算”。 但实际上，和式真正厉害的地方，从来都不是硬算，而是**变形**。 你可以把它理解成： **求和不是结束计算，而是开始操作。** 这篇文章就系统整理一下和式处理中最常见、最实用的一些方法： - 和式的三大基本法则 - 等差和的经典推导 -...

```cpp #include using namespace std; using ll=long long; int n, m, ans, tim; vector te[2005], bu, bv; int tin[2005], out[2005], dep[2005]; void df1(int u, int p) { tin[u] = ++tim;...

### P1063 能量项链 题解 #### 题意简述 给定一个链，链上有$N$个珠子，不同珠子合并会产生不同的能量，问：按照什么样的顺序合并这$N$个珠子能产生最大的能量？ #### 题目分析 1. 因为题目中所给的是环，我们需要将其转化为链，可以将环断开，拼成一个长度为$2N$的长链，每个新链上第$i + N$颗珠子都对应着原链上第$i$颗珠子。 2....

# 绿【树形动态规划、DFS序】选课 # 题意概括 给定包含 $N$ 个节点与 $M$ 个选取配额的依赖网络。节点 $i$ 具有权值 $s_i$ 与唯一的直接前置依赖节点 $k_i$（若 $k_i=0$ 则无依赖）。依赖关系整体构成森林拓扑。现要求在严格满足拓扑依赖律（即选取节点 $i$ 的必要条件为节点 $k_i$ 已被选取）的前提下，选取恰好 $M$...

# T1 题目 ## 题目描述 若 $$ a_1 + a_2 + a_3 + \cdots + a_k = n \quad (1 \le k \le n) $$ 求 $$ \prod_{i=1}^{k} a_i $$ 的最大值。 --- ## 输入格式 第一行输入整数 $$ T \quad (1 \le T \le 10^4) $$ 表示测试组数。 接下来...

 ## T1 chip change ## 题目描述 奶牛 Bessie 手里有 **A** 个 A 类筹码，以及 **B** 个 B 类筹码（$0\le A,B\le 10^9$）。 她可以进行如下操作任意多次： - 如果当前 **至少有 $c_B$** 个 B 类筹码，就可以用...

## 语法A训练大纲 | 大标题 | 小标题 | 核心考察知识点训练 | | -------------------------------------------- | --------------------- | ------------------------------------------------------------ | | 顺序结构...

## 预备知识与符号约定 在开始证明之前，我们首先需要建立一套清晰的数学语言与符号体系。 * **图的表示**：一个带权有向图被表示为 $G = (V, E)$，其中 $V$ 是顶点的集合， $E$ 是边的集合。图中顶点的数量记为 $|V|$，边的数量为 $|E|$。每条边 $(u, v) \in E$ 都有一个权重（cost），由函数 $w: E \to...

# 划分DP 划分型动态规划（划分DP）是一种处理特定类型问题的动态规划方法，常用于解决需要将数据结构（如数组、字符串等）划分成若干部分以优化某些目标函数的问题。这类动态规划问题的关键在于找到合适的状态表示和状态转移方程。下面是划分的$ DP $一些常见做法： 主要分为两种类型： ## $\color{red}\text{1、确定段数的划分}$ ###...

# 概率与期望 ## 概率论 ### 事件的运算及概率 - **包含**：$A \subset B$，发生 $B$ 时必然发生 $A$，发生 $A$ 时不一定发生 $B$。 - **并（和）事件**：$A \cup B = A + B$，$A$ 发生或 $B$ 发生或两者都发生。 - **交（积）事件**：$A \cap B = AB$，$A$ 和 $B$...