UOJ Round #25

• A. 设计草图
  • 5
  • 20
  • 35
  • 100
• B. 见贤思齐
  • 40
• C. 装配序列
  • 5
  • 15

A. 设计草图

5

$S$ 中只含 ?

任意一个长度为偶数的区间都合法，答案为 $\left \lfloor \frac{n}{2} \right \rfloor \cdot \left \lceil \frac{n}{2} \right \rceil$。

20

$n \le 20$

暴力枚举所有区间及每个 ? 的取值检查是否合法。

时间复杂度 $\mathcal O(2^n n)$。

35

$n \le 5000$

一个区间合法当且仅当以下条件满足：

1. 区间长度为偶数
2. 将所有 ? 替换为 ( 后，把 ( 当成 1，) 当成 $-1$，所有前缀和均大于等于 $0$
3. 将所有 ? 替换为 ) 后，把 ) 当成 1，( 当成 $-1$，所有后缀和均大于等于 $0$

第二个条件相当于对每个 $l$，存在一个 $p_l$ 使得在 $l \le r \le p_l$ 成立。

第三个条件相当于对每个 $r$，存在一个 $q_r$ 使得在 $q_r \le l\le r$ 成立。

在预处理出 $p_i, q_i$ 后，枚举 $l$ 与 $r$ 并 $\mathcal O(1)$ 进行判定。

时间复杂度 $\mathcal O(n^2)$。

100

$n \le 10^6$

上述问题是一个二维数点问题。

时间复杂度 $\mathcal O(n \log n)$。

B. 见贤思齐

40

$n \le 1000$
$q \le 2 \times 10^5$

暴力模拟，将询问离线后按照时间顺序处理。

时间复杂度 $\mathcal O(n d + q)$。

C. 装配序列

5

$x \le 10^6$

直接拿出前 $10^6$ 项然后用你喜欢的方法计算所有前缀的 LIS 即可。

15

$n \le 2 \times 10^3$

可以发现如果 $x \ge n^2$，那么答案为 $n$。

直接拿出前 $n^2$ 项然后用你喜欢的方法计算所有前缀的 LIS 即可。

时间复杂度 $\mathcal O(n^2 \log n + m)$。