如果你90分WA第二个点
查看原帖
如果你90分WA第二个点
552165
ComplexPlanck楼主2022/12/14 20:28

RT,友情提供一组 Hack 数据:

Input:
4 8
7 1
8 2
1 5
3 7
Output:
3 4 3 3 

错误原因:对于跨越 m1m\sim 1 这条分界线的区间,在将断环为链,然后复制成两倍的做法下,要想使得接力完成,可能会出现某个同样跨越这条分界线的区间:成为接力完成(或者说答案最优)的一个必选项。

但是在复制成两倍的情况下,这个区间不可能会在扩增段出现,因为它的右端点会超过 2m2m

因此本题应该断环,然后复制成三倍才行。在实际上,我们不必再扩增出 2m3m2m\sim 3m 段,而只需将跨越分界线的区间也扩增出来(这时扩增的区间的右端点会超过 2m2m

2022/12/14 20:28
加载中...