闲话
某人写了 INTERNET YAMERO 上黑板
……我觉得会被跳过
另一个人写了 Brain Power 上黑板
A 老师：这玩意有词？
美式咖啡喝凉的好还是热的好？
模拟赛
这模拟赛打的 明天是要模拟如何翻盘？
T1
签到题。考虑直接枚举前面的 BABA...BA 是 \([1, r]\)，这样的 \(r\) 可以枚举 BA 长度后 check \(O(n)\) 段得到。然后就是统计 \([r + 1, n]\) 段和 BA 的 lcp 长度，可以二分得到。
通过哈希实现的总时间复杂度 \(O(n\log n)\)，注意数组是否越界。
T2
考场降智时刻。
考虑第一问。设 \(f(u)\) 表示子树内叶子情况全知道的最小花费，\(g(u)\) 表示有且只有一个叶子不知道的最小花费，转移就是 \(g(u) = \min_w\{\sum_{v \neq w} f(v) + g(w)\}, \ f(u) = \min\{\sum_v f(v), g(u) + c[u]\}\)。叶子初值 \(f(u) = c[u], g(u) = 0\)。
考虑第三问。设 \(fw(u)\) 表示子树内叶子情况全知道的所有情况，\(gw(u)\) 表示有且只有一个叶子不知道的所有情况，我们只需要按上面的最小情况转移即可。也就是说，上面加法改成乘法，上面最小值改成把所有最小情况加和即可。叶子初值 \(fw(u) = gw(u) = 1\)。
考虑第二问。我们按照上面的情况直接再做一遍递归即可。也就是说，我们按照最优方案 dfs，dfs 时记录当前节点子树内还有几个叶子不知道，再记忆化，保证只搜索 \(O(n)\) 次。
总时间复杂度 \(O(n)\)。
T3
设 \(f(u, h)\) 表示到 \(u\) 点，还剩 \(h\) 点生命值时答案的期望。不难写出
我们发现，这是有后效性的，但是所有后效性只取决于 \(f(1, H)\) 这一个点的值。考虑如何把这个点的值删去。
引入变元 \(x = f(1, H)\)，我们设 \(f(u, h)(x)\) 为如上的期望对变元的函数。可以证明的是，\(\forall u, h, \ \dfrac{\text d}{\text dx} f(u, h)(x) \le 1\)。
证明考虑归纳法。
我们首先观察 \(f(n, h)(x)\)，这些函数总是定值 \(0\)，因此 \(\dfrac{\text d}{\text dx} f(u, h)(x) = 0 \le 1\)。
我们已经知道了对 \(\forall u\to v, \ f(v, h)(x)\) 全满足这条件，现在需要证明 \(f(u, h)(x)\) 也满足这条件。可以简记形态为
其中 \(\forall g_i(x), \ \dfrac{\text d}{\text dx} g_i(x) \le 1\)。它的曲线非光滑，但由于间断点都是第一类的，我们可以只对连续的部分考虑导数。也就是说我们只需要对 \(\min\) 的前后两部分分别归纳证明。前一部分是显然的，\(\dfrac{\text d}{\text dx} (x + c) = 1 \le 1\)，而后一部分可以知道
\[\dfrac{\text d}{\text dx} \left(\frac{1}{k}\sum_{i = 1}^k g_i(x) + c\right) = \frac{1}{k}\sum_{i = 1}^k \dfrac{\text d}{\text dx} g_i(x) \le \frac{1}{k} \sum_{i = 1}^k 1= 1 \]这也就证明了 \(f(u, h)(x)\) 也满足这条件。
考虑这是个 dag，点 \(u\) 的出边只会指向 \(> u\) 的点。因此假设我们已知了 \([l, n]\) 段都符合要求，总存在一个只连向 \([l, n]\) 段的节点使得我们可以拓展符合要求的区间，取 \(l - 1\) 即可。
证毕。
所以我们也能知道 \(\dfrac{\text d}{\text dx}f(1, H)(x) \le 1\)，即 \(\dfrac{\text d}{\text dx}(f(1, H)(x) - x) \le 0\)。这也就说明了 \(f(1, H)(x) - x\) 是有单调性的。我们只需要二分得到 \(f(1, H)(x) - x = 0\) 的 \(x\)，这 \(x\) 就是答案。
总时间复杂度 \(O(nH\log V)\)，其中 \(V\) 是答案的值域。