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$ 以后找到了反例，于是以为排序是错的…… 太菜了啊。