CF926 Div.2

C. Sasha and the Casino

赌场规则：如果下注 \(y(y > 0)\) 元，如果赢了则除了 \(y\) 元外，额外获得 \(y \times (k - 1)\) 元，否则则输掉 \(y\) 元；

并且你不能连续输超过 \(x\) 次

最初，你有 \(a\) 枚硬币，询问是否能够赢取任意数量的硬币

题解：思维

考虑这样一种策略：假设前面一直输，保证如果当前的这局赢了，盈利将超过亏损的钱，这种叫做倍投法，这样一旦赢了，我们重新从 \(1\) 开始下注

那么我们只需要暴力跑 \(x + 1\) 次即可

注意会爆 long long

D. Sasha and a Walk in the City

题解：树形 DP

定义 \(dp[i][0/1/2]\) 代表以 \(i\) 为根的子树中，从任意叶子出发到 \(i\) 的路径中有 \(0/1/2\) 个危险节点

\[dp[i][0] = 1 \\ dp[i][1] = \prod_{j} (dp[j][0] + dp[j][1])\\ dp[i][2] = \sum_j (dp[j][1] + dp[j][2]) \]

E. Sasha and the Happy Tree Cutting

题解：状压 DP + 虚树思想

关键路径数量 \(k \leq 20\) 提醒我们状压

我们对于每条边 \(i\) 求出有哪些关键路径经过 \(i\)，定义其为 \(S_i\)

定义 \(dp[i][mask]\) 代表在前 \(i - 1\) 条边中涂色，使得有哪些关键路径被覆盖的状态为 \(mask\)

那么转移很简单：\(dp[i + 1][mask\ | \ S_i] = \min(dp[i + 1][mask\ | \ S_i], dp[i][mask] + 1)\)

\(dp[i + 1][mask] = min(dp[i + 1][mask], dp[i][mask])\)
但是现在复杂度为 \(O(n2^k)\)，但是观察后我们发现实际上只有 \(O(k)\) 种 \(S_i\)，因为我们对 \(2k\) 个关键点建虚树，虚树上的边数就是 \(S_i\) 不同的边数，即 \(O(k)\)

所以我们直接 \(O(nk)\) 处理 \(S_i\) ，然后排序后去重

然后 \(O(k2^k)\) 状压即可

注意滚动优化空间

F. Sasha and the Wedding Binary Search Tree

题解：隔板法 + 二叉树的遍历

考虑到二叉树的中序遍历是有序的

那么我们就很多线段，并且我们也得到了每条线段中数的范围 \([l, r]\)

那么对于每条线段来说，就转化为：长度为 \(x\) 的线段，其中每个数范围在 \([l, r]\)，要求使得线段中的数不递减的方案数

这是一个经典的组合数问题：我们考虑将线段中每个数看成小球，然后数的范围看成盒子，也就是 \(x\) 个相同的小球，放入 \(r - l + 1\) 个不同的盒子中，允许盒子为空的方案数，显然隔板法，即 \(C_{r - l + x}^{r - l}\)

但是 \(r - l\) 太大了，无法预处理，我们考虑换个形式 \(C_{r - l + x}^{r - l} = C_{r - l + x}^x\)，我们考虑暴力计算，因为 \(\sum x = O(n)\) ，所以可以暴力

最后将每条线段的方案数的乘积作为答案即可