Posts by hostmaster

This post is password protected. Enter the password to read it.

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

地址：https://git.rbtr.ee/ 先声明一下，由于我寄术高超，请不要在此 git 服务器上上传重要不可找回文件。服务器没有备份！服务器没有备份！服务器没有备份！ 哪个男孩不想把整个世界都装进自己的口袋里呢？今天，我朝这个目标又迈进了一小步。由红黑树维护的基于 Gitea 的 git 服务器诞生啦 (*^▽^*)！ FAQ Q…

前言 之前写过一篇大楼丢鸡蛋问题，今天看到以前写的东西纯属胡扯，所以重写一下，因为今天有幸见到了大楼丢鸡蛋的终极强化版本：$10^3 \times 10^{18}$。 题目 URAL - 1597 有一个 $N$ 层的大楼，你有 $K$ 个鸡蛋。每个鸡蛋的硬度都是相同的。碎鸡蛋不能用来测试。你要求出 至少扔多少次才能保证测出鸡蛋的硬度。…

清晰版 定义 简单来讲（不严谨）若一个变换 $\mathscr A$ 是线性变换，则对于线性空间中的任意元素 $\alpha$ 和 $\beta$ 它必须满足： $\mathscr A\left(\alpha + \beta\right) = \mathscr A\left(\alpha\right) + \mathscr A\left(\beta\right)$…

This post is password protected. Enter the password to read it.

题意 给定一棵树，每次随机选一个点永久删除它及它的所有子树。输出一个实数表示期望被删空的次数。 $n = 10^5$，$0.5$ 秒 题解 结论：$ans = \sum\limits_{i = 1}^n1/dep_i$ 如果我们要删除点 $i$，那么要么直接删除 $i$，要么删除 $i$ 的一个祖先。只有直接删除 $i$ 时，我们才将这笔…

题意 给定长度为 $n$ 的数组 $c$，重排它，最大化最大子段和。 给出一些限制 $\left(a_i, b_i\right)$，表示原始数组中的第 $a_i$ 个元素必须在第 $b_i$ 个元素之前。 $n = 50$ 题解 我们可以把数组分为三个部分：最大子段和所在区间的前面、最大子段和所在区间、最大子段和所在区间的后面。 注意到每…

概述 多项式插值算法用于寻找一个恰好通过给定数据点的多项式。 问题形式 给定 $k + 1$ 个互异数据点 $\left(x_i, y_i\right)$，找到一个 $n$ 次多项式 $f\left(x\right)$，使得对于任意的 $0 \leq i \leq k$，有 $f\left(x_i\right) = y_i$。在某些情况下…

清晰版 题意 给定一个长度为 $n$ 的数组 $s$。随机选择两个可以相等的位置 $i_a$ 与 $i_b$。设 $a = s_{i_a}, b = s_{i_b}$。 现在有 Alice 和 Bob 在猜 $a$ 与 $b$ 的大小关系。 从 Alice 开始轮流，每次轮到的人可以说“我不知道相对大小”然后轮给另一个人，或者说“我知道了…