Codeforces Round #827 (Div. 4) ABCDEFG Solutions (Java/C++)

A. Sum

Solution:

After sorting directly, see if the sum of the first two numbers is equal to the third number.

Code:

Java

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

C++

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

B. Increasing

Solution:

Sort directly, and then see if there are two adjacent numbers are equal.

Code:

Java

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

C++

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

C. Stripes

Solution:

Scan each row to see if you can find a whole row that is R. If so, then the last one painted must be R, otherwise it must be B. (You can’t paint nothing at all)

Code:

Java

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

C++

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

D. Coprime

Solution:

First, we found that the data range is only 1000. And the numbers that are relatively prime within 1000 can be found directly by $10^6$.
We put the found coprime numbers in 1000 lists, and for the $i$th list, only put all the numbers coprime with $i$ .

Then, for each number that appears in the array $a$, we record the largest index that appears, which is marked as max_pos. (If the result really chooses this number, it is better to choose a larger index than a smaller one.)

Finally, for each number $i$ that appears, go to the list at the beginning to find $j$ that is coprime with it, and then check whether the max_pos of $j$ exists, and then calculate the result of this pair, and finally take the largest one.

Code:

Java

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

C++

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

E. Scuza

Solution:

Obviously, binary search.

According to the array a, maintain a array: max. Where max[i] is the maximum value of a[i] from 0 to i. That is to jump to the i-th level, the step with the largest span that will be encountered in the process.
Also maintain a prefix sum of a.

Therefore, according to the input k, just binary search on the max array. The use the found i, and use the previously maintained prefix sum array to get the result.

Please note that the value range of a can reach $10^9$, so pay attention to the prefix sum array and use 64-bit int.

Code:

Java

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

C++

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

F. Smaller

Solution:

We count the number of letters in s and t.

Obviously, if there is a non-a letter in the string t, then directly put the non-a subtitle at the top, and at the same time, s puts a at the top.

Now t is full of letters a. Now suppose there is a letter in s that is not a.
If the number of letters a in s is less than t, then obviously s is greater than t anyway.
If the number of a in s is more than or equal to t, then s must be longer than t, so s is still larger than t.
In summary, as long as there is a letter other than a in s, then s must be greater than t.

In the end, there are only scenarios where both s and t are a's. Then just compare the length directly.

Code:

Java

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

C++

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

G. Orray

Solution:

First of all, it is obvious that the array b is single-incremented. At the same time, according to the value range of a, b has at most 64 different numbers. Because it is nothing more than ORing one bit into 1 each time. (In fact, there are 32, but I don’t want to think about long or int, and it’s the same to write 64 directly)
Therefore, for the arrangement of array a, only the arrangement of the first 64 bits will affect the result. (If b is still increasing after 64 bits, you can put the corresponding a in front, and the result must be better)

So directly enumerate the first 64 numbers with brute force. For the i-th number, we only need to ensure that the corresponding b[i] is as large as possible.

Code:

Java

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

C++

Submission #178707967 - Codeforces
Codeforces. Programming competitions and contests, programming community
DigitalOcean Referral Badge 蜀ICP备19018968号