社区讨论
提供本题翻译
AT_agc055_e [AGC055E] Set Merging参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo2hi642
- 此快照首次捕获于
- 2023/10/23 13:55 2 年前
- 此快照最后确认于
- 2023/10/23 13:55 2 年前
RT
题目描述
给出 个集合 ,起初这些集合满足 。你被允许执行如下操作任意次:
选择任意一个满足 的整数 ,首先计算 ,然后将 和 均置为 (即选择两个相邻的集合,把它们均变为这两个集合的并集)。
请输出至少需要多少次操作(可能是 次)才能使得对于所有 均有 。如果无论如何操作都无法实现,输出 。
输入格式
第一行一个整数 ,代表集合数量。
接下来 行,每行一对整数 ,表示第 个集合最终应为 。
输出格式
如果能够满足要求,输出一行一个整数 ,表示所需的最少步数。否则,输出 。
数据范围
对于 的数据,满足 ,。
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 条回复,欢迎继续交流。
正在加载回复...