※ 引述《[email protected] (...)》之铭言： : ※ 引述《sophialiege ()》之铭言： : : 令[u,v]是正解 : : 就是最佳解的最低处高度是u,v是最高处 : : 因为每个格子的值在0~99之间,所以u和v也是在这之间 : : 对於每一组假设的[u,v],你可以在图上将高度介於这之间的位置做记号 : : 看连通的记号足不足够盖一个部落 : : 再来是要降复杂度,假如[u,v]足够盖,那麽[u,v+k] (k 是正整数) : : 也一定足够 ==> bisch is possible : : 故复杂度粗估是 Constant * 100 * 8 * 40 * 40 : : ^^^ ^^^ ^^^^^^^ : : u log(v) graph search : 真神奇 原来可以这样子来降低时间复杂度 : 我了解了 谢谢你 :) : 另外再请教一件事情 : 我在讨论版看到有人宣称他使用了 union-find 来缩短时间 解决这一题 : 如果真是这样 那要怎麽做呢? 我想应该是在"graph search"时他用union and find来进行分堆 这样可以降掉一般搜寻的常数 --

※ 发信站: 批踢踢兔(ptt2.cc) ◆ From: 218.162.202.42