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取余数。

最后,我们只需要看dp[n-1][diff][0][0]是否存在解,然后根据记录依次找出每次决策涂色的选择即可。

代码

Java

需要注意的是,Java的多维数组的性能非常糟糕,因此需要尽可能转化为1维数组。如果是2维数组的话,需要尽可能将较小的值放在前面(int[4][100]的性能会高于int[100][4])。

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

C++

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

参考

Java: Multi-dimensional array vs. one-dimensional
For example: a) int [x][y][z] vs b) int[x*y*z] Initially thought I’d go with a) for simplicity. I know that Java doesn’t store arrays linearly in memory like C does, but what implications does...
Efficient implementation of multi-dimensional arrays in Java?
As far as I understand (from answers such as this), java has no native multi-dimensional continuous memory arrays (unlike C#, for example). While the jagged array syntax (arrays of arrays) might b...
展示评论