一个Oier

基础知识 简介 线段树是一颗不那么完全的二叉树。 设线段树有 h 层，则第 1 ∼ h − 1 层是满的，而第 h 层并不一定是满的，而是由第 h − 1 层的非叶子节点伸出两个儿子。 维护区间序列信息； 所有非叶子节点都有两个儿子 树上每个节点对应序列的一个区间 线段树是算法竞赛中常见的用来维护 区间信息 的数据结构。 编号方式 线段树是将序列分治的过程，并且将分治的过程记录下来。 根节点编号为 1，对应整个区间 [1, n]。 对于当前节点编号 u，对应区间 [l, r]。 令 ，则： 左儿子编号 2 × u，对应区间 [l, mid]； 右儿子编号 2 × u + 1，对应区间 [mid + 1, r]； 父亲编号为 。 区间长度为 1 的线段树节点为叶子节点，没有左右儿子。 空间复杂度 线段树是一个类似完全二叉树的结构，开空间时要为下面一层留足空间 考虑从上至下的每层节点数量之和，得到 1 + 2 + 4 + ⋯ + 2⌈log n⌉ ≤ 2⌈log n⌉ + 1 一般大小开到 4 × n...

省流：本文将介绍用指针实现线段树，并介绍如何在题目中运用线段树解决问题。 线段树 の 实现 线段树一般用于维护区间信息。 题目示例 要求维护一个序列 {an}，实现两种操作： 给定 l, r 和 x，让 a 中 [l, r] 区间内的每一个数加上 x（区间加）。 给定 l, r，求 （区间求和）。 朴素实现 / Bruteforce 前缀和：发现有区间求和，容易想到用前缀和 O(1) 维护。但是对于区间加，最坏情况下要修改整个前缀和序列，时间复杂度为 O(n)。 差分：发现有区间加，容易想到用差分 O(1) 维护。但是对于区间求和，每次需要计算一次差分序列的前缀和，时间复杂度为 O(n)。 线段树 / Segment Tree 有没有一种可以均衡两个操作复杂度，每次操作是 O(log n) 的数据结构呢？ 线段树是将序列分治的过程，并且将分治的过程记录下来。 线段树维护的信息需要满足可合并性，即可以从儿子的信息得到父亲的信息。 存储方式 线段树将序列中若干个区间在树上用结点来表示，其中 [1, n]（在下文的讨论中 n...

题目 给定 n, m, p，求 杨辉三角递推 PS：该做法适用于 p 恒定时的做法。 Solution 根据组合恒等式 可以开一个二维数组 C，其中 C[i][j] 表示 的值。 接下来依次递推即可。 Code 123456// MAX 为最大值for (int i = 0; i <= MAX; ++i) for (int j = 0; j <= i; ++j) { if (!j) C[i][j] = 1; else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p; } Lucas 定理 PS：该做法适用于 p 较小时的情况。 Solution Code 根据公式计算

基础知识 矩阵定义 晚点写。 矩阵加法/矩阵减法 晚点写 矩阵乘法 前置条件 矩阵乘法有意义，当且仅当第一个矩阵的列数和第二个矩阵的行数相同时。 则此时两个矩阵相乘的行数为第一个矩阵的行数，列数为第二个矩阵的列数。 可以记为将两个矩阵相同的一个边长去掉，然后第一个矩阵剩余的边长作为最终结果的行数，第二个矩阵剩余的边长作为最终结果的列数。 故设 P 为 a × b 的矩阵，Q 为 b × c 的矩阵。 设 R 为矩阵 P 与 Q 的乘积，则大小为 a × c。 运算法则 矩阵 R 中的第 i 行第 j 列元素可以表示为 一种可能的记忆方法 对于 A 矩阵的第 i 行，将其顺时针旋转 ，并将其与 B 矩阵的第 j 列每个对应的数相乘，其和即为 Ci, j。 举个例子： A 为 4 × 6 的矩阵，B 为 6 × 2 的矩阵，则 C 为 4 × 2 的矩阵。 假设要求 C3, 2，则取出 A 矩阵第 3 行，将其顺时针旋转 ，可得 A′。同时去除 B 矩阵第二列，将 A′ 与 B 第二列位于同一行的数乘起来，最后将所有乘积求和即得...

定义 若 c ∣ a 且 c ∣ b，那么称 c 为 a 和 b 的公约数。 在 a 与 b 的所有公约数中，最大的那一个称为最大公约数，记为 gcd (a, b)，在不混淆的情况下亦可记为 (a, b)。 性质 gcd (a, gcd (b, c)) = gcd (gcd (a, b), c)​。 假设维护一个集合的 gcd  = x，设新增一个数后新的 gcd  = x′，则有 x′ ≤ x，且变化次数最多 log n 次。 设 a = ∏piαi, b = ∏piβi (pi ∈ ℙ) 那么 gcd (a, b) = ∏pimin {αi, βi} 其中认为不存在的质因数 pi 的指数为 0。 辗转相除法 定理 gcd (a, b) = gcd (b, a mod  b) 证明： 不妨令 a > b​。 设 a = b ⋅ k + r，r < b（r = a mod  b​）。 设 g = gcd (a, b)，且 a = n ⋅ g，b = m ⋅ g。 那么...

费马小定理 定理 如果 那么有 ap − 1 ≡ 1 (mod  p) 证明 引理 1 若 a ⋅ c ≡ b ⋅ c (mod  m) 且 c ⊥ m，则 a ≡ b (mod  m)。 证明 1 a ⋅ c ≡ b ⋅ c (mod  m) 可得 (a − b) × c ≡ 0 (mod  m)，又因为 c ⊥ m，那么 (a − b) × c 当且仅当 a − b 是 m 的倍数即 a − b ≡ 0 (mod  m)，即可得 a ≡ b (mod  m)。 引理 2 若 a ⊥ m，则 {a, 2a, 3a, …, (m − 1)a} 是一个模 m 的完全剩余系。 证明 2 考虑使用反证法。 假设 使得 i × a ≡ j × a (mod  m)，又因为 a ⊥ m，根据 引理 1，可得 i ≡ j (mod  m)，而 i, j ∈ [1, m − 1]，所以 i ≡ j (mod  m) 当且仅当 i = j，与假设矛盾，故得证。 由上述引理，可知 {1, 2, 3, …, p − 1} 与...

Solution F1 观察 n 的范围，由于 1 ≤ n ≤ 106，足以开下一个完整的数组，所以可以直接进行模拟。 对于每一个输入的 a，枚举 max {a − 2, 1} ∼ min {a + 2, n}，这样就不会越界了。可以开一个计数数组 ， 表示 i 位置被劈中的次数。 最后遍历整个数组，统计即可。 时间复杂度 O(n + m)，空间复杂度 O(n)，可以通过本题。 #### F2 考虑一种情况，当 n 的范围非常大，以至于无法开一个数组记录时，应该如何解决呢？ 首先，我们要使得时空复杂度与 n 无关。对于每一个 a，影响的位置只有 5 个，开一个数组记录的话很大一部分空间都被浪费了。 所以，我们只需要存储被劈过的位置，并且为了方便去重，并且使得时间复杂度较低，可以使用哈希表存储被劈过的位置。 ### Code #### F1 123456789101112131415161718#include <iostream>const int MAX = 1e6 + 10;int n, m, ans, t[MAX];// t 为计数数组int main()...

Solution 选择与扶苏本轮打出的牌花色相同且点数大于扶苏打出的牌中点数最小的一张打出。 上面这句话是题目的核心。 首先，必然要开题目描述中的 4 个数组 f1, p1, f2, p2，然后由于已经打出的牌无法再次打出，所以需要开一个标记数组 b，其中 bi 表示小 F 的第 i 张牌是否被打出。 接下来，对于每一个 p，我们需要找到符合要求的牌。遍历 1 ∼ n，不符合如下条件就需要跳过： - bi = true ，即第 i 张牌已经被选择； - f2i ≠ f1p，即两张牌花色不同； - p2i ≤ p1p，即小 F 的这张牌的花色不大于扶苏打出的牌的花色。 接下来，题目要求找到牌中点数最小的一张打出。所以我们需要一个记录答案编号的变量 ，初始的时候对应牌的编号可以设置为 inf ，然后遍历时如果牌都满足上面的条件且点数小于 这张牌的点数，那么就更新 。 最后如果可以打出牌的话，那么要将 bi 设为 true 。 最后结果就是统计 bi 中结果为 false ，即未被打出的牌的数量。 ### Code...

算法分析 首先，由于要求最大化下面的式子： 容易想到使用 DP。 其次，由于双端队列需要控制两端的位置，所以显然要使用区间 DP。 状态设计 首先记录一个区间的左、右端点，所以第一步令 fl, r 表示 a 中 [l, r] 这一区间最大的贡献。 但是，[l, r] 可能由 [l + 1, r] 或 [l, r − 1] 得来，无法固定，所以需要记录 [l, r] 是由哪个区间得来的。 能不能记录这个数的下标呢？这是不行的，因为这样空间复杂度就会变为 O(n3)，铁定爆炸。 根据之前的描述，[l, r] 只有两种得到的可能性，所以可以将第三维表示为 0/1： fl, r, 0 表示当前区间为 [l, r]，且是先弹出 al； fl, r, 1 表示当前区间为 [l, r]，且是先弹出 ar。 这样，我们就可以进行状态转移了。 状态转移 声明：下面的转移方程中暂时先忽略取模。 考虑 fl, r, 0 如何转移。 由于 fl, r, 0 由 [l + 1, r] 得来，所以此时先弹出的是 al，即 bi = al。 由于...

Description 给定一张 n 个点的带权无向完全图，求出从 0 到 n − 1 经过每个点恰好一次的最短路径。 ## Solution ### Brute Force 考虑最朴素的做法。 由于每个点只能经过一次，所以可以枚举 n 个点的全排列。对于每个全排列，遍历每个点，计算路径长度。最后找到最短的路径长度即可。 时间复杂度：O(n ⋅ n!)，20! 铁定是会 TLE 的。 ### DP n ≤ 20 的数据范围，除了搜索，指数级别的算法也是可以的。可以考虑状态压缩 DP。 无后效性：每个点只能经过一次，后面的状态不会影响前面的状态； 最优子结构：每个状态的转移都是类似的，都是从前一个状态加上边权得到现有状态。 考虑已经经过了一些点到达了节点 u，现在再走一个点到达 v。由于每个点只能经过一次，我们不可避免地要关心每个点是否经过。但是与暴力做法相比，经过了这些点之后，就不再关心这些点经过的顺序。 状态表示 首先，我们要在任何时刻都可以表示已经经过了哪些点。可以使用一个 n 位二进制数 S，第 i (0 ≤ i < n) 位为 1 则表示这个点已经经过，为...