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 i$,$p_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, \ldots$ 与 $B_1, B_2, B_3, \ldots$,假设 $B$ 中最小的为 $B_k$。
    那么此节点的 $K$ 为 $max(\max K_i, \max_{i\neq k} (B_i + 2))$,此节点的 $B$ 为 $B_k + 1$。

  3. 对于根节点,与 2 基本相同,但是我们寻找一个 B 值最大的子树最后吃。
    假设其子节点的返回为 $K_1, K_2, K_3, \ldots$ 与 $B_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