Posts by hostmaster

题意 有 $n$ 个不大于 $m$ 的自然数 $a_i$, 你需要找到一个不大于 $k$ 的自然数 $s$，以最小化： $$\min\limits_{i \neq j} \left(a_i + s\right) \oplus \left(a_j + s\right)$$ 你只需要输出这个最小值即可。其中 $\oplus$ 表示按位异或。…

题目 题解 这个 graze 函数就是求一个曼哈顿距离。曼哈顿意义下的圆是一个旋转 45 度的正方型。把它转回来，就相当于是求矩形内部点数了。 这个做法有很多。可以 CDQ，也可以二维线段树，还可以 K-D Tree。

前言 建议在看本文章时动笔算一算。 概述 泰勒展开用于近似一个函数在某个点附近的值。 通过泰勒展开，你可以把某个简单的东西拉长。看上去是复杂化了，但在某些情况下，化简后你可以完成一些不可思议的操作。 一些看似非常难求的东西，用上泰勒展开就好求了。 举例 本质 泰勒展开的本质是通过用高次函数来模拟目标函数曲线。 公式 泰勒展开（Taylor…

题意 给定长度为 $n$ 的数组 $a$ 和 $b$，有 $q$ 次询问，每次询问给定整数 $l, r, x$，求 $$\sum\limits_{i = l}^r\frac{a_i}{b_i + x}$$ $1 \leq 3\times 10^5, 1 \leq q, a_i, b_i \leq 10^6$ 精度 $10^{-6}$ 时限…

题意 Ankica 和 Branko 在玩游戏。 有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个。玩家轮流移除一堆石子中的若干个，取到最后一个石子的玩家获胜。 但在该游戏中每个玩家从哪堆石子中取石子是由另一名玩家固定的。 具体来说，游戏的回合数从 $1$ 开始每次递增，增量为 $1$，而游戏将会以如下方式进行： 在奇数回合，Bran…

题意 有 $n + 1$ 辆巴士，编号为 $0$ 到 $n$，它们的速度都是固定的。前 $n$ 辆巴士有固定的出发时间。 在公路上，这些巴士不能超车（相对位置不能改变），所以当快的车追上慢的车之后，需要跟慢车保持同一速度行驶。 有 $m$ 个点，在这些点上可以超车（同一时间到这个点的车按照行驶速度排序，快车在前，慢车在后）。 现在有 $q$…

题意 给定一张无向联通图，小 B 从某个点开始，每秒移动到一个相邻节点（不能不动）。小 A 每秒猜测小 B 所在的位置。若小 B 刚好在小 A 所猜的位置，小 A 就赢了。 问小 A 能否在有限步数内赢。如果可以，给出步数最小的构造方案。 $1 \leq n \leq 1000$ 题解 首先考虑有环的情况。小 B 可以选择从环上一点开始，…

题意 给定一个长度为 $n$ 的数组 $a$。有 $q$ 个询问，每次询问给出 $a, b, m, r$，求在范围 $\left[a, b\right]$ 中，$a_i \bmod m = r$ 的个数。强制在线。 $1 \leq n, q \leq 3 \times 10^5, 1 \leq a_i, m \leq n, 0 \leq r < m$…

题意 给出一个长度为 $\dfrac{n\left(n + 1\right)}2$ 的直尺，要在 $0$ 和 $\dfrac{n\left(n + 1\right)}2$ 之间选择 $n - 1$ 个刻度，使得 $1$ 到 $\dfrac{n\left(n + 1\right)}2$ 中任意一个长度都可以由某两个刻度（包括 $0$ 和 $\dfrac{n\left(n + 1\right)}2$…

题意 加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的 $1$ 号城市上。这个可乐机器人有三种行为：停在原地、去下一个相邻的城市。自爆。它每一秒都会随机触发一种行为。现在给出加里敦星球城市图，在第 $0$ 秒时可乐机器人在 $1$ 号城市，问经过了 $t$ 秒，可乐机器人的行为方案数是多少…