欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

JZOJ6893. 【提高组模拟】小 T 与灵石(stone)题解

程序员文章站 2022-04-01 10:36:05
这道题需要转化,换根和卡常。首先将集合中的点拉出来,找它们的直径不需要什么虚树,随便挑一个集合里的点为根,做一遍dfs,找最远点x(要在集合里),以x为根重复以上操作,找到最远点y,x-y就是题解所谓“集合中点的直径”然后,f[i]f[i]f[i]值可以转化成i与直径中点距离加上直径长度的一半问题来了,如果有直径长度单数情况怎么办?方法1(题解):发现这时中点在边上,如果中点在x-y边上,考虑新建点z,x,y分别与z连边,长度为1/2,此时z就是中点,为了避免小数,将所有边权*2方法2(By F...

这道题需要转化,换根和卡常。
首先将集合中的点拉出来,找它们的直径
不需要什么虚树,随便挑一个集合里的点为根,做一遍dfs,找最远点x(要在集合里),以x为根重复以上操作,找到最远点y,x-y就是题解所谓“集合中点的直径”
然后, f [ i ] f[i] f[i]值可以转化成i与直径中点距离加上直径长度的一半
问题来了,如果有直径长度单数情况怎么办?
方法1(题解):发现这时中点在边上,如果中点在x-y边上,考虑新建点z,x,y分别与z连边,长度为1/2,此时z就是中点,为了避免小数,将所有边权*2
方法2(By FK)直径长度/2上取整,此时不必新建点,将x,y看成中点即可
我们在中点处(两个中点则两个中点都要)打上tag标记,代表直径长度/2上取整。
不可能nq复杂度更新f数组,考虑换根。
先从1开始dfs,那么有
a n s [ t ] = m i n ( m i n ( a n s [ s o n ] + 1 ) , t a g [ t ] ) ans[t]=min(min(ans[son]+1),tag[t]) ans[t]=min(min(ans[son]+1),tag[t])
然后换根,则有
a n s [ f [ k ] [ 1 ] ] = m i n ( a n s [ f [ k ] [ 1 ] , a n s [ t ] + 1 ) ans[f[k][1]]=min(ans[f[k][1],ans[t]+1) ans[f[k][1]]=min(ans[f[k][1],ans[t]+1)
本来需要消除儿子对根的影响,但是min并无所谓,sum就要
其实,理论上呢,这道题应该就结束了。
但是,这道题卡常加上OJ栈空间不够,让它十分恶心!
首先,你会发现自己RE78(如果不WA)
原因:OJ栈空间不够
解决方案:人工栈
然后就是各种各样的TLE
两点间距离可以用ST表预处理,虽然预处理是log的,但查询是O(1)的
此时,如果你还TLE,卡常吧
方法包括但不限于register,inline,if语句改三元运算符等
然后,运气好的话,你就可以AC了
或者依靠OJ的随机摆动,找到快的评测机AC
例如(不是我的):JZOJ6893. 【提高组模拟】小 T 与灵石(stone)题解
正负100ms都是常事,不要惊讶。

本文地址:https://blog.csdn.net/wangyuda123456789/article/details/110174850

相关标签: NOIP模拟