回転松ぼっくり!!

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

数学杂记(更新于 20241122)

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

21795C3C87629DEBA67287015640FBED

0 条评论 杂事 无标签
请输入密码访问

NOIP2024 赛前模拟赛记录

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

洛谷 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]$ 的楼均没有交点(交在端点...

取模的最小公倍数

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

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

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

最小割与最大割

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

CF2006B Iris and the Tree 做题笔记

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

HDU 7541 LIS 做题笔记

0 条评论 做题笔记 网络流
题意给定长度为 $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...

三次方程解法

2 条评论 学习笔记 数学
二次方程如今我们都知道的形式是 $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$ 的形...