社区讨论

提供本题翻译

AT_agc055_e [AGC055E] Set Merging参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo2hi642
此快照首次捕获于
2023/10/23 13:55
2 年前
此快照最后确认于
2023/10/23 13:55
2 年前
查看原帖
RT

题目描述

给出 nn 个集合 S1,S2,...,SnS_1,S_2,...,S_n,起初这些集合满足 Si={i}S_i=\{i\}。你被允许执行如下操作任意次:
选择任意一个满足 1i<n1 \leqslant i < n 的整数 ii,首先计算 U=SiSi+1U=S_i \cup S_{i+1},然后将 SiS_iSi+1S_{i+1} 均置为 UU(即选择两个相邻的集合,把它们均变为这两个集合的并集)。
请输出至少需要多少次操作(可能是 00 次)才能使得对于所有 ii 均有 Si={Li,Li+1,...,Ri1,Ri}S_i=\{L_i,L_i+1,...,R_i-1,R_i\}。如果无论如何操作都无法实现,输出 1-1

输入格式

第一行一个整数 nn,代表集合数量。
接下来 nn 行,每行一对整数 Li,RiL_i,R_i,表示第 ii 个集合最终应为 {Li,Li+1,...,Ri1,Ri}\{L_i,L_i+1,...,R_i-1,R_i\}

输出格式

如果能够满足要求,输出一行一个整数 AnsAns,表示所需的最少步数。否则,输出 1-1

数据范围

对于 100%100\% 的数据,满足 1n5×1051 \leqslant n \leqslant 5 \times 10^51LiRin1 \leqslant L_i \leqslant R_i \leqslant n
Markdown:
MD
### 题目描述

给出 $n$ 个集合 $S_1,S_2,...,S_n$,起初这些集合满足 $S_i=\{i\}$。你被允许执行如下操作任意次:

选择任意一个满足 $1 \leqslant i < n$ 的整数 $i$,首先计算 $U=S_i \cup S_{i+1}$,然后将 $S_i$ 和 $S_{i+1}$ 均置为 $U$(即选择两个相邻的集合,把它们均变为这两个集合的并集)。

请输出至少需要多少次操作(可能是 $0$ 次)才能使得对于所有 $i$ 均有 $S_i=\{L_i,L_i+1,...,R_i-1,R_i\}$。如果无论如何操作都无法实现,输出 $-1$。

### 输入格式

第一行一个整数 $n$,代表集合数量。

接下来 $n$ 行,每行一对整数 $L_i,R_i$,表示第 $i$ 个集合最终应为 $\{L_i,L_i+1,...,R_i-1,R_i\}$。

### 输出格式

如果能够满足要求,输出一行一个整数 $Ans$,表示所需的最少步数。否则,输出 $-1$。

### 数据范围

对于 $100\%$ 的数据,满足 $1 \leqslant n \leqslant 5 \times 10^5$,$1 \leqslant L_i \leqslant R_i \leqslant n$。

回复

2 条回复,欢迎继续交流。

正在加载回复...