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

A. Era

Solution:

Just simulation. When we find a certain a[i]>i+ ans, insert the number of a[i]-(i+ ans).

Code:

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

Solution:

If n is an even number, then we use every single number to be a independent subarray. In this way, an even number of 1s are XORed, and the result must be 0.

If n is an odd number, similarly, we look for $a[i]\geq a[i+1]$, so that when these two numbers are put together, the even number of 1s will be XORed.

Code:

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

Solution:

Obviously, a[1] must not be divisible by 2, otherwise it must be NO. Because a[1] cannot be deleted by deleting the previous number. Similarly, a[2] can be at least not divisible by one of 2 and 3. And so on.

At the same time, we noticed that if a number is divisible by all the numbers between 2 and x, then this number must be divisible by the least common multiple of 2, 3,..., x.
Therefore, we only need to get the minimal x such that $lcm(2,3,\dots,x)>10^9$.

As long as a[i] can be divisible by a number between 2 and min(x, i). If it can be divided by all of them, it outputs NO.

Code:

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

Solution:

According to the relationship between x and y, there are the following situations:

  1. If x>y, then n=x+y. At this time, n mod x = y mod n = y.
  2. If x=y, n=x.
  3. If y>x and y mod x = 0. Then n=x. At this time, n mod x = y mod n = 0.
  4. If y<x and y mod x $\neq$ 0. At this point, we notice that both x and y are even numbers. Naturally, $n=\frac {\left \lfloor \frac y x \right \rfloor \cdot x + x} 2$.

Code:

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

The key to this question is to find that for any a[i], there are at most only $\sqrt a[i]$ different ways of possible splits. Taking 100 as an example, it must be impossible to split 100 into 20, 40, and 40. If the final 100 is to be split into 3 numbers, then it must be 33, 33, and 34.
With this, the dp part is easy to think of.

Codeforces Round #752 Extreme Extension Solution (Java/C++)
Solution:Obviously, we don’t need to consider the operation sequence. Therefore, we directly consider how to perform several operations on a certain number.
Click the link above for detail solution
Show Comments
DigitalOcean Referral Badge