Posts by hostmaster

故事发生在一个遥远的神秘世界。在那里，人们可以制造出不同等级的毒药。这种毒药是致命的，唯一的解药则是更强的毒药。若不幸中毒后，只要及时喝下更强的毒药就没事了，否则不管是谁都会在10分钟之内死亡。 一天，恶魔向国王发起挑战，看谁拥有最毒的毒药。这是一场死亡竞赛，比赛规则很简单：双方各带一瓶毒药，先把对方瓶中的毒药喝掉一半，然后再把毒药换回来…

题意 有 $n$ 种物质，每单位时间会随机生成一种物质，生成第 $i$ 种物质的概率为 $\frac{p_i}m$。求获得 $k$ 种物质的期望时间。 $1 \leq n \leq 1000, 1 \leq m \leq 10000, 1 \leq k \leq n, n - k \leq 10$ 题解 考虑直接使用 Min - kMax…

题意 有 $n$ 种卡片，每次购买有 $p_i$ 的概率买到第 $i$ 种，求使得每种都买到的期望购买次数。 $1 \leq n \leq 20$ 题解 考虑 Min - Max 容斥。 此时，$\displaystyle E\left(\min\left(S\right)\right) = \frac1{\sum\limits_{i \in S} p_i}$…

概述 Min - Max 容斥，又称最值反演，是一种对于特定集合，在已知最小值或最大值中的一者情况下，求另一者的算法。 例如： $$\max\left(a, b\right) = a + b - \min\left(a, b\right)$$ $$\max\left(a, b, c\right) = a + b + c - \min\left(a, b\right) - \min\left(a, c\right) - \min\left(b, c\right) + \min\left(a, b, c\right)$$…

$$\left(1 + 9^{-4^{7 \times 6}}\right)^{3^{2^{85}}}$$ 它恰好用到了 1 到 9 这 9 个数字。 猜猜看它能精确到 e 的小数点后多少位？ 10 位？100 位？1000 位？10000 位？ 它能精确到小数点后 18, 457, 734, 525, 360, 901, 453, 87…

题意 某大公司有这么一个规定：只要有一个员工过生日，当天所有员工全部放假一天。但在其余时候，所有员工都没有假期，必须正常上班。这个公司需要雇用多少员工，才能让公司一年内所有员工的总工作时间期望值最大（假设一年有 365 天，每个员工的生日都概率均等地分布在这 365 天里）？ 题解 你的感觉或许是，50 人或 100 人左右吧。但其实答案…

题意 要求在把单位圆的圆周分为 $n$ 段，求第 $m$ 短的段的期望长度。 （感觉应该会有原题） 题解 查看题解 可以考虑先求最短的段的期望长度。假设最短的段长为 $t$，那么剩下的 $n - 1$ 段的长度都大于等于 $t$，所以先将每条线段的长度都减去 $t$，这样问题就变成了在长度为 $2\pi - nt$ 的线段上随便取 $n - 1$…

游戏简介 游戏在一个 4 × 4 的棋盘上进行，棋盘里填有一个个的“数块”，每个数块上都写有某个形如 2^n$ 的正整数。每一步，你需要从上、下、左、右四个方向中选取一个方向，按下对应的方向键之后，所有的数块都会“落”到这个方向；若有两个同种的数块在此过程中发生碰撞，则它们的值会相加起来，并合成一个新的数块。然后，系统会在棋盘中随机选择一个空白位置，并在此生出一个新的数块，上面写有数字 2 或者数字 4 （两种情况之比为 9 : 1）。游戏开始时，棋盘上会自动生成两个随机的数块。 证明 由于棋盘上的每个数都是形如 $…

题意 一个人（叫做小明）和一只鳄鱼同被关在一个半径为 $10$ 米的岛上，鳄鱼位于岛中心处，小明则在距离中心 $1$ 米的地方。两者的最大运动速度都是每秒 $1$ 米。鳄鱼有没有什么必胜策略，使得不管小明怎么跑，它总能在有限的时间里抓住小明？ （别问我鳄鱼为什么不能跳到水里，因为这是题目设定） 题解 我猜如果你想出来的话，应该想的是： 鳄…

题意 给出一个 $n$ 个点 $m$ 条边的有向图，点的编号为 $1$ 到 $n$，第 $i$ 条边从 $u_i$ 出发连向 $v_i$，长度为 $w_i$。 你想要在这张图上玩若干轮游戏。在一轮游戏中，你会先选定一个点 $p \neq 1$，接着在 $1$ 号点和 $p$ 分别放置一枚金币。你可以沿着有向边任意移动金币，但需要花费边长对…