A. Not Shading
Solution:
Obviously if (r, c) is originally black, then output 0. Output 1 if row r or column c is black. Output 2 if black is present. If not even black, output -1.
Code:
Java
C++
B. Not Sitting
Solution:
Obviously Rahul will choose the middle seat as much as possible, and Tina will hide in the 4 corners as much as possible. And when the middle position is painted pink, then Rahul will choose the position closest to the 4 corners (the maximum distance from the 4 corners).
So we calculate the distance from each point to the 4 corners, and then sort and output.
Code:
Java
C++
C. Not Assigning
Solution:
Obviously, the edge weight of each edge must be a prime number, and there must be exactly one edge between two adjacent edges whose edge weight is 2. Therefore, there is a solution if and only if the tree is actually a chain.
Therefore, it is only need to verify whether the tree is a chain, and then fill in 2 and 3 in turn.
Code:
Java
C++
D. Not Adding
Solution:
For a certain number X, if the GCD of all multiples of X in the final array is X, then X must be in the final array also.
Because if these numbers are multiples of X, there are only two possibilities for their GCD: 1. equal to X; 2. greater than X.
For the case greater than X, we give an example to illustrate. [8, 12, 13]. When X is 2, we find that the GCD is 4. Then it means that 4 should also be in the final result array. But not 2.
So we enumerate each number in order from large to small, and check it as above.
Code:
Java
C++
E. Not Escaping
Solution:
Clearly a DP problem. It's just that the code implementation is slightly cumbersome.
Since k is at most $10^5$, there are actually only at most $2\cdot 10^5 + 2$ points (include the start and end points) that have an impact.
So we can build a map based on these points, and then DP on the map.
We let DP[i][j] denote the minimum cost for the i-th floor to walk to the j-th room.
Obviously, if we know the final cost of floor a, we can update the value of DP[c][d] with DP[a][b] according to the situation of the ladder.
But at this time the value of DP[c][d] is not the final cost, because it is possible to go from DP[c][e] to DP[c][d] to obtain a smaller cost. So,$$\text{DP[c][d]} =
\begin{cases}
\text{dp[c][e]}+\text{x[c]}\cdot|d-e|, & d > e\\
\text{dp[c][e]}+\text{x[c]}\cdot|e-d|, & e > d
\end{cases}$$Therefore, we only need to traverse from left to right and from right to left twice to get the final value of DP[c][d].
In the end we just need to output the value of the end point.
Code:
Java
C++
