Codeforces Round #748 Red-Black Number 题解 (Java/C++)

题解

一个很明显的dp问题。

不难想到有这样几个状态：1、前i个数字；2、|r-l|；3、除以A的余数；4、除以B的余数。
于是我们就有这样的dp定义：dp[i][diff][a][b]表示从右往左的前i个数，红色比黑色多diff个（不取绝对值），除以A余a，除以B余b时是否可能。
然后因为最后要输出结果，我们需要在dp中额外记录当前的dp值是由谁更新的，因此需要记录下上一个diff，a和b。
所以，最终我们的DP定义是：dp[i][diff][a][b][data]。其中额外的data的取值是0-3。0记录当前的字母选择（R或B），1记录上一个diff，2记录上一个a，3记录上一个b。（显然的，dp[i]只会和dp[i-1]有关，因此不需要额外记录上一个i的值。）
另外需要注意的是，因为diff的值可能为负数，因此在代码实现过程中，diff需要+40之后再存储。同时，如果dp[i][diff][a][b][0]不是R或者B就表示不可能构造出这种情况。

有了状态，状态转移就比较容易了。
首先，当我们有了i和diff之后，我们就能得出当前到底有多少块涂了红色，有多少块涂了黑色。因为根据定义，我们有$\begin{cases}
\text{count_a} + \text{count_b} = i + 1\\[2ex]
\text{count_a} - \text{count_b} = \text{diff}
\end{cases}$，其中count_a表示涂成红色的数目，count_b表示涂成黑色的数目。于是我们有$\begin{cases}
\text{count_a} = \frac {i+1 +\text{diff}} {2}\\[2ex]
\text{count_b}= \text{count_a} - \text{diff}
\end{cases}$。
接着我们考虑如何利用dp[i]推导出dp[i+1]的状态。这时，无非两种情况：1. 把x[i+1]涂成红色；2. 把x[i+1]涂成黑色。于是当dp[i][diff][a][b][0]是R或者B（也就是存在这种可能）时，如果涂成红色：$$\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}$$如果涂成黑色：$$\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}$$以涂成红色为例，因为多涂了一个红色，所以diff+1。因为把x[i+1]涂成红色，所以红色的值增加了$10^{\text{count_a}} \cdot \text{x[i+1]}$，于是和已有的值a相加后，对A取余数。