CF1929

比赛链接

A

简单题，一眼秒答案为最大值减最小值。

记录

B

简单题，观察到先染第一列第一到第 $n-1$ 行，再染最后一列第一到第 $n-1$ 行，能保证每次都有两个新的对角线被覆盖，如果 $k\leq 2\times n - 2$，输出 $k/2$ 上取整，否则输出 $2 * n - 2 + k - (4 * n - 4)$。

记录

C

不难发现，每次赌钱的策略都是固定的。假设赌了 $x$ 元，如果赢了那么从开始到现在净收益一定要 $>0$，如果没赢，继续赌下一场。如果 $x$ 场都没赢，把所有的都赌上再看一下净收益即可。

记录

D

此题中，设链为一个点一直走若干次父亲所形成的节点集合。

设 $f_{i,0/1}$ 为以 $i$ 为根的子树，子树内 没有/有 一条链，使得这条链上有两个危险节点，转移分当前节点危不危险即可。

记录

E

$k\leq 20$，容易想到状压，先 $O(n\times k)$ 预处理出每个边，选它之后能让哪些路径的集合被覆盖，这是一个二进制状态。然后就可以 $O(n\times 2^k)$ 作动态规划。

接着发现对于所有节点，不同的二进制状态最多只有 $2\times k$ 种，于是去重之后能做到 $O(k\times 2^k)$。

记录

F

首先要用到一个性质，BST 的中序遍历是有序的，然后就把题目转换为了给你一个有序数组，值域为 $[1,C]$ 其中有些值已确定，求符合条件的序列数量。

我们可以将其划分成若干个子问题，即求解长度为 $n$ 的数列，值域为 $[1,C]$，没有位置确定的方案数。

考虑如果是严格有序的数列该怎么办，显然为 $C(C,n)$。

但是现在不是，我们可以将第二项 $+1$，第三项 $+2$，以次类推，这样一定得到一个严格有序的，。于是方案数为 $C(n+C-1,n)$。

记录

总结

B 由于刚开始用小数输出自动四舍五入吃 $n$ 发罚，且浪费时间。

C 不知道答案会很大，没判于是又吃一发。

D 被正难则反害惨了，一开始连正都没想直接想反，浪费巨久。

E F 很水，下次倒开。