CodeForces VP 记录

*A. Mystical Mosaic

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

反正直接模拟就可以了。

代码：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

*C. Riverside Curio

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

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

代码：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 \empty$ 即可，如果是同向的飞机 $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

太菜了，不会。

*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

*B. Sasha and One More Name

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

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

代码：58788424

C. Sasha and One More Name

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

维护以下三种操作

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$。

题解留坑吧……

打了场 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\le 10^{18},q\le 10^4$。

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

假设一段有 $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

*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

E.Compress Words

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

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

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

代码：58886006

又是一场愉快的 Div. 2。

可惜窝还是爆蛋了……

*A. Distinct Digits

直接模拟即可……

代码：61680483

*B. Filling the Grid

直接模拟即可……

代码：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

*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

*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

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

我们考虑容斥，有 $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)$。