(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）
T1 鲲
典型的追及问题，其中值得注意的是，HtBest反向游回起点时有可能被在起点等待的鲲抓到。
T2 鹏
考虑保存⼀下前⼀座⼭之后最低点，这时如果遇到下坡，就判断⼀下下坡后的点是否≥之前保存的最低点，如果是，则需要多翻越⼀次。
T3 桃花
两遍dfs，第⼀遍从任⼀点开始，找到距这个点最远的点，他⼀定是直径的⼀端，然后从这个点开始再dfs，找到最远的距离，输出即可。
T4 字符串丝带
考虑用⼀个数组保存下每个字母的最后出现位置，然后用⼀个数组f，f[i]表示第i个位置的该字母之前出现的次数即可。
T5 对弈
模拟下棋，下⼀步棋判断⼀下这个新落的⼦是否会影响胜负即可。
T6 发电
用树状数组维护每个节点的发电效率，除法用逆元搞。
T7 指纹锁
思考会发现set的实现⽅式与这个有惊⼈的相似处，需要重载⼀下运算符，差距小于k的返回相等，删除操作用while⼀个⼀个指纹来删，知道查询不到指纹x为⽌。
T8 挖沟
裸的最小⽣成树。
T9 公交线路
原题目前我能想到的算法是O(n^2*2^n)的，显然通过不了n=100的数据。
修改后该题是⼀个单源最短路问题，可以考虑使用Dijkstra或者SPFA算法实现。
T10 洋灰三角
矩阵快速幂，转移矩阵：
k 1 1 0
0 1 0 1
0 0 1 0
0 0 0 1
初始矩阵：
1 //答案
p //转移时需要加的值
1 //维护答案
p //维护转移时需要加的值
其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305
全部评论
(1) 回帖