Codeforces Round 1002 (Div. 2) A/B/C/D

A

题意

定义一个数列是好的，当且仅当其中每个元素都至少出现两次。现在给定两个长度为$n$的数列$a$和$b$，问能否通过打乱数列$a$的顺序之后将两个数列对应位置的元素相加得到新的数列$c$，使得数列$c$中至少有$3$个元素互不相同。

解法

首先一个显然的性质是，打乱$a$的顺序后对应相加，本质上就是把数列$a$和数列$b$两两配对求和。
一个容易想到的构造方案是，把$a$和$b$中最大的数分别相加，最小的数分别相加，之后把这两个数加起来，这样得到的三个元素一定是互不相同的。由于$a$和$b$中每个数字至少出现两次，因此不会出现“最大的数拿去加完之后没有了”的情况。
唯一的例外情况就是，某个数列中的元素全都相同，最大数和最小数一样。此时，只要考察另一个数列中的元素是否有$3$种以上即可。
复杂度$O(nlog_{2}n)$

B

题意

给定一个长度为$n$的数列$a$，和一个小于等于$n$的偶数$k$，要求把数列$a$切分成$k$个非空的段，之后将其中偶数编号的段连起来，末尾再拼上一个$0$，得到数列$b$，数列$b$中最小的满足“元素的值和从$1$开始计算的下标不相等”的下标即是这个数列$b$的权值，求这个权值的最小值。

解法

这题需要一些注意力。
首先，我们希望权值最小，而鉴于权值的计算方式，只要有一个更小的下标与元素的值不匹配，之后的位置是否匹配已经不重要了。
之后注意到，对于任意某一个下标，它可能的值在数列$a$中是一个连续的区间内的值——从之前的每一段都只取$1$个数，到之后的每一段都只取$1$个数，这个区间内的任意数字都可以构造成为数列$b$中这个下标的值。
因此，我们考虑对于下标$1$，这个区间内的数只要有一个不为$1$，那么答案就一定是$1$——因为没有比这个更小的下标了。
而如果区间内每一个都是$1$，此时注意到另一件事，当区间大小不为$1$时，取这个区间作为第二个段，那么在数列$b$中的第$2$个数就一定为$1$，因此答案就一定是$2$——因为不可能为$1$，而$2$是剩余下标中最小的。
那么最后一种情况，就是这个区间的大小恰好为$1$，实际上，只有$n$恰好等于$k$时符合这个条件，而此时数列$b$的内容是确定的（即是数列$a$中所有偶数位连起来），因此枚举一遍确认答案即可。
复杂度$O(n)$

C

题意

有$n$个数字，一开始均为$0$。执行$n$轮操作，每一轮操作为：每个数字均加上一个给定的值（每个数字加的值不一定相同），之后任意选择一个数字，使其变为$0$。求在最佳情况下，$n$轮操作之后，数字的MEX最大是多少。

解法

这题看似很复杂，实际上需要注意到一个很重要的点：数据范围中，每一轮每个数字加上的值至少为$1$。
为什么这件事很重要呢？因为考虑到MEX的定义，我们需要从$0$开始构造；从后往前倒推，在每一轮加的值都大于$0$的情况下，一定只有你最后一次选择的数字大小是$0$，其他数字都至少为$1$。
还没完——再继续往下推，会发现$1$也一定只会出现在倒数第二轮被选中，最后一轮加上了$1$并且没有被选中的情况下。这个规律是可以往下推的——也就是，最终能为MEX做出贡献的，除了最后一次被选中的那个$0$，其他的一定是从某一轮开始，每一轮都只加$1$，一直到最后为止的这些数字，并且它最后连续加了几轮$1$，就是这个数字能够做出为MEX贡献的范围。
因此答案就很简单了——每个数字求出每轮加的值的数列中后缀$1$的数量，把这个数量排序，然后尽量分配给MEX，看看到哪个数字为止没法分配，这个数字就是答案。
复杂度$O(n^{2})$

D

题意

给定两张无向连通图，点数相同。一开始两张图中各有一个token，执行以下操作无限次：两个token各沿着某条边走到另一个点，分别称为$u_{1}$和$u_{2}$，花费为$|u_{1}-u_{2}|$。问在最优方案下，最终最小的总花费是多少，或者花费一定会无限大。

解法

首先考虑一个无限次的操作，最终总花费有限的条件。容易想到，需要在最后无限循环花费为$0$的操作。而由于花费的定义，花费为$0$意味着两个token在两张图中对应的同一个点上。而需要无限循环，因此最终的条件就是，需要有一条边，这条边在两张图中都存在，那么最后两个token就可能可以在这条边上无限来回循环。
注意，这是一个必要条件，而不是一个充要条件，因为有可能两个token分别在这条边对应的两个点上，而不是同一个点，导致花费并不为$0$。
在这个基础上，我们的目标就是，以最小的花费达到这样的状态。由于数据范围只有$1000$，我们可以把两个token所在的点拼成一个数对，作为一个状态，这样的状态总数是$10^{6}$种，可以接受。那么我们知道，满足上面的条件的状态（也就是某一条两张图中都存在的边，所连接的两个点，两个token都在同一个点的状态。例如，一条这样的边连接了$u$和$v$两个点，那么$(u,u)$和$(v,v)$都是符合条件的状态）的花费就是$0$。之后就可以使用类似Dij的思路，逐个拓展每种状态的最优解了。
这样的做法复杂度是否可以通过呢？考虑到边的总数不超过$1000$，因此每条边最多用来在$4$个状态中更新，最终的复杂度也就是$1000$的平方级别。
复杂度$O(max(n^{2},m^{2}))$