[CF] 1040 Div 2 部分题解

博客又是好久没更了。。。

挖坑不填。。。

又挖了个新坑。。。

---

题面

题解

---

A. Submission is All You Need

给定非负整数可重集 $S$，重复任意次操作：选取子集 $S'$，将 $\text{sum}(S')$ 或 $\text{mex}(S')$ 添加到分数，删去 $S'$。求最大分数。

只有当 $S'=\lbrace 0\rbrace$ 时，$\text{mex}(S')$ 比 $\text{sum}(S')$ 更优。

故 $ans=\sum S+\text{Count(0)}$

B. Pathless

给定数组 $\lbrace a\rbrace, a_i\in\lbrace 0,1,2\rbrace$（$\lbrace a\rbrace$ 中包含至少一个 $0$，一个 $1$ 和一个 $2$） 和整数 $s$，是否可以通过重排 $\lbrace a\rbrace$ 使得不存在一条从 $1$ 到 $n$ 的路径（每一步均可以向左或向右移动一个单位，但起点终点确定），若可以，输出任意满足条件的 $\lbrace a\rbrace$，不满足输出 $-1$。

分类讨论：

• $\sum a_i > s$：$\lbrace a\rbrace$

• $\sum a_i = s$：$-1$

• $\sum a_i < s$：

  • $s - \sum a_i = 1$：$\lbrace 0,\dots,0,2,\dots,2,1,\dots,1\rbrace$

  • $s - \sum a_i > 1$：$-1$

    • 至少有一个 $0$ 与 $1$ 相邻：显然可以；

    • $0$ 只与 $2$ 相邻：则至少有一个 $1$ 与 $2$ 相邻，可以在 $\sum a_i$ 的基础上加上任意个 $2$ 和 $3$ 构成 $s$。

C. Double Perspective

题面太长了不写了。。

$g(S)$ 一定为 $0$

Sol 1

用并查集维护，每次选不会构成环的加进答案。

Sol 2

被其他线段完全包起来的线段不选。

D. Stay or Mirror

给定一个排列 $p$，创建一个数组 $a,a_i\in\lbrace p_i, 2n-p_i\rbrace$，求最小的相邻元素交换次数使 $a$ 由大到小有序。复杂度要求：$O(n^2)$。

对于 $p_i=1$：

• Stay：贡献为 $n-i$；

• Mirror：贡献为 $i-1$；

删去 $1$，重复此过程可得对于第 $i$ 个元素：

• $Stay_i=\sum_{j=i+1}^n 1\ \text{if } p_j>p_i$；

• $Mirror_i=\sum_{j=1}^{i-1} 1\ \text{if } p_j>p_i$；

$ans=\sum_{i=1}^n\min(Stay_i, Mirror_i)$

E1. Interactive RBS (Easy Version)

$f(t)$ 是 $t$ 中非空正则括号字串个数，通过 $f(t)$ 找到长为 $n$ 括号序列 $s$，$n\leq 1000,Q\leq 550$。

首先寻找 $i,j$ 使得 $s_i=$ (，$s_j=$ )：

• $f(s)\not=0$：

  二分查找使得 $f(s_1s_2\dots s_i)\not=0$ 的最小的右端点，则有 $s_{i-1}=$ (，$s_i=$ )；

• $f(s)=0$：

  由题意 $s_n=$ (，$s_1=$ )；

构造 $t={s}_i\texttt{)(}{s}_j\texttt{()}$，可根据 $f(t)$ 的结果知道 $s_i$ 和 $s_j$ 的值。