8.11

· · 个人记录

CF1994E Wooden Game

神金诈骗题。

最难的是想到只用分一个个的，因为如果把子树分开，和不分是等价的。

问题就转化成了一个数可以把它变小，问最大的或。

注意到 \sum s_i\le10^6，所以直接枚举每棵树留几个节点即可。

P3619 魔法

负收益的情况：

考虑一对(i,j)

i在j前的要求

  1. x>=a_i
  2. x>=a_j+a_i-b_i

==> x>=max(a_i,a_j+a_i-b_i)

j在i前的要求

  1. x>=a_j
  2. x>=a_i+a_j-b_j

==> x>=max(a_j,a_j+a_i-b_j)

哪个更小哪个更优。

也就是 b_i>b_j 时，i 更优

转化到树上，如果一个点的优先级是最高的，那么处理完它的父节点之后一定会立即更新它。可以把它和它的父节点合并起来，合成一个新点，再计算它的优先级，这个动态维护的过程可以用优先队列等方法。

高维前缀和。

容斥思想，枚举子集。

$g_S=\sum_{T\sub S} f_T$。 $f_S=\sum_{T\sub S} (-1)^{|S-T|}\times g_T$。