数学杂记（更新于 20241122）

@1 强迫症的投掷器 20240420$n$ 个东西，每次等概率随机一个东西摸一下。问期望几次能摸过所有 $n$ 个东西。显然第一次一定会摸到一个新东西。考虑期望多少次操作能拿到第二种新东西。显然有 $\frac{n - 1}n$ 的概率摸到新东西，于是期望次数就是 $\frac n{n - 1}$ 次。再摸到第三个东西的期望次数就是 $\frac n{n - 2}$ 次。于是总答案就是$$...

21795C3C87629DEBA67287015640FBED

请输入密码访问

NOIP2024 赛前模拟赛记录

请输入密码访问

洛谷 P9870 双序列拓展 做题笔记

题目题解考虑一个计算量 $nm$ 的 DP，设 $f_{i, j}$ 表示能否让 $x_i$ 与 $y_j$ 匹配。转移为$$f_{i, j} = \left(x_i < y_j\right) \land \left(f_{i - 1, j} \vee f_{i, j - 1} \vee f_{i - 1, j - 1}\right)$$可以看作在一个 $A_{i, j} = \lef...

CSP-S 2024 游记

16:9 的显示器，用的是 4:3 分辨率，锁定了改不了，愤怒。提前 20 分钟进考场，赛前尝试改分辨率，尝试 10 min 以失败告终。然后趁没开始打了个线段树。t1 发现是要求一个最小链覆盖，转最长反链 7 min 做完了。t2 发现是个小模拟，50 min 差不多做完了。加速度公式也没看，直接看的样例解释里面的那个算法。t3 首先 5 分钟写了一个 $n^2$ 的 DP，然后尝试一些线...

洛谷 P4198 楼房重建 做题笔记

题意有 $n$ 栋楼，第 $i$ 栋楼的高度为 $H_i$。在坐标轴上用一条 $\left(i, 0\right)$ 到 $\left(i, H_i\right)$ 的线段表示。称第 $i$ 栋楼可以被看到，当且仅当从 $\left(0, 0\right)$ 到 $\left(i, H_i\right)$ 的线段上，与 $\left[1, i - 1\right]$ 的楼均没有交点（交在端点...

取模的最小公倍数

请输入密码访问

摩尔投票与 Misra - Gries 算法学习笔记

请输入密码访问

最小割与最大割

请输入密码访问

CF2006B Iris and the Tree 做题笔记

题目题解这里给出一个不依赖子树标号连续的做法。我们可以认为，如果一条路径上还有一条边的边权没有固定，那么这条路径的权是容易计算的。我们可以认为，一开始所有点都是独立的，每次添加一条边。当一条路径的两个点连通时，这条路径上的边权就全部固定了。我们需要做的是合并两个连通块，启发式合并即可。代码/* C++20 is required! * By rbtree (https://rbtr.ee)...

HDU 7541 LIS 做题笔记

题意给定长度为 $n$ 的排列 $a$，删除 $a_i$ 的代价是 $b_i$。现在希望删除一些 $a_i$，使得删完后 $a$ 的最长上升子序列长度不超过 $k$，最小化被删除元素的代价和。对 $k \in \left[1, n\right]$ 分别求出答案。题解根据 Dilworth 定理，LIS 长度为 $k$，代表可以用 $k$ 个下降子序列覆盖全部。因此对于每个 $k$，我们要求出...

CF786C Till I Collapse 做题笔记

题意对于每个 $k \in \left[1, n\right]$，输出最小的 $m$，满足存在一种将给定的 $n$ 个数划分成 $m$ 段的方案，每段中不同数字的个数不超过 $k$ 个。题解做法 1我一开始想到的就是这个。首先观察到我们一段区间里至少会有 $k$ 个数，因此可以暴力枚举 $k$，然后快速跳。这样是一个调和数。我们需要对于一个点 $l$，快速找到一个 $r$，使得 $\left...

三次方程解法

二次方程如今我们都知道的形式是 $ax^2 + bx + c = 0$，我们有通解 $x = -b \pm \frac{\sqrt{b^2 - 4ac}}{2a}$。我们希望找一个有启发性的解法，帮助我们推导三次方程的解。首先我们先给我们的形式简化一下，显然可以变成 $x^2 + \frac bax + \frac ca = 0$，但这样不太美观，我们换成 $x^2 + px = q$ 的形...