挑战赛25题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 小枫的大写字母 入门 T2 小枫的机器人 普及- T3 小枫的平方数 普及- T4 小枫的mex 普及/提高- T5 道路修建 普及/提高- T6 最小路径价值 普及+/提高
T1 小枫的大写字母
题目大意
输出字符串中唯一一个大写字母所在位置。
解题思路
遍历字符串，找到大写字母，输出对应位置即可。
参考代码
T2 小枫的机器人
题目大意
判断通过题目给出的行走路线，是否会经过重复的位置。
解题思路
考虑记录所有走过的位置，如果某个位置经历过两次及以上，则输出 Yes 。
但显然无法用二维数组直接记录，那么考虑使用 map<pair<int,int>,bool> ，其中 pair<int,int> 用于存放二维坐标 (x,y)(x,y)(x,y)。当移动到坐标 (x,y)(x,y)(x,y) 发现 map 中已经记录过此位置，则输出 Yes 。
参考代码
T3 小枫的平方数
题目大意
给定一个只包含数字的字符串，找出这个字符串重新排列组合后，能组成多少种不同的平方数。
解题思路
一个 131313 位数字，最大为 999999999999999999999999999999999999999 ，打表发现 101410^{14}1014 以内的平方数有 316227831622783162278 个。
所以我们可以先预处理出 101410^{14}1014 以内所有的平方数，再对这些平方数逐一检查是否可以被给定字符串组成。
在检查时，我们只需要判断 111 ~ 999 的数字个数是否完全相等，并且给定字符串 000 的个数要大于等于平方数的 000 的个数。
参考答案
T4 小枫的MEX
题目大意
给定一个序列，进行 qqq 次操作，每次操作后输出操作后的序列的 mexmexmex 。
解题思路
首先，很显然的是，无论进行怎样的操作，一个序列的 mexmexmex 一定不会超过 nnn 。
所以只需要记录和处理小于等于 nnn 的元素即可，这个过程可以通过桶数组 cnt 和 set 完成，其中桶数组用于记录当前序列中小于 nnn 的各个元素的个数，set 记录当前这个序列还没有出现过的数，即满足 cnt[i]=0 的数字 iii 。最终答案即为 set 中第一个数，输出 *s.begin() 即可。
参考代码
T5 道路修建
题目大意
有 nnn 个点，mmm 条边的无向图，如果点 aaa 和点 bbb 有一条边，点 aaa 和点 ccc 有一条边，而点 bbb 和点 ccc 之间没有边，则可以在点 bbb 和点 ccc 之间添加一条边，求最多可以添加多少条边。
解题思路
不难发现，在一个连通块内的所有点都可以通过若干次操作使得每两个点之间连上一条边。于是，我们求出每个连通块的大小 szszsz 和已有边数 edgsedgsedgs ，就可以求出连通块内没有连接的边数 sz×(sz−1)2−edgs\frac{sz\times(sz-1)}{2} - edgs2sz×(sz−1) −edgs，也就是答案。
可以用并查集维护 szszsz 以及 edgsedgsedgs 。
时间复杂度 O(nlogn)O(nlogn)O(nlogn)
参考代码
T6 最小路径价值
题目大意
有一颗 nnn 个结点的树，定义一个结点的路径价值为 f(x)=∑i=1n(wi×d(x,i))f(x) = \sum_{i=1}^{n} (w_i \times d(x, i))f(x)=∑i=1n (wi ×d(x,i)) ，求整棵树的最小路径价值。
解题思路
考虑计算所有结点的路径价值，取最小值即可得到答案。
以上实现方法很容易想到换根DP，设 sumisum_isumi 表示子树 iii 的权值和，即
sumi=∑j=subtreei(wj)sum_i = \sum_{j=subtree_i} (w_j) sumi =j=subtreei ∑ (wj )
并记录以 111 为根节点的路径价值 f(1)f(1)f(1) 。
接下来考虑换根，假设当前结点为 uuu ，父结点为 fafafa ，那么 f(u)=f(fa)+sum1−2×sumuf(u)=f(fa)+sum_1-2\times sum_uf(u)=f(fa)+sum1 −2×sumu
参考代码
