Codeforces Round #688 (Div. 2) 题解

A.Cancel the Trains

题目链接:https://codeforces.com/contest/1453/problem/A
这题不多说,行列只有编号相同的车会相撞,故问题转化为统计行车号与列车号中编号相同的车。

B.Suffix Operations

题目链接:https://codeforces.com/contest/1453/problem/B
这道题目感觉挺难的,比赛的时候思考了很久……

题目大意

给你一个序列 a_1, a_2, \ldots, a_n,有两种操作:
* 给序列一个后缀的所有数字 – 1
* 给序列一个后缀的所有数字 + 1

现在问你可以将序列中的一个数字修改成任意的的数字的基础上,最少需要多少次操作将序列的数字变得相同。

题解

拿到题目后,一个很强的直觉 就是我们的操作只能对后缀进行,所以操作更改的其实是这个序列的差分,我们应该在这个序列的差分序列上进行考虑。

很容易发现,我们发现最优方案是将序列通过操作变换成 a_1,因为能覆盖到 a_1 的操作一定覆盖所有序列,这对于我们的目标没有帮助。

现在假设我们先不考虑任意变换数字,这个序列的最少操作次数是什么呢?其实是差分序列的绝对值之和: \sum_{i=2}^n|a_i-a_{i-1}|

现在考虑修改一个中间数字,假设是 a_k, 2\leq k \leq n-1,那么它只能影响求和式的 |a_k – a_{k-1}|,|a_{k+1} – a_{k}| 两项,我们通过将它修改到 \left[a_{k-1},a_{k+1}\right] 可以将这两项的值最小化到 |a_{k+1} – a_{k-1}|
如果修改首位的数字呢?那么其实就是把 |a_2 – a_1| 或者 |a_n – a_{n-1}| 从求和式子里面去掉。

我们线性地考虑所有的修改情况,然后找一个最优答案就行了。时间复杂度:O(n)

代码:https://codeforces.com/contest/1453/submission/100368203

C.Triangles

题目链接:https://codeforces.com/contest/1453/problem/C

题目大意

给你一个 n\times n 的网格,每个格子都是 0-9 的一个数字。
分别对于 0-9 每个数字 x 独立地考虑问题,我们可以先将棋盘上的某一个格子修改为 x,我们要找到所有满足以下条件的三角形,找到面积最大的三角形输出其面积。
1. 三个顶点所在的格子都是 x
2. 一条边平行于坐标轴

题解

读完题目应该发现平行于坐标轴这个条件大大地降低了题目的难度,所以解决的问题入手点也应该是它上。

我们先考虑问题的一半,即三角形某一条边平行于 X 轴。另一半只需要将矩阵转置后,即可转化为此问题。

我们考虑枚举三角形平行于 X 轴的那一条边,假设这条边在第 i 行,那么有以下几种可能:
1. 选取第 i 行的两个数字 x,然后将第一行或者最后一行的某个数字改为 x 组成一个三角形。
2. 将第 i 行的最左或者最右改为数字 x 和此行的另一个数字形成一条最长边,然后在同最上或者最下面的 x 组成一个三角形。

枚举每一行,都这样考虑一下,我们就可以求出对于 x 且三角形一条边平行于 X 轴 的最大面积。

剩余的部分就是重复运行此代码了,考虑 x \in [0, 9] 并且转置矩阵再考虑一遍。这个题目就是一个中规中矩的暴力,时间复杂度 O(n^2)

代码:https://codeforces.com/contest/1453/submission/100372856

D. Checkpoints

题目链接:https://codeforces.com/contest/1453/problem/D

题目大意

假设一个游戏有 n 个关卡,每一关可以有保存点或者没有,玩家顺次闯关。当玩家闯第 i 关时成功则进入第 i + 1 关;失败则掉回最近的一个有保存点的关卡 k(k \leq i)。另外,玩家闯关的成功率固定为 50%

现在,给定玩家通关游戏的期望闯关次数,要求构造一个长度不超过 2000 的游戏(分配每一关有没有保存点)。

题解

这道题目是一个数学题,我们首先应该能给定一个游戏正向地计算出闯关期望,然后再考虑根据这个过程解题。

我们定义 p_i 是当前位于第 i 关并通过第 i 关所需要的闯关次数。(如果第 i 关闯关失败,导致进度回退多消耗的次数也是计算在 p_i 中的),在这个定义下总闯关次数期望是 \sum p_i

我们算两个例子 1, 1, 1, 1,这个期望是 8,因为 p_1 = p_2 = p_3 = p_4 = 2
因为每一关都有保存点,我们进入第 i 关失败了还是从第 i 关重来,那么就有: p_i = 0.5 \times 1 + 0.5 \times (1 + p_i),解得 p_i = 2

接下来考虑没有保存点的情况 1 0 0 1 0,由上一个例子得 p_1 = p_3 = 2
第 2 关没有保存点了,第二关失败将从第一关开始打,所以有等式 p_2 = 0.5 \times 1 + 0.5 \times (1 + p_1 + p_2),故 p_2 = 4
第 3 关也没有保存点,第三关失败将直接回到第一关(常回家看看~),所以有等式 p_3 = 0.5 \times 1 + 0.5 \times (1 + p_1 + p_2 + p_3),得 p_3 = 8
第 5 关的情况和第二关相同,可以自己算一下 p_5 = 4

由这两个例子可以发现对于第 i 关,我们要向前找到最近的保存点位置(假设是 j\leq ip_i = 2^{i – j + 1}
再通俗一点就是有保存点将把通过此关的期望重置为2,没有保存点将让通过此关的期望是通过上一关的期望的两倍。

知道了这件事情之后,我们就可以贪心构造了。对于每一关首先尝试让这关没有保存点,看看期望步数会不会超,如果超了就让此关有保存点就行了。一直构造到达到目标期望步数。

代码:https://codeforces.com/contest/1453/submission/100378655

E. Dog Snacks

题目链接:https://codeforces.com/contest/1453/problem/E
这个题目好像不是很难啊,简单的考虑一下情况就可以了。

题目大意

你有一棵树,树上每个节点都有吃的,有一条狗从根出发,开始寻找吃的:
1. 他只能闻到距离不超过 K 的食物(如果找不到食物他就输了)
2. 他会从距离自己最近的有食物的节点中机智地挑一个过去吃了
3. 最终他要回到根节点(可以认为吃完所有食物之后距离根节点距离不能超过 K)

当他吃完所有食物且回到根节点时才算胜利。

现在给你树的形态,问你狗狗胜利所需要的最小的 K 是多少。

题解

拿到这个题目,感觉简单的统计一下就行了。因为进入每一颗子树之后肯定先把这颗子树吃完再出来,所以问题应该是一个统计子树相同的子问题(K和回到根距离),父节点处合并答案的形式,所以实际上我们对于每一颗子树都要计算子树内的 K 是多少,吃完子树内食物回到根要多远为 B

  1. 如果这是一个叶子节点,显然 K = B = 0

  2. 如果这是一个非叶子节点(且不为根),那么我们肯定要按照一定的顺序吃完其子树,并且最后返回根节点,那我们肯定找一个 B 值最小的子树最后吃。
    假设其子节点的返回为 K_1, K_2, K_3, \ldotsB_1, B_2, B_3, \ldots,假设 B 中最小的为 B_k
    那么此节点的 Kmax(\max K_i, \max_{i\neq k} (B_i + 2)),此节点的 BB_k + 1

  3. 对于根节点,与 2 基本相同,但是我们寻找一个 B 值最大的子树最后吃。
    假设其子节点的返回为 K_1, K_2, K_3, \ldotsB_1, B_2, B_3, \ldots,假设 B 中最大的为 B_k
    最终答案为 max(\max K_i, \max_{i\neq k} (B_i + 2), B_k + 1)

整个考虑的流程其实都是一个贪心的过程,递归的处理出所有节点的 B 与 K 之后,我们就能算出最终的答案。

时间复杂度:O(n)。(因为我代码里拍了个序我的代码复杂度 O(n \log n)

代码:https://codeforces.com/contest/1453/submission/100385420

F. Even Harder

题目链接:https://codeforces.com/contest/1453/problem/F

比赛的时候没时间做这题了,如果再有 1 个小时的话,我觉得是一定够做出来的。

题目大意

给定一个序列 a_1, a_2, \ldots, a_n,在位置 i 可以跳到 \left[i + 1, i + a_i\right](如果 a_i=0,则这个点没法跳了),我们从第 1 个点出发,最终的目标是跳到第 n 个点。

现在我们可以将一些点的 a_i 清零,使得从 1 号点出发仅有一条路到达 n 号点,问最少需要清零多少个 a_i

题解

可以很容易想到是一个动态规划,而且我们发现一维的状态肯定是不够的,因为题目中需要表示的信息有点和能够到达的区间,考虑在状态中表示这两个东西。

dp\left[i\right]\left[k\right] 表示仅有一条路跳到点 i 且 i 之前的点最远只能跳到 k 的最少清除次数,这里显然 k \geq i

转移的时候,我们依次计算所有的 dp\left[i\right]\left[\cdot\right],保证仅有一条路能够到达 i
需要我们枚举节点 j<i,这个节点满足 j<i\leq j+a_j,即 j 能跳到 i。同时,让节点 q \leq j-1 无法跳到节点 i 且让节点 p\in(j, i) 都不能跳到节点 i,如果能跳到我们强制把它清零,这里 cnt 为需要清零的点的数量。那么,

dp[i][j+a_j] = min(dp[i][j+a_j], dp[j][i-1]+cnt)

最后每次算完状态,我们还需要把状态从表示 仅有一条路跳到点 i 且 i 之前的点**刚好**跳到 k 的最少清除次数 纠正成 表示仅有一条路跳到点 i 且 i 之前的点最远只能跳到 k 的最少清除次数

时间复杂度 : O(n^2)
代码:https://codeforces.com/contest/1453/submission/100411686