9月杂题选做

标签：考虑 le color times cases 杂题 bigstar

上回说到：2022.8

关于难度

\(\color{gray}\bigstar\) 可以秒杀的题。

\(\color{green}\bigstar\) 思考一会儿后可以秒的题。

\(\color{blue}\bigstar\) 需要较长时间思考的题。

\(\color{Gold}\bigstar\) 看题解、稍加指点就会做的题。

\(\color{red}\bigstar\) 看题解后需要较长时间消化，甚至现在都没有完全理解的题。

---

ABC266Ex *2865 \(\color{blue}\bigstar\)

有 \(n\) 个点，第 \(i\) 个点在 \((x_i,y_i)\) 在第 \(t_i\) 时刻会出现 \(a_i\) 个球然后下一个时刻消失，现在有一个人在 \((0,0)\)，每个时刻可以向上左右走，但不可以向下走，求最多拿几个球。

\(n\le 10^5\)。

不是很难的题。

考虑设 \(f_i\) 表示最后一个拿的球是 \(i\) ，最多可以拿多少个球，那么考虑 \(i\) 可以向 \(j\) 转移的条件是什么，可以列一下：

\[\begin{cases}y_i\le y_j\\t_i\le t_j\\ |x_i-x_j|+y_j-y_i\le t_j-t_i \end{cases} \]

然后考虑如果 \(t_i>t_j\)，第三个等式右边 \(<0\)，显然不合法，因此这个条件可以扔掉。

然后考虑绝对值的意义，就是 \(|a-b|=\max(a-b,b-a)\)，所以可以直接拆成两个式子，然后可以得到：

\[\begin{cases}y_i\le y_j\\ x_i-x_j+y_j-y_i\le t_j-t_i\\ x_j-x_i+y_j-y_i\le t_j-t_i \end{cases} \]

移项一下，就可以发现本质上是一个关于 \(i,j\) 的三维偏序，因此考虑 cdq。

直接先做左边，然后考虑左边转移右边的，再做右边的。注意转移完了序列需要回复到开始状态。

code

---

ARC051D *2779 \(\color{blue}\bigstar\)

有一个 \(n\times m\) 的矩阵，\((i,j)\) 上写有数字 \(a_i+b_j\)，\(Q\) 次询问，每次询问左上角一个子矩形，求这个子矩形的子矩形内数和的最大值。

\(n,m,Q\le 2000\)。

考虑相当于选 \(a,b\) 各一个区间，对于同样的区间长度显然选和最大的，假设 \(f_i,g_i\) 分别表示行，列上连续 \(i\) 个数的最大值，这个可以 \(O(n^2)\) 预处理，然后考虑如果选了 \(f_i,g_j\)，答案就是 \(f_i\times j+g_j\times i\)，咋求最大值呢。

这个东西不是很好搞，考虑整体除以 \(i\)，变成 \(\frac{f_i}{i}\times j+g_j\)，这是一个关于 \(\frac{f_i}{i}\) 的一次函数，可以直接李超树维护，也可以斜率排序后直接整体二分做。

总复杂度 \(O(n^2\log n)\)。

code

---

标签：考虑,le,color,times,cases,杂题,bigstar
From： https://www.cnblogs.com/houzhiyuan/p/16667191.html