随便写点（2）

本讲作业

例题

例1 【The Number Games】 CF-980E
例2 【Tree Shuffling】CF-1363E
例3 【删括号】 https://ac.nowcoder.com/acm/problem/21303
例4 【Company】 CF-1062E
例5 【Lightest language】 SP186
例6 【Tree】CF-468D （未考虑：字典序最小）
例7 【方差】DP讲解。

总结

复盘【删括号】和【Tree shuffling】思维流程
复盘【Tree】 CF468D 每一步如何往下思考的。
【Lightest language】 复现正确性证明。

• 思考另外一些贪心方法错误的原因（课上提到一个）。
• 如果要求 树是满 \(k\) 叉树，应该如何解决。请给出 \(\mathcal{O}(n log k)\) 算法！

作业

1【Big Bishops】 SGU-221 (区间DP 练习题)
2【圣诞树】 poj3013
3【黑白树】https://ac.nowcoder.com/acm/problem/13249
4【Teleporter】 agc004d
5【Royal Federation】SGU-216
6【宝藏 NOIP'17】 (状压dp）P3959
7 上次的【Ants in leaves】 需要自己完成证明。

例题

CF980E

关键转化：注意到删点不好删，考虑选点。

首先，\(n\) 号节点是一定需要选择的。

然后观察到每个节点的权重是 $ 2^i$，而 \(2^i > \sum_{j = 1}^{j < i} 2^j\)。因此，我们考虑贪心的使得剩下的最大编号的点 \(x\) 能选就选。

可以用 树状数组 判断 \(x\) 是否能选。