竞赛讨论区 > 【题解】Wannafly挑战赛5
头像
王清楚
发布于 2021-11-23 14:31
+ 关注

【题解】Wannafly挑战赛5

T1 珂朵莉与宇宙

值域只有

所以只用考虑的完全平方数

for一遍,然后暴力一下

T2 可编程拖拉机比赛

按题意模拟即可就是用ceil减去floor

T3 标准差

出题人的做法:

枚举平均数 ,重算边权, .
二分答案,判断ST之间是否有长度为负的路径即可(负环也可以) .
通过计算可得二分的复杂度是
或者也可以是.
Bellman-Ford求负环复杂度
总复杂度,不太满。

验题人的做法:

首先发现这个

我们可以两眼一闭大力搜

先搞出根可达的所有点

然后搜,找到一个环的话,要么不在上面转,要么在上面转永久次,所以可以直接拿那个环的方差来当答案

然后就15ms AC……

其实就算被卡了也可以用SA或者其他的随机化算法爆搞吧

感觉不可能卡得掉啊

T4 子序列

考虑统计不包含T作为子序列S的个数。那么枚举T的是S的子序列的最大前缀是T[1..i],考虑T[1..i]在S中的位置,我们选择尽量靠前的方案,那么选的方案是C(m,i),剩下的分成i+1段,每一段都不能出现后一个字符,比如第一段不能出现T[1]等等,于是答案就是

时间复杂度:

T5 喵喵的盆栽

出题人给的做法:

容易发现第个盆栽里切割后会对树高产生变化的边一定是从根往下的一条链。于是我们可以DP出每个顶点作为根时那条链的尾端点。这样对于每个询问只需要求出树上两路径交即可。

验题人的做法:

首先发现可以删的边一定是连续的一段边,然后可以发现可以删的边一定是从查询的点的lca到a的一段,和lca到b的一段可以考虑用toptree支持:换根Cut一个边查询一个点子树的最大深度(应该可以支持吧我也没写过这东西)

全部评论

(0) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐