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

A. Not Shading

题解

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

代码

Java

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

C++

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

B. Not Sitting

题解

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

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

代码

Java

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

C++

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

C. Not Assigning

题解

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

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

代码

Java

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

C++

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

D. Not Adding

题解

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

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

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

代码

Java

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

C++

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

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

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

C++

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