Posts by hostmaster

Problem Statement Find all real roots of $\sqrt{5 - x} = 5 - x^2$. Tutorial 1 Square both sides. After simplification, we have $$ x^4 - 10x^2 + x + 20 = 0. \tag*{} $$ Of…

清晰版 约定 现在要计算两个 $n$ 位二进制数 $a$ 和 $b$ 的乘积，这是为了方便描述，一下算法可以直接应用到任意进制的情况。 我们的计算机每次仅可以对一位二进制位进行操作，我们的复杂度也是在这样的机器上进行计算的。 Karatsuba 型算法时期 Karatsuba 算法 前置知识 主定理（Master theorem）) Ka…

清晰版 前言 好久没更了，刚考完省选有点颓。 前置知识 积性函数（乘性函数） 数论分块 线性筛（欧拉筛） 狄利克雷卷积（Dirichlet convolution） 莫比乌斯反演（Möbius inversion） 概述 杜教筛用于在 $\Theta\left(n^\frac32\right)$ 的时间内求解某些函数的前缀和。 公式 杜教…

清晰版 题意 注意，所有的 $h_{i, j}$ 都不会重复 稍微提高点难度吧，询问次数限制改为 $5n$。 题解 首先有一个一定能找到相对高地的方法（此处取名“蛇形法”，至于为什么，往下看就知道了）： 随机一个点，寻问四周，向最高的点移动，直到四周都比它低。 <此处应有 $30$ 秒思考，你需要知道它为什么是对的，又需要知道它在什么情况…

题意 题解 首先可以以一个对于当前的 $H$ 合适的长度，随机合理的次数，得到一个较接近 $H$ 的解。然后考虑如何微调。 如果加入一个出现次数最多的数，那么熵就会减小。反之则会增大。 而这个增减幅度会随着字符串的长度越来越小，于是最终可以接近 $H$，而 $1000$ 的长度非常充足。 对于一些难处理的数，可以尝试打表。 代码 // :…

题意 维护长度为 $n$ 的数组 $a$： 区间 chkmax 撤销某次 1 操作 询问某点的值 $N = Q = 2 \times 10^5, 1 \leq A_i \leq 10^9$ 题解 线段树上每个节点维护一个 multiset，每次 chkmax 就往 multiset 里加数，每次撤销即是删除数。每次查询操作则是查找根到该点…

题意 由于题目比较搞笑，就不简述题意了，大家自己看看吧（ 加特林轮盘赌是一个养生游戏。 与俄罗斯轮盘赌等手枪的赌博不同的是，加特林轮盘赌的赌具是加特林。 加特林轮盘赌的规则很简单：在加特林的部分弹夹中填充子弹。游戏的参加者坐在一个圆桌上，轮流把加特林对着自己的头，扣动扳机一秒钟。中枪的自动退出，坚持到最后的就是胜利者。 我们使用的是 20…

题目 题意 给定长度为 $2N$ 的两个序列 $A$ 和 $B$。 构造一个长度为 $2N$ 的序列 $\mathrm{C}$。满足以下条件： 序列 $\mathrm{C}$ 的第 $i$ 个数 $C_i$，只能从 $A_i$ 和 $B_i$ 中选取。 设 $a$ 为序列 $\mathrm{A}$ 中元素被选取的次数，$b$ 为序列 $\mathrm{B}$…

题目 题意 有 $n$ 个文件，其中有 $k$ 个必须上传，其他所有文件不可以上传。 每次上传操作可以选择按照文件名字典序排序或按照创建时间排序，然后上传一段连续区间里的所有文件。 题解 考虑最小割。 假设现在以字典序排序或按照创建时间排序。一个需要上传的文件如果不和 该排序下的下一个文件 一起上传，那么就需要耗费额外的 $1$ 的代价。…

概述 计算几何主要解决 点、线、面 之间的位置和大小关系。 向量 向量是一个有大小和方向但不确定位置的量，但我们可以用 $\overrightarrow {AB}$ 表示一个从 $A$ 点到 $B$ 点的向量。另外 $\left\lvert AB \right\rvert$ 表示向量的模（又称模长，是向量的大小和长度）。 向量加法 对每个…