11.07图论水题Test
| 题目 | 描述 | 做法 |
|---|---|---|
| \(BSOJ6378\) | 在\(i\)位置可以到\(i+a_i\)或\(i+b_i\)求\(1\rightarrow n\)字典序最小路径 | 判可达性后贪心\(dfs\) |
| \(BSOJ5154\) | 过长 | 裸的期望\(dp\) |
| \(BSOJ5155\) | 多次询问:树上路径\(x\)到\(y\)，初始\(c\)元，每次碰到比当前最大值大的就买，求购买次数 | 倍增预处理，二分 |
\(T1\)
注意数组含义(\(vis\&able\))
\(T2\)
注意概率不是出度，而是可以到达的儿子数
\(T3\)
考虑我们处理出每个点向上第一个比它大的值设为\(f_{i,0}\)
首先很容易想到用倍增求它
我们设\(fa_{x,k}\)表示\(x\)的\(2^k\)级父亲,\(max_{x,k}\)表示\(x\)到\(fa_{x,k}\)之间最大值，
那么我们从大向小枚举\(k\),小于\(a_x\)就跳
那么\(fa_{t,0}\)就是答案
考虑\(fa_{x,k}\)和\(max_{x,k}\)可以去掉
我们用\(f_{fa_{x},0}\)来求\(f_{x,0}\)即可
最后询问有两种处理方式
可以离线把询问变点加进去
也可以在线做
后一种更快