沙雕场
我杀我自己
A
- 写的时候没脑子
- 写完还没review
- 该死
B
模拟即可。
C
题意
给出长度为n，含有括号的？的字符串，问将？替换成左或者右括号，使得除了长度为n的前缀以外的前缀都没有完整的括号序列且不存在不合法的括号序列(右括号数量大与左括号数量)。
题解
- 对于所有的？，越靠近末尾越是）越好。
- 因为最后一个字符是),左括可能会和其匹配，但最后一个字符必须和第一个字符匹配，才可能合法。
- 用stack贪心维护。
D
题意
给一颗n个节点有根树，假设一共有k个叶子结点，那么每个叶子都是不重复中的一个值，每个非叶子节点有一个属性，要么是所有叶子max或者min，问根的最大值？
$(n\le 3·10^5)$
分析
- 树形dp
- 定义$dp_u:$ 节点 $u$ 的最大值, $sz_u$ 为子树 $u$ 中叶子节点的数量。
- 当 $u$ 是 $max$ 时：$dp_u = max(sz[u] - (sz[son]-dp[son])$，这种就是考虑那一部分代价最小，就把大的数放在那个子树。
- 当 $u$ 是 $max$ 时：$dp_u = 1 + \sum {(dp[son] - 1)(u 的所有son)}$，这种就是考虑每个子树可以抬的数量，但每个子树不是连续的一段数字(thx qls)