CodeForces VP 记录

感觉 tf 的时候还是打几场 VP 好……

加*号的是当场过掉的，这样以后复习可以用。

Codeforces Round #472 (rated, Div. 1, based on VK Cup 2018 Round 2)

*A. Mystical Mosaic

~~题意好难翻译啊，那就不翻译了吧。~~

反正直接模拟就可以了。

*B. Three-level Laser

题目大意是给你一个长度为 $n (n \leq 10^{5})$ 的严格递增的正整数序列 ${E}$ ，让你求 $i < j < k$ 使得 $E_{k} - E_{i} \leq U$ 且 $η = \frac{E_{k} - E_{j}}{E_{k} - E_{i}}$ 最大。

考虑到严格递增应该是单调性问题。

显然如果 $i$ 和 $k$ 固定，那么 $η$ 与 $E_{j}$ 负相关，于是 $i = j - 1$ 。

然后考虑枚举 $i$ 算 $k$ ，直接把上面的 $E_{k}$ 去掉即可： $η = \frac{E_{k} - E_{j}}{E_{k} - E_{i}} = \frac{E_{k} - E_{i} + E_{i} - E_{j}}{E_{k} - E_{i}} = 1 + \frac{E_{i} - E_{j}}{E_{k} - E_{i}}$

二分一下就好了。

代码：58555515

*C. Riverside Curio

题意大概就是有一个人每天去看一条河的水位，每次在水位上画一条线，并记录下严格高于当前水位的线有几条，记为 $m_{i}$ 。令第 $i$ 天严格低于当前水位的线有 $d_{i}$ 条，求 $\sum d_{i}$ 的最小值， $n \leq 10^{5}$ 。

显然最少有 $max {m_{i}}$ 条线，然后我们找到这个位置，然后往两边跑。往后跑就直接模拟即可，因为之后是不会画新的线了。往前跑相当于是删线，显然是能删就删，维护一下前缀 $max$ 即可。

代码：58556096

D. Contact ATC

题意是说有 $n (n \leq 10^{5})$ 架飞机在一条数轴上飞，坐标为 $x_{i}$ ，速度为 $v_{i}$ ，有 $x_{i} v_{i} < 0$ （往原点飞），现在可能有一速度为 $v$ 的风，只能预测出 $v \in [- w, w]$ ，当然保证 $| v_{i} | < w$ 。求有多少对飞机可能同时到达原点。

感觉自己好菜啊，推式子发现是跟斜率相关的一个东西，然后惊喜地发现这好像是道计算几何，然后码了一年……

我们考虑计算出飞机到达原点的时间 $t_{i} \in [l_{i}, r_{i}]$ ，考虑到风速与时间是呈一个一次函数的关系，画图便可知道如果是相向飞行的飞机 $i, j$ ，只要 $[l_{i}, r_{i}] \cap [l_{j}, r_{j}] \neq \emptyset$ 即可，如果是同向的飞机 $i, j$ ，只要 $[l_{i}, r_{i}] \subseteq [l_{j}, r_{j}]$ 或 $[l_{i}, r_{i}] \supseteq [l_{j}, r_{j}]$ 即可。

然后就变成了一个二维数点问题。

代码：58560521

E. Wardrobe

题解写在了另一篇文章里。

F. Minimal Subset Difference

太菜了，不会。

Codeforces Round #539 (Div. 1)

*A. Sasha and a Bit of Relax

题意大概就是给你一段长度为 $n (n \leq 3 \times 10^{5})$ 序列 ${a} (0 \leq a_{i} < 2^{20})$ ，求有多少个区间 $[l, r]$ 使得 $r - l + 1$ 是偶数且 $⨁_{i = l}^{m} a_{i} = ⨁_{i = m + 1}^{r} a_{i}$ ，其中 $m = \frac{l + r - 1}{2}$ ， $⨁$ 是指 xor。

显然只要 $⨁_{i = l}^{r} a_{i} = 0$ 即可，然后开个桶算。

代码：58788064

*B. Sasha and One More Name

题意是给你一个回文串 $s (1 \leq | s | \leq 5000)$ ，求最小割多少刀然后重组变成一个不同的回文串，无解输出 Impossible。

显然答案只有 $1$ 、 $2$ 、Impossible 三种，Impossible 直接判， $1$ 直接暴力枚举，剩下来的都是 $2$ 。

代码：58788424

C. Sasha and One More Name

数据结构题，直接抄了这篇博客的翻译：

维护以下三种操作

1 t s：在时刻 $t$ 插入命令 $s$ 。保证任意操作后，任意时刻至多只有一个命令。
2 t：删除时刻 $t$ 的命令。
3 l r v：求最小的 $t \in [l, r]$ ，使得 $f (t) = 0$ 。

其中

f (t) = v + \int_{l}^{t} g (x) d x

其中设在 $[l, r]$ 时间内的命令依次为 $(t_{1}, s_{1}), \dots, (t_{m}, s_{m})$ ，则：

g (t) = {\begin{cases} 0 & l \leq t < t_{1} \\ s_{1} & t_{1} \leq t < t_{2} \\ \dots \\ s_{k} & t_{k} \leq t < t_{k + 1} \\ \dots \\ s_{m} & t \geq t_{m} \end{cases} .

若不存在，则返回 $- 1$ 。

题解留坑吧……

Codeforces Round #578 (Div. 2)

打了场 Div. 2 感觉自己心情舒畅，~~然鹅还是自闭了……~~

话说我的 hash 好菜啊，为什么一定要打双哈希啊……

自闭了：

*A. Hotelier

直接模拟就可以了。

代码：58884080

*B. Block Adventure

还是直接模拟就可以了。

代码：58884001

*C. Round Corridor

大概就是有类似这样的一个圆形屋子，内层有 $n$ 格，外层有 $m$ 格，每层都有一面墙在 $12$ 时的位置，每格大小均匀。内外层没有墙，但每层格子与格子之间有墙。多次询问 $(s_{x}, s_{y})$ 和 $(e_{x}, e_{y})$ 询问着两个格子能否相互到达。

$n, m \leq 10^{18}, q \leq 10^{4}$ 。

显然可以把这个环形分成一段一段，每段都相连且独立（与其他格子不连通）。

假设一段有 $x$ 个内层格子与 $y$ 个外层格子，那显然有 $\frac{n}{x} = \frac{m}{y}$ ，即 $n y = m x$ ，我们需要找到最小的 $x, y$ ，也就是 $n y = m x = lcm (n, m) = \frac{n m}{gcd (n, m)}$ ，也就是 $x = \frac{n}{gcd (n, m)}, y = \frac{m}{gcd (n, m)}$ ，然后每次 $O (1)$ 判断两个点是否在同一联通块中即可。

代码：58883764

*D. White Lines

题意是有一块 $n \times n$ 的画布，有一些像素点是 W，有一些是 B，你可以将一个 $k \times k$ 的子矩阵中所有的 B 全部变成 W，问做多能有多少行列是全白色的， $n \leq 2000$ 。

我们考虑行和列分开来看，我们令 $f_{i, j}$ 表示左上角在第 $i$ 行第 $j$ 列，会把多少原来不是全白的行变成全白的行，同理可以定义 $g_{i, j}$ 表示会把多少原来不是全白的列变成全白的列。当然，为了复制粘贴方便，代码中把 $g_{i, j}$ 定义为了左上角在第 $j$ 行第 $i$ 列。

由于转移是对称（行和列的方程一样）的，所以我们就仅考虑行。我们考虑要把一行变成全白，必须把该行上最左边的黑色格子和最右边的黑色格子全部覆盖到，所以对于每行我们可以 $O (1)$ 计算。

我们考虑先 $O (n k)$ 暴力算出 $f_{1, j}$ ，然后每次计算 $f_{i, j}$ 考虑增加第 $i + k - 1$ 行的贡献并删除第 $i - 1$ 行的贡献即可。

这样复杂度就是 $O (n^{2})$ 的了。

代码：58884654

E.Compress Words

题目大意是有 $n$ 个字符串 $s_{i}$ ，从左往右依次合并每一个字符串，就是找到之前合并完的串的最长后缀使其是要合并的那个串的前缀，输出最终合并完的串， $n \leq 10^{5}, \sum | s_{i} | \leq 10^{6}$ 。

直接哈希就可以了，复杂度 $O (n)$ ……

大概需要双哈希，我的单哈希 wa on 66。

代码：58886006

Codeforces Round #589 (Div. 2)

又是一场愉快的 Div. 2。

可惜窝还是爆蛋了……

*A. Distinct Digits

直接模拟即可……

代码：61680483

*B. Filling the Grid

直接模拟即可……

代码：61680658

*C. Primes and Multiplication

题目大意有点复杂，~~然后我就看错了一年的题……~~

定义 $prime (x)$ 表示 $x$ 的质因子集合， $g (x, p)$ 表示最大的 $p^{k} ∣ x (k \in N)$ ， $f (x, y) = \prod_{k \in prime (x)} g (y, k)$ ，求 $\prod_{i = 1}^{n} f (x, i)$ 。（ $x \leq 10^{9}, n \leq 10^{18}$ ）

考虑到全是乘法，显然满足交换律。

所以我们对每个质因子分开来求，最后乘起来即可。

我们考虑质因子 $k$ ，显然 $1 \sim k - 1$ 的区间贡献是 $1$ ， $k \sim k^{2} - 1$ 的贡献是 $k$ ， $k^{2} \sim k^{3} - 1$ 的贡献是 $k^{2}$ ……

然后不难发现只有 $\log$ 个这样的区间，所以总复杂度 $O (\sqrt{x} + \log x \log n)$ 。

代码：61681335

*D. Complete Tripartite

有 $n (3 \leq n \leq 10^{5})$ 个点 $m (0 \leq m \leq min (3 \cdot 10^{5}, \frac{n (n - 1)}{2}))$ 条边的无向无自环无重边图，需要对每条边染色（ $1, 2, 3$ ），使得每种颜色自己的点之间没有边，其余的必须两两有边，求一种方案或无解。

直接模拟即可……

代码：61681851

*E. Another Filling the Grid

有一个 $n \times n$ 的矩阵，需要将每个格子用 $1 \sim k$ 的数字填充，要求每行每列都有至少一个 $1$ ，求方案数。 $n \leq 250, k \leq 10^{9}$ 。

$O (n^{3})$ 的 dp 很好想，直接令 $f_{i, j}$ 表示到第 $i$ 行已经有 $j$ 列有 $1$ 。

考虑转移，枚举一个 $t$ 表示这一列之前有多少列有 $1$ ，那么这些格子可以乱填，为 $k^{t}$ 。其中 $j - t$ 个格子只能填 $1$ ，其余格子不能填 $1$ 。这样直接转移过去即可。

由于每一行也至少要有一个 $1$ ，所以转移时一行中没有一个 $1$ 的方案数减掉即可。

代码：61682746

结果一看题解发现复杂度可以更优。

我们考虑容斥，有 $i$ 行 $j$ 列没有 $1$ ，所以答案就是：

\sum_{i = 0}^{n} (- 1)^{i} (\binom{n}{i}) \sum_{j = 0}^{n} (- 1)^{j} (\binom{n}{j}) k^{(n - i) (n - j)} (k - 1)^{n i + n j - i j}

当然写的好看一点也可以是：

\sum_{i = 0}^{n} \sum_{j = 0}^{n} (- 1)^{i + j} (\binom{n}{i}) (\binom{n}{j}) k^{(n - i) (n - j)} (k - 1)^{n i + n j - i j}

这样就可以 $n^{2} \log n$ 啦！

然后我们考虑继续优化。

我们观察后面那只 $\sum$ ：

\sum_{j = 0}^{n} (- 1)^{j} (\binom{n}{j}) k^{(n - i) (n - j)} (k - 1)^{n i + n j - i j}

我们发现她可以转换成一个二项式展开的形式，也就是把后面的 $(k - 1)^{n i + n j - i j}$ 看成是 $(k - 1)^{i (n - j)} \cdot (k - 1)^{n j}$ ：

\sum_{j = 0}^{n} (\binom{n}{j}) {(k^{n - i} (k - 1)^{i})}^{n - j} {(- (k - 1)^{n})}^{j} = {(k^{n - i} (k - 1)^{i} - (k - 1)^{n})}^{n}

于是最终答案就变成了：

\sum_{i = 0}^{n} (- 1)^{i} (\binom{n}{i}) {(k^{n - i} (k - 1)^{i} - (k - 1)^{n})}^{n}

复杂度 $O (n \log n)$ 。

Codeforces Round #472 (rated, Div. 1, based on VK Cup 2018 Round 2)

*A. Mystical Mosaic

*B. Three-level Laser

*C. Riverside Curio

D. Contact ATC

E. Wardrobe

F. Minimal Subset Difference

Codeforces Round #539 (Div. 1)

*A. Sasha and a Bit of Relax

*B. Sasha and One More Name

C. Sasha and One More Name

Codeforces Round #578 (Div. 2)

*A. Hotelier

*B. Block Adventure

*C. Round Corridor

*D. White Lines

E.Compress Words

Codeforces Round #589 (Div. 2)

*A. Distinct Digits

*B. Filling the Grid

*C. Primes and Multiplication

*D. Complete Tripartite

*E. Another Filling the Grid

Cite this post