Codeforces Round #748 Red-Black Number Solution (Java/C++)
Solution:
A very obvious DP problem.
It is not difficult to think of several states: 1. The first i numbers; 2. |r-l|; 3. The remainder of division by A; 4. The remainder of division by B.
So we have this definition of dp: dp[i][diff][a][b] represents that: for the first i numbers from right to left, when red is more diff than black (not taking the absolute value) and divided by A remainder a and divided by B remainder b, can be build or not.
Then because the coloring method needs to be output at the end, we need to additionally record who updated the current DP value in the DP state, so we need to record the last diff, a and b.
So, the final definition of our DP is: $$\text{dp[i][diff][a][b][data]}$$The value of the additional data is 0-3. 0 records the current letter selection (R or B), 1 records the previous diff, 2 records the previous a, and 3 records the previous b. (Obviously, dp[i] is only related to dp[i-1], so there is no need to record the value of the previous i.)
Another thing to note is that because the value of diff may be negative, in the code implementation process, diff needs to be stored after +40. At the same time, if dp[i][diff][a][b][0] is not R or B, it means that it is impossible to construct such a situation.
With state, state transition is easier.
First, when we have i and diff, we can figure out how many digits are painted red and how many digits are painted black. Because by definition, we have:$$\begin{cases}
\text{count_a} + \text{count_b} = i + 1\\[2ex]
\text{count_a} - \text{count_b} = \text{diff}
\end{cases}$$.Where count_a represents the number of digits painted in red, and count_b represents the number of digits painted in black. So we have:$$\begin{cases}
\text{count_a} = \frac {i+1 +\text{diff}} {2}\\[2ex]
\text{count_b}= \text{count_a} - \text{diff}
\end{cases}$$
Then we consider how to use dp[i] to derive the state of dp[i+1]. At this time, there are nothing more than two cases: 1. Paint x[i+1] in red; 2. Paint x[i+1] in black. So when dp[i][diff][a][b][0] is R or B (that is, there is such a possibility), if it is painted in red:$$\begin{cases}
\text{dp[i+1][diff+1][(a+$10^{\text{count_a}} \cdot \text{x[i+1]}$)%A][b][0]} = \text{'R'}\\[2ex]
\text{dp[i+1][diff+1][(a+$10^{\text{count_a}} \cdot \text{x[i+1]}$)%A][b][1]} = \text{diff}\\[3ex]
\text{dp[i+1][diff+1][(a+$10^{\text{count_a}} \cdot \text{x[i+1]}$)%A][b][2]} = \text{a}\\[4ex]
\text{dp[i+1][diff+1][(a+$10^{\text{count_a}} \cdot \text{x[i+1]}$)%A][b][3]} = \text{b}
\end{cases}$$If it is painted in black:$$\begin{cases}
\text{dp[i+1][diff+1][a][(b+$10^{\text{count_b}} \cdot \text{x[i+1]}$)%B][0]} = \text{'R'}\\[2ex]
\text{dp[i+1][diff+1][a][(b+$10^{\text{count_b}} \cdot \text{x[i+1]}$)%B][1]} = \text{diff}\\[3ex]
\text{dp[i+1][diff+1][a][(b+$10^{\text{count_b}} \cdot \text{x[i+1]}$)%B][2]} = \text{a}\\[4ex]
\text{dp[i+1][diff+1][a][(b+$10^{\text{count_b}} \cdot \text{x[i+1]}$)%B][3]} = \text{b}
\end{cases}$$Take the color red as an example, because one more red is painted, so diff+1. Because x[i+1] is painted red, the value of red is increased by $10^{\text{count_a}} \cdot \text{x[i+1]}$, so it is added to the existing value a and take the remainder of A.
Finally, we only need to see if there is a solution for dp[n-1][diff][0][0], and then find out the choice of coloring for each decision in turn according to the records.
Code:
Java
It should be noted that the performance of Java's multi-dimensional array is very bad, so it needs to be converted into a 1-dimensional array as much as possible. If it is a 2-dimensional array, you need to put the smaller value in front as much as possible (int[4][100] will perform better than int[100][4]).
C++