警示后人
查看原帖
警示后人
982540
123456a01楼主2024/11/19 00:38

如果你用的是这篇题解的思路(必要条件缩小范围)

这篇题解的文字部分与代码严重不符。 题解中描述如下:

至于解决是否存在 ixi\ge x,使得 ii 为合法点,发扬人类智慧,考虑当 C=iC=i 足够大时,限制 11 必然满足,而其它限制都是 CC 较小才容易满足,所以直接去掉限制 11 后,按照 C=xC=x 跑一遍差分约束即可!

第一,题解代码是在去掉 限制 22 后用差分约束+二分求出了一个所谓的“左端点 LL ”.

第二,经上述操作求出的 LL 不一定 就是答案区间左端点(记为 LL' ),而只能保证 L<=LL<=L' .
加入限制2后再次二分求出右端点 RR , 由于此时所有限制都已加入,显然 RR 即为答案区间右端点。
因此,根据该篇题解文字叙述,我们得到了区间 [L,R][L,R] ,而答案区间包含于 [L,R][L,R] , 还需要在区间 [L,R][L,R] 内进行第三次二分求出 LL' . 该篇题解在文字叙述中略去了这一操作。

尽管题解中写道

代码如下,不过具体实现和上述思路有略微区别:

但我认为这已经不是“有略微区别”了。

2024/11/19 00:38
加载中...