树的点分治

jys posted @ Jul 29, 2013 09:51:28 PM in 未分类 , 1120 阅读

分治的一个重要技巧是每次递归的复杂度必须只能和当前处理的子树大小有关,所以flag的清零啊什么的都要把扫过的点重新扫一遍。

如果把已经处理过的子树和当前子树看作两棵子树的话点分治还是挺好写的。

把已经扫过的子树中的所有点记录到一个序列中,如果需要重新扫这棵子树那么就扫那个序列,可以让程序快不少。

还是很担心如果考试考到点分治会被卡成暴力分。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter