红黑树的小屋


世界再见

主站
祝大家 2024 新年快乐!
新的一年,大家有事没事多留点评论吧(
这个可能稍微有点小错位不要太在意(划掉

数学杂记(更新于 20241122)

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

Bostan-Mori 算法 学习笔记

1 条评论 学习笔记 数学 生成函数 多项式
线性递推我们说明,如果一个生成函数 $\frac{P\left(x\right)}{Q\left(x\right)}$,满足 $\deg\left(P\left(x\right)\right) < \deg\left(Q\left(x\right)\right)$,那么,该封闭形式所对应的原函数 $A\left(x\right)$ 是一个 $\deg\left(Q\left(x\rig...

洛谷 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 游记

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

洛谷 P4198 楼房重建 做题笔记

0 条评论 做题笔记 线段树 数据结构
题意有 $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]$ 的楼均没有交点(交在端点...

NOIP2024 赛前模拟赛记录

0 条评论 做题笔记 无标签
请输入密码访问

取模的最小公倍数

0 条评论 做题笔记 数学
请输入密码访问

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

0 条评论 学习笔记 无标签
请输入密码访问

最小割与最大割

0 条评论 学习笔记 无标签
请输入密码访问

CF2006B Iris and the Tree 做题笔记

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

List 1

0 条评论 杂事 无标签
ABC368D Minimum Steiner Tree考虑到我们可以从叶子开始删,我们这里对叶子的定义是度数为 $1$ 的点。维护集合 $L$,如果一个叶子需要保留,那么从 $L$ 中删除这个点,不再考虑在这个叶子上操作。否则我们可以删除这个叶子 $x$,看看删掉 $x$ 之后,$x$ 的父亲是否变成了叶子,如果是,则要加入进 $L$ 里。换句话说,如果一棵树的所有叶子都需要保留,那么此时...