# CodeForces VP 记录

Author: Fanyi Pu

Published: 2019-08-15

Canonical: <https://pufanyi.com/blog/oi-icpc/codeforces/codeforces-vp>

CodeForces Virtual Participation 记录与题解。

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

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

## [Codeforces Round #472 (rated, Div. 1, based on VK Cup 2018 Round 2)](https://codeforces.com/contest/956)

### \*A. Mystical Mosaic

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

反正直接模拟就可以了。

代码：[58555087](https://codeforces.com/contest/956/submission/58555087)

### \*B. Three-level Laser

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

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

显然如果 $i$ 和 $k$ 固定，那么 $\eta$ 与 $E_j$ 负相关，于是 $i=j-1$。

然后考虑枚举 $i$ 算 $k$，直接把上面的 $E_k$ 去掉即可：$\eta=\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](https://codeforces.com/contest/956/submission/58555515)

### \*C. Riverside Curio

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

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

代码：[58556096](https://codeforces.com/contest/956/submission/58556096)

### D. Contact ATC

题意是说有 $n(n\le 10^5)$ 架飞机在一条数轴上飞，坐标为 $x_i$，速度为 $v_i$，有 $x_iv_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](https://codeforces.com/contest/956/submission/58560521)

### E. Wardrobe

题解写在了[另一篇文章里](https://pufanyi.com/blog/oi-icpc/codeforces/cfdpproblems#codeforces-924e-wardrobe)。

### F. Minimal Subset Difference

太菜了，不会。

## [Codeforces Round #539 (Div. 1)](https://codeforces.com/contest/1109)

### \*A. Sasha and a Bit of Relax

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

显然只要 $\bigoplus_{i=l}^r a_i=0$ 即可，然后开个桶算。

代码：[58788064](https://codeforces.com/contest/1109/submission/58788064)

### \*B. Sasha and One More Name

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

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

代码：[58788424](https://codeforces.com/contest/1109/submission/58788424)

### C. Sasha and One More Name

数据结构题，直接抄了[这篇博客](https://www.cnblogs.com/TinyWong/p/10400682.html)的翻译：

维护以下三种操作

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

其中

$$
f(t) = v+\int_l^t g(x) \mathrm{d} x
$$

其中设在 $\left[l,r\right]$ 时间内的命令依次为 $(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)](https://codeforces.com/contest/1200)

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

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

自闭了：

![](https://pufanyi.com/posts/oi-icpc/codeforces/codeforces-vp/zibi.avif)

### \*A. Hotelier

直接模拟就可以了。

代码：[58884080](https://codeforces.com/contest/1200/submission/58884080)

### \*B. Block Adventure

还是直接模拟就可以了。

代码：[58884001](https://codeforces.com/contest/1200/submission/58884001)

### \*C. Round Corridor

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

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

![](https://pufanyi.com/posts/oi-icpc/codeforces/codeforces-vp/1200C.avif)

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

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

代码：[58883764](https://codeforces.com/contest/1200/submission/58883764)

### \*D. White Lines

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

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

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

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

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

代码：[58884654](https://codeforces.com/contest/1200/submission/58884654)

### E.Compress Words

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

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

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

代码：[58886006](https://codeforces.com/contest/1200/submission/58886006)

## [Codeforces Round #589 (Div. 2)](https://codeforces.com/contest/1228)

又是一场愉快的 Div. 2。

可惜窝还是爆蛋了……

### \*A. Distinct Digits

直接模拟即可……

代码：[61680483](https://codeforces.com/contest/1228/submission/61680483)

### \*B. Filling the Grid

直接模拟即可……

代码：[61680658](https://codeforces.com/contest/1228/submission/61680658)

### \*C. Primes and Multiplication

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

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

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

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

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

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

代码：[61681335](https://codeforces.com/contest/1228/submission/61681335)

### \*D. Complete Tripartite

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

直接模拟即可……

代码：[61681851](https://codeforces.com/contest/1228/submission/61681851)

### \*E. Another Filling the Grid

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

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

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

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

代码：[61682746](https://codeforces.com/contest/1228/submission/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)^{ni+nj-ij}
$$

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

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

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

然后我们考虑继续优化。

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

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

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

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

于是最终答案就变成了：

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

复杂度 $\mathcal{O}(n\log n)$。