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

代码