一个Oier

引入 给定 n 个元素和若干组关系，每组关系表示两个元素属于同一集合。需要支持以下操作： 合并：将两个元素所在的集合合并为一个集合。 查询：判断两个元素是否在同一集合中。 这就是经典的并查集（Disjoint Set Union，DSU）问题。 例题：洛谷 P3367 【模板】并查集。 基本实现 核心思想 用一棵有根树表示一个集合，树的根节点作为该集合的代表元素。 用 fa[x] 记录节点 x 的父节点。初始时，每个元素独立成一个集合，即 fa[x] = x。 查找 查找元素 x 所在集合的代表元素（即树的根）： 1234int find(int x) { while (fa[x] != x) x = fa[x]; return x;} 合并 将 x 和 y 所在的集合合并，只需让一棵树的根指向另一棵树的根： 123void merge(int x, int y) { fa[find(x)] = find(y);} 查询 123bool query(int x, int y) { return find(x) ==...

RMQ 问题 RMQ（Range Maximum/Minimum Query），即区间最值查询。 给定一个长度为 n 的序列 {an}，每次询问给定 l, r，求 （或 max ）。 暴力做法每次询问 O(n)，q 次询问总复杂度 O(nq)，显然太慢了。 线段树可以做到 O(n) 建树、O(log n) 单次查询，总复杂度 O(n + qlog n)。 但如果没有修改操作，我们可以使用 ST 表 做到 O(nlog n) 预处理、O(1) 单次查询。 倍增思想 ST 表的核心是倍增。 倍增的基本思想是：预处理出长度为 2 的幂次的信息，查询时将任意区间拆成若干个预处理过的区间来合并。 一个直观的类比：任何正整数都可以用二进制表示，即拆成若干个 2 的幂次之和。倍增就是利用了这一点。 ST 表 预处理 例题：洛谷 P3865 【模板】ST 表。 定义 fi, j 表示从 ai 开始，长度为 2j 的区间的最大值，即 初始条件：fi, 0 = ai，即长度为 1 的区间最大值就是元素本身。 考虑递推。将区间 [i, i + 2j − 1] 从中间分成两半： 左半部分...

，其中 c 为常数。 ，其中 a 为常数且 a > 0。 ，其中 a 为常数且 0 < a < 1。 ，其中 a 为常数且 a > 1，f(n) 为有关 n 的多项式。 夹逼定理 如果数列 an ≤ bn ≤ cn，t 为一常数，若有 则 例题 Q1 求证： 对于任意给定的 ϵ > 0， 取 ，则 当 n > N 时，。 故 。 Q2 求 的极限。 Q3 求 的极限。 [!WARNING] 左边式子中有 n + 1 项，当 n → +∞ 时有 +∞ 项，所以不能直接拆开计算！ 涉及无穷时不能想当然！ 函数极限 函数极限的定义 如果存在 r > 0，使 D = {x ∣ 0 < |x − x0| < r, r > 0} 包含于 f(x) 的定义域，则说 y = f(x) 在 x0 附近有定义，称 D 是 x0 的邻域。 设函数在 y = f(x) 在 x0 附近有定义，y0 是实数。如果对任意给定的正数 ϵ，总能找到正数 δ，只要实数 x 满足...

朴素： fj ← max {fj, fj − v, fj − 2v, fj − 3v, ⋯, fj − sv}(假设 j ≥ sv) 12340 1 2 3 ... v - 1v v+1 v+2 v+3j j+1 j+2 ... m 12345q v+q 2v+q 3v+q ... pv+qdp[j] =max(dp[j])dp[j + v]=max(dp[j + v] - w, dp[j]) + wdp[j +2v]=max(dp[j +2v] - 2w, dp[j + v] - w, dp[j]) + 2w dp[j+kv] 在队列中的实际应为 dp[j+kv]-kw 现在已知是第 i 个物品，同余类为 j，体积为 k = j + xv 假设单调队列中最大值为 a = j + yv，最后的 b = j + zv 判断出队： k − a = (x − y)v 要求 x − y > s 那么 k − a > sv a = j + yv

很显然的二分。 二分最长长凳的最小长度 x，下面考虑如何 check。 在每一行一直放长度为 x 的长凳，直到放不下为止。记录当前可以做的人数 cnt。 如果 cnt ≥ k 则可行，反之不可行。 123456789101112131415161718192021222324#include <bits/stdc++.h>int T, n, m, k;bool check(int x) { long long cnt = 1ll * (1ll * m / (x + 1) * x + m % (x + 1)) * n; return cnt >= k;}int main() { std::cin.tie(0)->sync_with_stdio(0); for (std::cin >> T; T; --T) { std::cin >> n >> m >> k; int l = 0, r = m + 1; while (l + 1 != r) { int mid = l +...

分治。 由于表格是递归定义的，所以考虑递归地查询。 查询 (x, y) 的数字 递归查询。 假设当前的正方形左上角 (a, b)，右下角 (c, d)，记录当前左上角的值为 w。 容易得到正方形边长 l = c − a = d − b。 横渐近线为 ，竖渐近线为 。 令 ，即一个小正方形的大小。 左上角 w1 = w。 右下角 w2 = t + w。 左下角 w3 = 2t + w。 右上角 w4 = 3t + w。 递归下去即可。 查询 d 的位置 同上容易求出四个小正方形中的 min  和 max 。 找到 d 在哪个区间中，递归下去即可。 时间复杂度 时间复杂度 O(qn)。 代码 Record。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <bits/stdc++.h>using lint = long long;using pll = std::pair<lint,...

01 背包 题目描述 有 n 个物品，一个体积为 V 的背包。 第 i 个物品体积为 vi，价值为 wi。 每个物品只能选择一次，最大化放入背包物品的总价值。 输出最大总价值。 状态表示 集合 令 fi, j 表示 从前 i 个物品中选，总体积不超过 j 的方案集合。 属性 集合中的 最大价值。 状态转移 故 fi, j = max {fi − 1, j, fi − 1, j − vi + wi} DP 时间复杂度为 O(nV)。 初始条件 当选择 0 个物品时，无论总体积为多少，总价值都是 0，故 f0, j = 0 (j ∈ [0, V]) 最终结果 最终应当是 从前 n 个物品中选，总体积不超过 V 的方案中的最大价值，即 fn, V 代码实现 123456789101112131415#include <bits/stdc++.h>const int N = 1e3 + 10;int n, V, f[N];int main() { std::cin >> n >> V; for (int i = 1, v, w; i <=...

【预备周】 课前作业 B3701 [语言月赛202301] 避雷针 题解：B3701 [语言月赛202301] 避雷针 B3745 [语言月赛202304] 你的牌太多了 题解：B3745 [语言月赛202304] 你的牌太多了 B3767 [语言月赛202305] 你的牌太多了 2 题解 P1303 A*B Problem 题解 P1009 [NOIP1998 普及组] 阶乘之和 题解 P9064 [yLOI2023] 苦竹林 题解 P1803 凌乱的yyy / 线段覆盖 题解 P1192 台阶问题 题解 P1077 [NOIP2012 普及组] 摆花 题解 P7072 [CSP-J2020] 直播获奖 题解 B3631 单向链表 题解 P1449 后缀表达式 题解 P1143 进制转换 题解 B3625 迷宫寻路 题解 P1036 [NOIP2002 普及组] 选数 题解 P1102 A-B 数对 题解 P1612...

约定 下文代码中 lint 代表 long long。 下文代码中 pll代表 std::pair<lint, lint>。 质数 试除法判定质数 引理 1：∀ x ∈ {ℤ ∖ ℙ}，必然 ，使得 u ∣ x。 引理 1 证明： 假设 使得 u ∣ x。 因为 x 为合数，那么必然存在整数 使得 u ∣ x。 那么令 ，则 u ∣ x，且 ​，所以假设不成立。 故 ∀ x ∈ {ℤ ∖ ℙ}，必然 ，使得 u ∣ x。 那么可以遍历 ​ 间的所有整数，判断是否可以。 时间复杂度为 。 123456bool if_prime(lint x) { // 如果 x 为质数，返回 true；否则返回 false if (x < 2) return false; for (lint i = 2; i <= x / i; ++i) if (x % i == 0) return false; return true;} 分解质因数 时间复杂度为 。 123456789101112// 对 x 分解质因数，返回...

构造增广矩阵 找到绝对值最大的行 将绝对值最大的行置于目前第一行 将第一个数字消为 1 将 2 ∼ n 行的第一个数字消为 0 合并答案 代码实现 123456789101112131415161718192021222324252627282930313233343536int gauss() { int c, r; for (c = r = 0; c < n; ++c) { // 枚举列 int t = r; for (int i = r; i < n; ++i) // 找到绝对值最大的行 if (fabs(a[i][c]) > fabs(a[t][c])) t = i; if (fabs(a[t][c]) < eps) continue; // 最大为 0，跳过 for (int i = c; i <= n; ++i) std::swap(a[t][i], a[r][i]); // 将第一个数置为 0 for (int i = n; i >= c; --i)...