求 hack
查看原帖
求 hack
321177
SoyTony楼主2023/8/15 06:34

模拟赛写了这样一个做法:

分 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)
2023/8/15 06:34
加载中...