Codeforces Round #765 ABC Solutions (Java/C++)

A. Ancient Civilization

Solution:

Count the number of Xs where each bit is 1. If a bit has more than half of 1's, then y is 1 in that bit, otherwise it's 0.

Code:

Java

C++

B. Elementary Particles

Solution:

For any two identical numbers, at least, we can find l and r of length 1. Also quite naturally, we would want to extend the lengths of l and r.
Obviously, if the expansion to the right, the number on the right has more restriction; if it is expanded to the left, the number on the left has more restriction.
Therefore, two adjacent numbers that are the same must end up being longer than two non-adjacent numbers.

Therefore, we only need to record the position of the last occurrence of each number, so that the maximum length corresponding to the current number can be quickly calculated each time.

Code:

Java

C++

C. Road Optimization

Solution:

Obviously a DP problem.

dp[i][j] represents the minimum time required to reach the i-th road sign when j road signs are removed.
By definition, obviously dp[0][j]=0. It should be noted that here I also defined dp[0][2]=0, that is to say: the quota for deleting road signs is allowed to be wasted.

Then for i not equal to 0, dp[i][i - 1 - j + x]=min{dp[j][x]+a[j]*(d[i]-d[j])}.
That is, consider the minimum time to reach the i-th road sign and there are no other road signs from j to i. Obviously it takes a[j]*(d[i]-d[j]) time to get from j to i.
Among them, it is assumed that x road signs have been deleted when reaching j. Then at this time, plus deleting all road signs between i and j, a total of x+i-1-j road signs are deleted.

Finally, find the minimum value of dp[n+1].

Code:

Java

C++