社区讨论

求 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 年前
查看原帖
模拟赛写了这样一个做法:
Xi,XjX_i,X_j 大小讨论,可以得到:
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 条回复,欢迎继续交流。

正在加载回复...