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

A. Era

题解

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

代码

Java

Submission #134482316 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #134482383 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. XOR Specia-LIS-t

题解

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

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

代码

Java

Submission #134495709 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #134495823 - Codeforces
Codeforces. Programming competitions and contests, programming community

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

Submission #134500590 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #134500794 - Codeforces
Codeforces. Programming competitions and contests, programming community

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

Submission #134503746 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #134503894 - Codeforces
Codeforces. Programming competitions and contests, programming community

E. Extreme Extension

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

Codeforces Round #752 Extreme Extension 题解 (Java/C++)
题解显然,我们不需要考虑操作顺寻。因此我们直接考虑对某一个数会如何执行若干次操作。同样是显然的,经过若干次操作后,我们希望拆分出的数字尽可能平均。
点击上面链接查看详细题解