好像不是题解,算是记录。
记一个 Trick:当求路径边权的中位数的最大值的时候,可以先二分一个答案 \(mid\),然后把大于 \(mid\) 的边设为 \(1\),否则设为 \(-1\)。这样只需要看路径长度是否大于零就可以判断出有没有中位数大于等于 \(mid\) 的情况了。
当然类似到求一个序列区间的中位数也同样可以这样,看区间和就行了。
反正中位数都可以这样搞。
写了 8k,\(3\) \(\log\) 草过去了,卡大常。
好像不是题解,算是记录。
记一个 Trick:当求路径边权的中位数的最大值的时候,可以先二分一个答案 \(mid\),然后把大于 \(mid\) 的边设为 \(1\),否则设为 \(-1\)。这样只需要看路径长度是否大于零就可以判断出有没有中位数大于等于 \(mid\) 的情况了。
当然类似到求一个序列区间的中位数也同样可以这样,看区间和就行了。
反正中位数都可以这样搞。
写了 8k,\(3\) \(\log\) 草过去了,卡大常。