伸展
首先答案是可以二分的，当 达到比所有的相邻 的差值都要大的时候那么 绝对是满足条件的，而如果一个 满足条件那么 也是满足的，因此可以二分答案 值。
考虑如何判断 是否满足条件。令 表示为当前线段的左端点，那么很显然最开始时 是最优的。接下来枚举 ，判断能否伸到当前的点，即判断 ，如果不满足可以直接返回不满足条件；否则令 ，也就是往右铺 的长度，但是要保证下一个点仍然可以被覆盖。
时间复杂度 ，可以通过 分。由于有多组询问，可以尝试整体二分，但是由于我整体二分的 check 没有写好导致复杂度和正常二分是一样的。
因此我们需要找出规律。把上一个 的值带入进去，拆开 ，就可以得到 个不等式：
对于第 个不等式，它描述了从 开始能否走到 。多个数的 值大于等于一个值，那么这每一个数都要大于等于那个数，以第三个式子举例
准确地来说，对于从 开始走的情况，如果最终要走到 ，它的必要条件是对于 ，有 ，由于 是整数解方程得到 。因此 最终的取值是 。
当所有必要条件都满足（ 到 能走通， 到 能走通，……， 到 能走通）时， 到 才是真正可以走通的，因此 要是所有 到 要求的 值的最小值中的最大值。也就是最终 到 的答案等于
做两遍后、前缀 即可，也可以一遍搞完。时间复杂度 。
#include <iostream>
#include <cmath>
using namespace std;
using LL = long long;
const LL kMaxN = 5005;
LL a[kMaxN], ans[kMaxN][kMaxN], n, q;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
}
for (LL r = n; r >= 1; r--) {
for (LL l = r - 1; l >= 1; l--) {
ans[l][r] = max(ans[l + 1][r], (a[r] - a[l] + r - l) / (r - l + 1));
}
}
for (LL l = 1; l <= n; l++) {
for (LL r = l + 1; r <= n; r++) {
ans[l][r] = max(ans[l][r], ans[l][r - 1]);
}
}
for (LL l, r; q; q--) {
cin >> l >> r;
cout << ans[l][r] << '\n';
}
return 0;
}内鬼
我写的暴力。首先枚举删除的两个点，然后枚举相交的弦并累加答案。唯一有难点的是如何判断两个弦是否相交，最简单的道理是拿出其中一个弦 （，不满足就交换），另外一个弦 其中一个属于 ，另外一个不属于 。时间复杂度 。成功获得 分。
零一
我还是写的暴力。暴力枚举左端点然后往右找右端点，加上奇妙小剪枝，时间复杂度 但是可以通过 分。
反转
我分类写的暴力。对于 的数据，猜测答案不会太大所以进行迭代加深搜索；对于 但是答案不超过 的，先特判答案为 然后在枚举操作的点是什么。用并查集判断连通性。成功获得 分。
总结
总分：。
这场比赛相对于之前还是比较良好的，虽然在第一题坐牢了三个小时但是最终还是写出来了，后面的暴力也很稳，暴力本身没有挂掉，我也没有漏掉我不会会写的子测试点。只是水平还是有限了，第二题不会容斥，无法追求更高的分数，等会讲题的时候再看看。