社区讨论
求 hack
P9350[JOI 2023 Final] 宣传 2 / Advertisement 2参与者 4已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo1uj7zn
- 此快照首次捕获于
- 2023/10/23 03:12 2 年前
- 此快照最后确认于
- 2023/11/03 03:44 2 年前
模拟赛写了这样一个做法:
分 大小讨论,可以得到:
X_i+E_i\ge X_j+E_j &X_i< X_j\\
X_i-E_i\le X_j-E_j &X_i>X_j
\end{cases}$$
$X$ 有重复取 $E$ 最大的。
之后以 $X_i+E_i$ 为关键字,对每个 $i$ 求出其右侧第一个大于的位置 $j$,定义 $r_i=j-1$。以 $X_i-E_i$ 为关键字,对每个 $i$ 求出其左侧第一个小于的位置 $k$,定义 $l_i=k+1$。
这样选取 $i$ 可以覆盖到 $[l_i,r_i]$(但这是极大连续段,并非全部可以覆盖到的位置),按右端点排序后贪心覆盖,求覆盖所有位置的最小线段个数。
通过了所有数据,有无人能说明正确性,或给个 hack 数据?
[代码](https://www.luogu.com.cn/paste/wiyye30h)
回复
共 3 条回复,欢迎继续交流。
正在加载回复...