CodeForces VP 记录

2019-08-15

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

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

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

*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 \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\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\)。

题解留坑吧……

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\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

Codeforces Round #589 (Div. 2)

又是一场愉快的 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)\)。

Cite this post

@misc{pu2019codeforcesvp,
  author = {Pu, Fanyi},
  title  = {CodeForces VP 记录},
  year   = {2019},
  month  = {8},
  url    = {https://pufanyi.com/blog/codeforces-vp}
}