Looking for a challenge刷题记录

QAQ从教练那里借来了这本书,我对着这本书刷一波POI题好了TAT

我已经做了1


AMPPZ2011 Ants

考虑对树上的每个位置用一个实数数对(a,k)去表示,其中a表示蚂蚁沿着边,需要走多少条边能到达这个位置,k表示这个点的高度,即根到达这个点需要经过几条边(不走蚂蚁路线)。那么记(f(a,k,s_{u},s_{d})表示向上走的速度为s_{u},向下走的速度为s_{d},需要多久能够到达(a,k)这个位置。显然有

f(a,k,s_{u},s_{d})=\frac{a+k}{2}s_{u}+\frac{a-k}{2}s_{d}

至于为什么,考虑和差公式,向上边和向下边的和一定是a,向下边和向上边的差一定就是k,因为会抵消掉非达祖先链上的边。

那么假设左边的这只蚂蚁走到了(a,k)这里,且相遇点在下一条边的某个位置。我们设\varepsilon表示这个相遇点到(a,k)的距离,那么有

a_{1}=a+\varepsilon,k_{1}=k+b\varepsilon

其中b表示这条边是向上边(1)还是向下边(-1),新的(a_{1},k_{1})即相遇点。显然一定满足等式

f(a_{1},k_{1},2,1)=f(2n-a_{1},k_{1},1,\frac{1}{2})

于是解得

\varepsilon=\frac{6n-k-9a}{9+b}

也就是说第一次相遇的时间应该是

t_{1}=a_{1}+k_{1}+\frac{a_{1}-k_{1}}{2}=\frac{3a_{1}+k_{1}}{2}

接下来我们考虑返回的时间,即左边的蚂蚁需要f(a1,-k1,2,1)的时间,容易算出来是t_{1}-k_{1},右边的蚂蚁同理,需要的时间是t_{1}-\frac{k_{1}}{2},易得左边蚂蚁比右边蚂蚁先回到树根。

那么接下来问题就是考虑第二次相遇,不妨假设右边的蚂蚁回到了(a',k')这个位置,且下一条边就和左边的蚂蚁相遇了,那么再次设走到了(a_{2}=a'+\gamma,k_{2}=k'+b'\gamma)。考虑同样的式子,有

f(2n-a_{2},k_{2},2,1)+f(a_{1},-k_{1},2,1)=f(a_{2}-a_{1},k_{2}-k_{1},1,\frac{1}{2})

解之得

\gamma=\frac{12n-k_{1}+9a_{1}-9a'+k'}{9-b'}

进一步我们得到

t2=\frac{3(a_{2}-a_{1})+(k_{2}-k_{1})}{4}

最终,得到

t1+t2=\frac{3(a_{1}+a_{2})+(k_{1}+k_{2})}{4}

读入的十六进制每位拆8421码即可,容易发现所有数乘上800一定是个整数,这样就可以做到输出既约真分数了。时间复杂度O((n+\log1e9)T)


 

发表评论