codecraft-20.md 5.7 KB

+++ date = "2020-03-15T11:40:00+08:00" draft = false tags = [] title = "CodeCraft-20 (Div. 2)" authors = ["xry111"] +++

CodeCraft-20

A. Grade Allocation

问题重述

给你 $n$ 个整数,让你修改一下它们,使得它们仍然是整数, 都在 $[0, m]$ 之内,平均值不变,且最大化第 $1$ 个数。

题解

SB 题,平均值不变就是和不变, 因此如果和不超过 $m$ 就把所有数加起来给第 $1$ 个数,剩下都变成 $0$ , 否则就把第一个数改成 $m$ 然后随便减小一下后面的数。

代码

B. String Modification

问题重述

给你 $t$ 个串,对于每个串 s,你可以选择一个整数 $k$, 然后从左往右依次翻转 s 的每个长度为 $k$ 的切片。 你选择的 $k$ 要使得得到的串字典序最小。 保证 $t \leq 5000$,$t$ 个串的长度之和不超过 $5000$。

题解

一开始把题读成了每个串长度不超过 $5000$,就得用 $\mathcal{O}(|s|)$ 或者 $\mathcal{O}(|s| \log |s|)$ 的算法, 死活做不出来。然而实际上题目说总长度不超过 $5000$,就可以写 $\mathcal{O}(|s|^2)$ 的大暴力了…… 直接模拟是 $\mathcal{O}(|s|^3)$ 的, 但我们可以找规律,发现如果 $n$ 和 $k$ 同奇偶,得到的串就是 s 向左循环移 $k - 1$ 位,否则就是 s 向左循环移 $k-1$ 位, 再把移到最后的 $k-1$ 个字符倒序。这样只要给定 $k$,就能 $\mathcal{O}(n)$ 地把得到的串构造出来,取最大即可。

如果真的是总长度可能达到 $5000 \times 5000$ 貌似得用后缀数组 (并不会) ……

代码

C. Primitive Primes

问题重述

给定两组多项式系数 $\mathbf{a} = {a_i}$ 和 $\mathbf{b} = {b_i}$, 两多项式乘积的系数是 $\mathbf{c} = {c_i}$。给定质数 $p$, 求 $t$ 满足 $p \nmid c_t$。保证有解。 $|\mathbf{a}|, |\mathbf{b}| \leq 10^6$。

题解

我们把 $c_i$ 的计算公式直接写出来:

$$c_0 = a_0 b_0$$ $$c_1 = a_0 b_1 + a_1 b_0$$ $$c_2 = a_0 b_2 + a_1 b_1 + a_2 b_0$$ $$c_i = \sum_k ak b{i-k}$$

我们先看 $c_0$,如果 $p \mid a_0 b_0$,问题就解决了。否则, $p \nmid a_0 b_0$,因为 $p$ 是质数,要么 $p \nmid a_0$,要么 $p \nmid b_0$。我们实际上只关心 $c_i \mod p$,如果 $p \nmid a_0$, 我们可以把公式中含有 $a_0$ 的项都划去。否则 $p \nmid b_0$, 可以把含有 $b_0$ 的项都划去。于是每个公式都会减少一项。 现在 $c_1$ 只有一项了,我们再对 $c_1$ 重复上面的讨论,要么 $t = 1$, 要么 $c_2, \cdots$ 都会再减少一项,结果 $c_2$ 又只有一项了。 不断这样做下去,就是 $\mathcal{O}(|\mathbf{a}| + |\mathbf{b}|)$ 的算法。

代码

D. Nash Matrix

问题重述

给定一组操作 $S = {U, D, L, R, X}$ ,分别表示上、下、左、右、不动。 如果有一个矩阵 $\mathbf{A} \in S^{n \times n}$, 我们可以模拟以矩阵中每个位置为起点的运动,把终点写在矩阵 $\mathbf{B} \in (\mathbb{Z} \times \mathbb{Z})^{n \times n}$ 的对应位置中, 如果运动不会终止就写 $(-1, -1)$。现在给定 $\mathbf{B}$,倒推 $\mathbf{A}$。可能无解。$n \leq 5000$。

题解

首先找到所有终点是自身的位置,把它标成 $X$, 直接暴力 DFS 就能找到那些最终到达它的其他点, 并顺便为它们标好上下左右。然后找到所有无限运动的位置, 如果有一个孤立的这样的位置,显然无解。 否则,只要有两个相邻的无限运动的位置,就把它们标记成移动到对方, 就实现了无限运动,然后把这两个位置 $p, q$ 当终点, DFS 找到能到达它们的,标着 $(-1, -1)$ 的位置,顺便为它们标上下左右, 使它们到达这 $p$ 或者 $q$。最后如果还有没标记上下左右或 $X$ 的点, 就无解。

代码

E. Team Building

问题重述

有元素的集合 $S$,以及一个映射 $a: S \rightarrow \mathbb{Z}^{p+1}$。 给定 $k$、$p$,让你选出子集 $S_k \subset S$,使得 $|S_k| = k$, 再从剩下的 $S / Sk$ 选出 $p$ 个元素组成的有序序列 $u$, 最大化收益: $$\sum{x \in S} a(x)0 + \sum{i} a(u_i)_i$$ 保证 $p \leq 7, p+k \leq |S| \leq 10^5$。

题解

如果 $k = 0$,就是一个特殊的一边只有 $7$ 个点的稠密二分图的匹配, 可以通过 $\mathcal{O}(2^p|S|)$ 的状压 DP 解决。 对于 $k > 0$,如果我们加一维状态表示 $S_k$ 里面现在放了多少个元素, 就变成 $\mathcal{O}(2^p k |S|)$,肯定 MLE 和 TLE 到人都没了。 然而,如果我们把 $S$ 中的元素按 $a(\cdot)_0$ 去降序排序, 就能实现取前面的元素进 $S_k$ 肯定比取后面的好, 这样我们 DP 的时候只要判断一下该状态中 $S_k$ 是否还没放满, 如果没放满就把未进入 $u$ 的元素塞到 $S_k$ 中,如果放满了, $S_k$ 中现有的元素肯定都比这个新元素好,所以把它丢掉就行了。 时间复杂度是 $\mathcal{O}(|S|(2^p + \log |S|)$。

这题其实排序挺容易想到的,但是比赛的时候我对于 $k=0$ 就想了个假贪心, 没找到反例,但加上 $k$ 以后找到了反例,于是以为排序是错的…… 太菜了啊。

代码