联合省选 2021 A 卷题解

首先一定是翻一个前缀和一个后缀。

然后是答案具有单调性，于是二分答案 (k)，考虑是否存在方案满足极差 (le k)。

考虑双指针，递增地枚举最大值 (v)，维护区间 ([l,r]) 使 (v-k le a_lle a_rle v)，然后检查两边的 (b) 是否也在 ([v-k,v]) 内。

若存在一个区间使 (b) 合法那么这个 (k) 可行。复杂度 (O(nlog n))，线性做法先咕了。

假如对 (a) 的大小没有限制，那么直接钦定最下最右侧为 (0)，推上去就行。

然后尝试调整，发现如果对一整行进行 (+x,-x,+x,-x, cdots) 的操作，(b) 值不变。

对列同理，但是我们改变一下，先 (-) 后 (+)，每个格子的修改就是 (a-b) 的形式了。

然后就是一个差分约束系统，(O(n+m)) 个变量，(O(nm)) 个约束，跑一遍 spfa 是 (O((n+m)nm)) 的。

考虑一个复杂度比较高的 dp：(f(S,i, j, k)) 表示已经滚过 (S) 集合的队伍，上一个为 (i)，当前一共用掉 (j) 个题，上一次用了 (k) 题。

然后尝试去掉 (k)。先考虑一个 (O(n!cdot n)) 的暴力，发现下一次只要令 (b_{p_{i+1}}=max(a_{p_{i+1}}-a_{p_i}, [p_{i+1}>p_i])) 就行。

令 (Delta_{i+1}=max(a_{p_{i+1}}-a_{p_i}, [p_{i+1}>p_i]))，那 (b) 就是 (Delta) 的前缀和，(Delta_i) 产生了 (n-i) 次贡献。

于是换枚举 (b) 为枚举 (Delta)，那 (k) 那一维自然就省掉了。最后复杂度是 (O(2^ncdot n^2m))。

gugugu

联合省选 2021 A 卷 题解