T1 洞穴
本质上是给出树上两点之间的距离,还原树的结构。
可以直接\(floyd\)来判定。
进一步的可以对边进行排序每次取最小的加入集合即最小生成树的过程保证正确性。
T2 小度养小猫
本质上是求出一个贪心的顺序使得代价最小。
每个代价为\((t_i^2-i^2)c_i\)
展开\(t_i^2c_i-i^2c_i\)后面的一项为常数可以忽略。
就先考虑第一次喂猫会喂谁,那么剩下的猫的增量为\((2t_i+1)c_i\)
注意到左侧每个猫都相同所以优先喂\(c_i\)较大的。
利用堆即可完成贪心过程。
T3 简单题