[Acwing Contest] 第 11 场周赛 题解

大家好,我是 Sora。这场周赛非常简单,所以写了 A 之后就没打了。

个人感觉 CF 有 1500 分就可以 AK 了。


A. 计算abc

题目描述

有三个正整数 \(a,b,c\),我们不知道每个数的具体值,但我们知道 \(a≤b≤c\)。

现在,以随机顺序给出 \(a+b,a+c,b+c,a+b+c\) 的值,请你求出 \(a,b,c\) 的值。

数据范围:\(2\le x_i \le 10^9\) 。

解法

解法相当显然。因为是正整数,所以最大的就肯定是 \(a+b+c\) 。

我们只需要排序,然后用最大的分别减去剩下最大的,次大的,最小的。

代码实现

您不会写这个?大佬说笑了。

CF 分数定位:\(\color\gray{800}\)。


B. 凑平方

题目描述

给你一个正整数 \(n\),你可以对 \(n\) 进行删位操作。求使得 \(n\) 可以成为某个正整数的平方的最小操作数。

数据范围:\(1≤n≤2×10^9\)。

解法 1

考虑拆位,发现拆字符串最多也只有 \(10\) 位,然后删除位置就 dfs 就可以了,,然后记下编辑距离,然后取最小值。

解法 2

预处理出平方小于 \(2 \times 10^9\) 的数插入一个 vector,然后每次查询就从位置向下找可能的数,同样取最小值,这里可以字符串 DP。

解法 3

直接 bfs。枚举删的位置,每次将该数开平方,如果是整数就接受,然后返回答案。

代码实现

在写解法 1 的时候注意前导 \(0\) 的处理。

剩下的不用的我说了哦。

CF 分数定位:\(\color\green{1300}\)。


C. 最大化最短路

题目描述

给定一个 \(n\) 个点 \(m\) 条边的不含重边和自环的无向连通图。边长度都为 \(1\)。指定图中的 \(k\) 个点为特殊点。

现在,你必须选择两个特殊点,并在这两个点之间增加一条边。所选两点之间允许原本就存在边。

我们希望,在增边操作完成以后,点 \(1\) 到点 \(n\) 的最短距离尽可能大。

输出这个最短距离的最大可能值。

解法

发现这题边长度都为 \(1\)。可以挖掘性质。

考虑不连通怎么做?不连通的话就在连通块里 bfs,找最远的重要点,然后一连,就是两个距离之和然后加一。

连通的话其实也差不多。同时从 \(1\) 和 \(n\) 开始同时 bfs。由于是连通的,那么总会交汇。每扫到一个重要点那就记下它的深度并且染色。全部染色完就停止。然后把两端的深度最大一加再加个 \(1\) ,和最短路取 min 就是答案。

代码实现

会 bfs 就能写。

CF 分数定位:\(\color\Turquoise{1500}\)。

上一篇:【CF】【思维】E. Replace the Numbers


下一篇:Codeforces Round #767 (Div. 2) 题解