CF1930 think-cell Round 1 题解

A. Maximise The Score

显然每次操作选择最大值和次大值。

B. Permutation Printing

不妨加强使得不存在 $i,j$ 满足 $p_i\lt p_j,p_{i+1}\lt p_{j+1}$，容易构造出形如 $1,6,2,5,3,4$ 的答案。

C. Lexicographically Largest

考虑从右往左删，如果当前即将加入到集合的数已经存在，则一定存在一种办法，将集合中这个数减一。所以将 $a_i+i$ 降序排序后，若 $a_i\gt a_{i-1}$ 则将 $a_i$ 调整为 $a_{i-1}-1$。

D1. Sum over all Substrings (Easy Version)

考虑如何对一个子串构造答案。注意答案不小于 1 的个数的一半下取整，考虑如何使一个构造串的一个 1 物尽其用。从左到右扫描，若为 1 则进行一次操作，操作为将答案加一并将后两个位置改为 0。

D2. Sum over all Substrings (Hard Version)

不妨考虑一个位置在哪些子串可以贡献答案。可以状压 DP $f_{i,msk}$ 表示考虑到第 $i$ 个位置，$msk$ 中的位置进行了 D1 所述的操作。只需要保留后两个位置即可 $f_{i,0/1/2}$

E. 2..3...4.... Wonderful! Wonderful!

非常好题目，对于一个 $k$ 可能删去的数量 $x$ 满足 $2k\mid x$，考虑枚举 $k$ 后枚举 $x$，这个部分是调和级数。我们考虑在 $\binom{n}{x}$ 中组合中不可能成立的部分。对于 $k=1$，这个部分是一段连续的位置，对于 $k=2$，是左右各一个点，中间一串连续的位置。推广得到 $\binom{n-x+2k-1}{2k-1}$。

F. Maximize the Difference

考虑贡献答案的点对是 $(x,y)$ 则答案一个数位为 $1$ 当且仅当 $x$ 的这一位是 $0$，$y$ 这一位是 $1$，将 $x$ 翻转，则相当于求两个集合中各选一个数，按位与的最大值。既然集合是增量构造的，那么我们只需要考虑插入进的这个数和原先集合的贡献，可以在插入时搜索子集，并在查询时进行类似于线性基的贪心。