Codeforces Round 926 (Div. 2)

A - Sasha and the Beautiful Array

给出的是差分的和，显然等于最后一个减掉第一个，于是答案为最大值减最小值。

Submission

B - Sasha and the Drawing

观察到：前几次操作可以使答案 \(+2\)，之后每次只能让答案 \(+1\)。手玩一下发现最优方案是先填满第一列，再从最后一列第二行填到倒数第二行，这样前 \(2n - 2\) 次都是 \(+2\)。

Submission

C - Sasha and the Casino

每次的赌注需要满足：赢了之后总收益为正。因为你可以在任一时刻赢一次，并用掉保底。

设已经花费了 \(r\)，则下一次下注的 \(c\) 需要满足 \(kc > r + c\) 即 \(c > \dfrac{r}{k - 1}\)。由于 \(c\) 为整数，于是可以写成 \(c > \left\lfloor\dfrac{r}{k - 1}\right\rfloor + 1\)。

如果存在一种方案，每一步都满足上述条件，且赌到保底时手上的硬币都还足够，那就可行。

显然第一次用 \(1\) 枚硬币最优，由于 \(x\) 很小，直接暴力计算即可。

注意这个 \(r\) long long 都存不下，超过 \(a\) 了要立即退出。

Submission

D - Sasha and a Walk in the City

树形 DP，设 \(dp_{u, 0 / 1 / 2}\) 表示 \(u\) 的子树中的所有叶子到 \(u\) 的路径上最多有 \(0 / 1 / 2\) 个危险点的方案数。

转移需要额外记录这个最大值是否多次出现，于是多加一维 \(0 / 1\) 表示最大值是否多次出现。

子树答案可以简单合并：\(i, j\) 合并到 \(\max(i, j)\) 处，同时分讨一下处理最大值出现次数。

最后考虑自己能否标记为危险点，可以把 \(0\) 的所有方案加到 \(1\) 中，而只能把 \(1\) 的最大值只出现一次的方案加到 \(2\) 中，否则会出现一条经过 \(u\) 的经过 \(3\) 个危险点的路径。

时间复杂度 \(\Theta(n)\)。

Submission

E - Sasha and the Happy Tree Cutting

数据范围明示状压。

考虑给每条边标记一个 \(T_i\) 表示有那些关键路径经过它，之后可以设 \(dp_{i, S}\) 表示处理完前 \(i\) 条边，已经满足了 \(S\) 中的条件时需要选择的最小边数。

转移很简单：\(dp_{i + 1, S \cup T_i} \leftarrow dp_{i, S} + 1\)。

不过 \(O(n 2^k)\) 显然过不了，但是观察到 \(T_i\) 不同的边只有 \(O(k)\) 条（考虑对 \(2k\) 个关键点建立虚树，虚树上的边数即为 \(T_i\) 不同的边数，而虚树的边数为 \(O(k)\)），于是排序去重后做上面的 DP 即可。

虚树不用建，LCA 可以暴力，时间复杂度 \(O(nk + k 2^k)\)。

Submission

F - Sasha and the Wedding Binary Search Tree

BST 是吓人的，直接中序遍历转成序列。相当于给定一个序列中若干个位置和序列中每个数的值域，求有多少种不降序列。

直接枚举有限制的位置 \(i\)，设上一个有限制的位置为 \(j\)（令 \(0\) 处有限制，\(val_0 = 1\)），那么方案数相当于值域为 \([val_j, val_i]\) 的长度为 \(i - j - 1\) 的递增序列个数。考虑在后面追加一个位置并钦定它的值为 \(val_i\)，并转化为求差分的方案数。这相当于求长度为 \(i - j\)，和为 \(val_i - val_j\) 且每一位都非负的序列的个数，可空插板即可得出方案数为 \(\dbinom{val_i - val_j + i - j - 1}{i - j - 1}\)。注意到 \(\sum i - j = n\)，直接暴力求下降幂计算即可。

最后还剩下一段后面没有限制，考虑令 \(n + 1\) 处有 \(val_{n + 1} = C\) 的限制，继续套用上述方法计算即可。

预处理阶乘逆元可以做到 \(\Theta(n)\)。

Submission