Codeforces Round #828 (Div. 3) ABCDEF 题解 (Java/C++)

A. Number Replacement

题解

显然每个数字只能被替换为同一个字母，因此我们只需要开一个Map来检查是不是有数字被替换成了不同的两个字母即可。

代码

Java

C++

B. Even-Odd Increments

题解

统计奇数和偶数的个数以及总和。对于每次修改，我们只需要把x乘以个数加到总和里即可。
同时需要注意，当x为奇数时，会改变奇偶性。因此需要把个数和总和加到另外一个类型里。

代码

Java

C++

C. Traffic Light

题解

模拟即可，记录下所有的绿灯的下标。然后从左往右依次检查，随着检查的右移，符合的绿灯也会逐渐右移。
当发现绿灯不能再右移时，说明需要进入下一个周期。

代码

Java

C++

D. Divisibility by 2^n

题解

首先看看所有的a[i]里有多少个2，然后再检查每个i里面有多少个2。
如果所有的a[i]里的2不够，那么就对i排序，尽可能优先选择2比较多的i即可。

代码

Java

C++

E. Divisible Numbers (Easy/Hard)

题解

显然，如果条件修改成$a \leq x \leq c$且$b \leq y \leq d$，那么直接使x=a，y=b即可。
因此自然可以想到，我们给x和y分别乘以一个尽可能小的数。比如2。

进一步我们可以发现，如果x和y的初值分别为a和b。我们把x的一个因子给y，把y的一个因子给x，再把变小的数乘以一个尽可能小的数使其大于其原始值会比直接乘以2得到更好的结果。
比如a能被2整除，b能被3整除。那么交换因子2和3，于是$x=\frac 3 2 \cdot a$，$y=\frac 2 3 \cdot b$。于是x只增加了1.5倍。y需要在乘以某个数使其超过b。

于是我们枚举x和y的所有因子相互交换的情况即可。

代码

Java

C++

F. MEX vs MED

题解

显然，mex要大于med，那么必然所有小于med()的值都必须出现。也就是说，中位数以前的所有数字都必须全部出现，其他数无所谓。
于是对于给定的长度，其med()的结果必然是固定的，且小于等于med()的值都必须出现。

于是我们只需要枚举长度。对于每个长度，我们计算出包含所有必须出现的数的最小区间，然后根据这个最小区间计算扩展成所指定的长度有多少种方式即可。

代码

Java

C++