大家好,我是 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}$。
%%%
%%%
%%%