Codeforces Round #766 ABCDE 题解 (Java/C++)

A. Not Shading

题解

显然如果(r,c)本来就是黑色，那么就输出0。如果r行或者c列有黑色，则输出1。如果存在黑色则输出2。如果连黑色都没有，那就输出-1。

代码

Java

C++

B. Not Sitting

题解

显然Rahul会尽可能的选择中间的座位，Tina会尽可能的缩在4个角。而当中间的位置被涂成粉色之后呢，那么Rahul会选择距离4个角最近的位置（距离4个角的距离中的最大值）。

于是我们对计算每个点道4个角的距离，然后排序后输出即可。

代码

Java

C++

C. Not Assigning

题解

显然每条边的边权都必须是质数，且相邻的两条边之间必然恰好有一条边的边权是2。因此，当且仅当这个树其实是一条链的时候，才有解。

因此只需要验证这个树是不是链，然后依次填2和3进去即可。

代码

Java

C++

D. Not Adding

题解

对于某一个数X，如果在最终的数组中所有的X的倍数的最大公约数是X的话，那么X一定应在最终的数组中。

因为如果这些数是X的倍数，所以其最大公约数无非两种可能：1. 等于X；2. 大于X。
对于大于X的情况，我们举一个例子来说明。[8,12,13]。当X为2时，我们发现最大公约数为4。那么说明其实4也应该在最终的结果数组里。

因此我们从大到小依次枚举每个数，并按上述方式检查即可。

代码

Java

C++

E. Not Escaping

题解

很明显的一个DP。只是代码实现稍显繁琐。

因为k最大是$10^5$，因此实际上有影响的点最多只有$2\cdot 10^5 + 2$个点（外加起点和终点）。
于是我们可以根据这些点建图，然后在图上DP即可。

我们令DP[i][j]表示第i层走到第j个房间的最小花费。
显然，假如我们知道a层的最终开销之后，我们可以根据梯子的情况用DP[a][b]更新DP[c][d]的值。
但此时DP[c][d]的值其实不是最终的开销，因为还可能从DP[c][e]走到DP[c][d]以获得更小的开销。所以，$$\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}$$因此我们只需要从左往右和从右往左遍历两次即可得到最终的DP[c][d]的值。

最终我们只需要输出终点的值即可。

代码

Java

C++