Codeforces Round #752 (Div. 2) ABCDE 题解 (Java/C++)

A. Era

题解

模拟即可。当我们发现某一个a[i]>i+ ans时，插入a[i]-(i+ ans)个数即可。

代码

Java

C++

B. XOR Specia-LIS-t

题解

如果是n是一个偶数，那么我们以一个数为一个子串。这样就是偶数个1做XOR操作，其结果必然为0。

如果n是一个奇数，类似的，我们寻找$a[i]\geq a[i+1]$，这样把这两个数放在一起时，就又是偶数个1取XOR。

代码

Java

C++

C. Di-visible Confusion

题解

显然的，a[1]必须不能被2整除，否则一定是NO。因为a[1]没有办法通过删除前面的数来删除。同理a[2]至少能不被2或3中的一个整除。以此类推。

同时，我们注意到，如果一个数能被2到x之间的所有数整除，那么这个数一定能被2，3，…，x的最小公倍数整除。
因此我们只需要求出这个x，使得$lcm(2,3,\dots,x)>10^9$。

只要a[i]能被2到min(x, i)之间有一个数不整除即可。如果都整除就输出NO。

代码

Java

C++

D. Moderate Modular Mode

题解

根据x和y的大小关系，由以下几种情况：

1. 如果x>y，那n=x+y即可。此时n mod x = y mod n = y。
2. 如果x=y，n=x即可。
3. 如果y>x且y mod x = 0。那n=x即可。此时n mod x = y mod n = 0。
4. 如果y<x且y mod x $\neq$ 0。此时，我们注意到x和y都是偶数。那很自然的，$n=\frac {\left \lfloor \frac y x \right \rfloor \cdot x + x} 2$。

代码

Java

C++

E. Extreme Extension

这道题的关键在于，发现任意的a[i]，其实最多只有$\sqrt a[i]$种可能的拆法。以100为例，把100拆分成20，40，40是一定不可能的。如果最终100要被拆成3个数，那么一定是33，33，34。
有了这一点，dp部分就很顺理成章了。