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

# [CodeCraft-20](https://codeforces.com/contest/1316)

## [A. Grade Allocation](https://codeforces.com/contest/1316/problem/A)

### 问题重述

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

### 题解

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

[代码](https://codeforces.com/contest/1316/submission/72494551)

## [B. String Modification](https://codeforces.com/contest/1316/problem/B)

### 问题重述

给你 $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$ 貌似得用后缀数组 (并不会) ……

[代码](https://codeforces.com/contest/1316/submission/72664133)

## [C. Primitive Primes](https://codeforces.com/contest/1316/problem/C)

### 问题重述

给定两组多项式系数 $\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}|)$
的算法。

[代码](https://codeforces.com/contest/1316/submission/72433846)

## [D. Nash Matrix](https://codeforces.com/contest/1316/problem/D)

### 问题重述

给定一组操作 $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$ 的点，
就无解。

[代码](https://codeforces.com/contest/1316/submission/72445453)

## [E. Team Building](https://codeforces.com/contest/1316/problem/E)

### 问题重述

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

[代码](https://codeforces.com/contest/1316/submission/72561732)
