RBTREE'S HOME

Goodbye World!

◆◆ 祝大家 2024 新年快乐！
新的一年，大家有事没事多留点评论吧（
这个可能稍微有点小错位不要太在意（划掉

数学杂记（更新于 20241122）

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

CSES 3152 Bubble Sort Rounds II

0 条评论 做题笔记 Data Structures
Problem StatementGiven an array $a$ of $n$ integers, find out the contents of the array after $k$ bubble sort rounds.$1 \leq n \leq 2 \times 10^5, 0 \leq k \leq 10^9, 1 \leq a_i \leq 10^9$TutorialN...

Bell Inequality

0 条评论 学习笔记 Quantum
The violation of the Bell inequality demonstrates that the classical theories based on local realism cannot completely explain the correlations predicted by quantum mechanics.CHSH GameConsider the ...

CSES 1160 Planets Queries II

0 条评论 做题笔记 图论
Problem StatementThere are $n$ nodes, and you are given an array $t$ of length $n$, where $t_i$ denotes that when you are at node $i$, you can teleport to node $t_i$.You have to answer $q$ queries....

CF2110F Faculty

0 条评论 做题笔记 No tags
Problem StatementYou are given an array $a$ of length $n$.Let $f\left(x, y\right) = \left(x \bmod y\right) + \left(y \bmod x\right)$.For each $i \in \left[1, n\right]$, you need to calculate:$$\max...

CSES 3140 Inversion Sorting 做题笔记

0 条评论 做题笔记 交互
题意有一个未知的排列 $a$，其长度为 $n$，你通过进行不超过 $4n$ 次交互将排列排序。给出 $l, r$，将 $a_l, a_{l + 1}, \ldots, a_r$ 翻转，即变成 $a_r, a_{r - 1}, \ldots, a_l$。操作完成后返回当前数组逆序对个数。题解考虑翻转 $\left[l, r\right]$ 对全局逆序对的影响。设：$v_1$ 表示 $\left...

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 双序列拓展 做题笔记

0 条评论 做题笔记 动态规划 动态规划优化
题目题解考虑一个计算量 $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 条评论 杂事 No tags
16:9 的显示器，用的是 4:3 分辨率，锁定了改不了，愤怒。提前 20 分钟进考场，赛前尝试改分辨率，尝试 10 min 以失败告终。然后趁没开始打了个线段树。t1 发现是要求一个最小链覆盖，转最长反链 7 min 做完了。t2 发现是个小模拟，50 min 差不多做完了。加速度公式也没看，直接看的样例解释里面的那个算法。t3 首先 5 分钟写了一个 $n^2$ 的 DP，然后尝试一些线...

洛谷 P4198 楼房重建 做题笔记

0 条评论 做题笔记 线段树 Data Structures
题意有 $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 条评论 做题笔记 No tags
请输入密码访问