专栏文章

p3523 sol（POI2011 DYN）

AAllenJYL
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqqi1vs
此快照首次捕获于
2025/12/04 09:05
3 个月前
此快照最后确认于
2025/12/04 09:05
3 个月前
查看原文
套路地二分答案 ww 转化为判定。实质上就是选出 mm 个点使得每个关键点的 ww 邻域中至少有一个选中点。
由于选点也满足单调性，我们不妨计算出使得每个关键点的 ww 邻域中至少有一个选中点的选点方案至少需要多少个点。
考虑递推。设计状态 fif_i 表示 ii 子树内距离 ii 最远的还不合法的关键点的距离。为了转移，还需要设计 gig_i 表示 ii 子树内距离 ii 最近的选中点的距离，以及 hih_i 表示 ii 子树内选中的点数。
考虑到合并子树，首先令
  • fi=max⁡(fv)+1f_i=\max(f_v)+1；
  • gi=min⁡(gv)+1g_i=\min(g_v)+1；
  • hi=∑hvh_i=\sum h_v。
其中 vv 是 ii 的儿子。特别地
  • 若 ii 子树内没有不合法关键点则 fi=−∞f_i=-\infty；
  • 若 ii 子树内没有选中点则 gi=+∞g_i=+\infty。
分两种情况考虑：
  • 若 di=1d_i=1，说明 ii 为关键点，此时
    • 若 gi≤wg_i\le w，那么 ii 合法，不需要额外考虑；
    • 否则，ii 当前不合法，计入 fif_i，即 fi←max⁡(0,fi)f_i\larr \max(0,f_i)；
  • 否则，ii 不为关键点，此时显然能不选择其就不选择其，因为越浅的节点可以覆盖的其他子树内的节点数就越多，将选择的点留到更浅的节点上更优，所以
    • 若必须选择其，则 hi←hi+1h_i\larr h_i+1，gi←0g_i\larr 0；
    • 否则，不需要额外考虑；
    判断必须选择当且仅当 fi=wf_i=w。
额外地，如果 fi+gi≤wf_i+g_i\le w，则令 fi=−∞f_i=-\infty。
初值容易判断。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...