【题解】Wannafly挑战赛5
(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)
T2 可编程拖拉机比赛
T3 标准差
出题人的做法:
验题人的做法:
T5 喵喵的盆栽
T1 珂朵莉与宇宙
值域只有10
所以只用考虑0 -> 1000的完全平方数
for一遍,然后暴力一下
O( nsqrt( na ) )
按题意模拟即可
就是用ceil减去floor
出题人的做法:
首先发现这个n才30,m才100
我们可以两眼一闭大力搜
先搞出根可达的所有点
然后搜,找到一个环的话,要么不在上面转,要么在上面转永久次,所以可以直接拿那个环的方差来当答案
然后就15ms AC……
其实就算被卡了也可以用SA或者其他的随机化算法爆搞吧
感觉不可能卡得掉啊
T4 子序列
考虑统计不包含T作为子序列S的个数。那么枚举T的是S的子序列的最大前缀是T[1..i],考虑T[1..i]在S中的位置,我们选择尽量靠前的方案,那么选的方案是C(m,i),剩下的分成i+1段,每一段都不能出现后一个字符,比如第一段不能出现T[1]等等,于是答案就是
时间复杂度:
出题人给的做法:
容易发现第i个盆栽里切割后会对树高产生变化的边一定是从根i往下的一条链。于是我们可以DP出每个顶点作为根时那条链的尾端点。这样对于每个询问只需要求出树上两路径交即可。
验题人的做法:
首先发现可以删的边一定是连续的一段边,然后可以发现可以删的边一定是从查询的点a,b的lca到a的一段,和lca到b的一段可以考虑用toptree支持:换根Cut一个边查询一个点子树的最大深度(应该可以支持吧我也没写过这东西)