Codeforces Round 926 (Div. 2) 题解

A. Sasha and the Beautiful Array

显然答案是最大值和最小值之差。

B. Sasha and the Drawing

抽象结论题，如果只填充第一排和最后一排，在前期可以做到一段连续的 $2$ 的贡献。答案当 $k=4n-2$ 时为 $2n$ 否则为 $\lceil\frac{k+1}{2}\rceil$。

C. Sasha and the Casino

抽象题，注意到若可以在当前基础上增加，则一定可以达到 $a$，否则一定不行。考虑系统的最优决策，对于每一次下注若赢得的价值不超过沉没成本，则一定会赢得但刷新了连续长度且不优。所以记沉没成本为 $s$，每一次的下注都是 $\lfloor\frac{s}{k-1}\rfloor +1$。

D. Sasha and a Walk in the City

小清新树形 DP。考虑处理完 $u$ 为根的子树时计算点集 $lca$ 为 $u$ 的答案，并记 $f_u$ 为若 $fa_u$ 属于点集，满足不构成三点共线的，$u$ 的子树内的点集数量。对于 $u$ 是否在点集中分开计算，若 $u$ 不在点集中，贡献为 $f_u - s$，其中 $s$ 为在子树内重复计算的量，若 $u$ 在点集中，则贡献恰好是 $s$。综上答案为 $\sum_u f_u$。

E. Sasha and the Happy Tree Cutting

注意到 $k\le 20$。不妨对于点对 $(u_i,v_i)$，将 $(u_i,v_i)$ 路径上的边染色 $i$。染色后本质不同的边相当于虚树上剩下的边，级别是 $O(k)$ 可以接受，跑一遍状压 DP，求出最小的个数使得覆盖全集即可。

F. Sasha and the Wedding Binary Search Tree

非常水 F 题，使我倒开。注意到若 $-1$ 构成一条链可以合并考虑，使我想到 $splay$，然后发现直接中序遍历拍扁成单调（除了 $-1$）序列即可变成一个简单组合题，其中大组合数按照定义求即可。