CF2030 题解

因为 cf 炸了所以没办法提供代码，抱歉喵。

A

给定序列，定义 $mn_i=\min_{j\le i} a_j,mx_i=\max_{j\le i}a_j$。  
重排该序列，最大化 $\sum_{i=1}^n mx_i-mn_i$。  
$n\le 10^5$  

正解

手玩出一个构造，把最大和最小值放在前两个位置，这样的价值是 \((n-1)\times(mx-mn)\)。
由于 \(mx_{1}=mn_{1}\)，所以该方案卡到了上界，故正确。

B

对于一个 01 串 t：  
定义 $f(t)$ 表示 t 的全 0 非空子序列个数，$g(t)$ 表示 t 的非全 0 非空子序列个数。  
构造长为 $n$ 的串 t，最小化 $\lvert f(t)-g(t)\rvert$。  
$n\le 10^5$

正解

容易发现 \(f(t),g(t)\) 可以只用 0 的个数（记作 \(x\)) 表示。
则 \(f(t)=2^{x}-1,g(t)=2^{n}-2^{x},g(t)-f(t)=1+2^{n}-2^{x+1}\)。
发现构造 \(n-1\) 个 0，1 个 1 的串即可，想一下发现没有特判。

C

给定一个 01 序列，A 和 B 可以在这 n-1 个位置上填 and 和 or 操作（and 优先级高于 or）。  
若最后运算结果为 1，A 胜，否则 B 胜。  
问先手是否必胜。  
$n\le 10^5$

正解

贪心地去博弈，A 必定只使用或操作，B 必定只使用与操作。
博弈相当于对序列进行分段，若每个段与起来都是 0 则 B 胜。
Conclusion：若存在 11 的情况先手必胜，或者存在序列最左或最右的 1 也必胜，否则必败。
Prove：
充分性显然，第二种情况显然，第一种情况形如一个活一（谁家五子棋）。
必要性也简单，考虑一下后发现 B 只需每次封锁 A 一段的 1 即可。

D

给定排列 p 和 LR 串 s。  
每次操作可以任选一个位置 x，若 $s_x$ 为 L，则交换 $p_{i-1},p_i$，否则交换 $p_i,p_{i+1}$。  
若能通过若干次操作使得排列升序，则合法。  
每次单点反转一个 s，问是否有解。  
$n\le 10^5$

正解

操作非常强，形如冒泡排序即可排序。
但若是出现 \(s_{i}=L,s_{i+1}=R\) 的情况，那么左右两侧不连通，只有左右两侧值域不交才合法。
于是预处理每个左右值域不交的间隔，每次维护不连通的间隔位置即可。

E

在多重集 a 上定义 $f(a)$ 表示：  
把 a 分为若干多重集，最大化 $\sum mex(s_i)$ 的值。  
对于给定的多重集，计算其所有非空子集的 $f(s)$ 之和。  
$n\le 10^5$

正解

对一个确定的集合来说，权值显然是 \(\sum\limits_{i\geq 0} \min\limits_{j\leq i}cnt_{j}\)。
于是考虑从值域上从小到大选择去 dp。
设 \(f_{i,j}\) 表示考虑了前 \(i\) 种值，最小的 \(cnt\) 是 \(j\) 的方案数，对应的设出 \(g_{i,j}\) 表示此时的权值和，这样设状态总数是 \(\sum\limits cnt =\mathcal O(n)\) 的。
转移是简单的，只需考虑枚举当前该值选择是大于 \(j\) 还是等于 \(j\)，贡献是一个组合数，后缀和优化一下就可以做到 \(\mathcal O(1)\) 了。
值得一题的是权值和的转移有 \(g(AB)=f(A)g(B)+g(A)f(B)\)，本质上是全期望公式。

F

称一个序列合法，当且仅当它能通过若干次以下操作删空：  
选择一个数值的连续段，删除它，每种数值在这个流程中至多删除一次。  
给定序列 a，每次询问它的一个连续子序列是否合法。  
$n,q\le 10^5$

正解

能提供一些关于区间交和序列顺序干扰问题的启发性。

Conclusion 1：
定义一个区间为一个值和它的等值后继。
那么合法当且仅当不存在两个不同值的区间有交。
Prove：充分必要分讨显然。
Conclusion 2：合法区间的子区间合法。

于是考虑双指针和扫描线。
\(l\) 自大而小枚举，若当前区间不合法则不断减小 \(r\)。
发现此时交叉有好的性质，只需判断 \(nxt_{l}\) 是否被一个区间覆盖，线段树即可。

细节是注意特判同种区间之间的交是不算的。

G

待补充。