Arkweedy's Blog

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]) 核心代码：...

2008H. Sakurako's Test 关键是前缀和和二分 以及对边界做一点特殊处理防止前缀数组越界 二分有说法的，要通过二分找到右边界(和中位数定义有关) 或许还可以改改代码，感觉自己写的有点怪 1992G. Ultra-Meow 看清这题的数据范围，对\(\sum n^2\)做了限制，所以单测\(O(n^2)\)的复杂度是没有问题的，不需要预处理所有答案然后\(O(1)\)查询。 做法是对于每个可能的\(k = mex(S)\),对\(k\)分讨，算出每种k的贡献次数即可，复杂度\(O(n^2)\)。 需要一点点组合。 组合的板子在对负数的处理上好像有不兼容的的地方？ 回头看看，改一下板子，这句话还在这里就表示没有修改板子以及搞清楚原因