1988D. The Omnipotent Monster Killer

由于只有相邻节点之间才有影响，树形dp即可。 权值每次至少减半，故杀死所有怪物的轮数不会超过\(\log n\)轮，相邻节点删去的轮数不同。 在有根树上dp，\(dp[i][j]\)代表在节点i在第j轮删除时，节点\(i\)子树的最小贡献。 状态转移： \(dp[i][j] = \sum_{v\in S_i}\min(dp[v][k]),k \neq j\)

1977E. Level Up

线段树+二分 第一次用自己写的线段树板子，爽捏。 对于每个位置，大于最小答案的每个k的取值都可以满足要求，故可以二分答案。check是计算答案为k时，前面的最小答案在1-k区间内的个数(即获得的exp)，然后按照题意判断即可。 一定要注意整型溢出的问题！！！ (因为在check的时候，使用了mid*a[i]与exp比较大小，而mid*a[i]是可能溢出的。) (当然，可以直接比exp/mid 和a[i]) 核心代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SegTree<int> t(n);
t.build();
for (int i = 1; i <= n; i++) {
    int ng = 0, ok = i + 1;
    while (ok - ng > 1) {
        int mid = (ng + ok) >> 1;
        int exp = t.qry(1, mid);
        if (exp / mid >= a[i]) {
            ng = mid;
        }
        else {
            ok = mid;
        }
    }
    ans[i] = ok;
    t.upd(ok, ok, 1);
}