LGR-222-Div.2 A~C 题解

A

因为删除左右两端的 0 对答案产生不了贡献,所以我们直接忽略。
接着我们计算出初始时有多少个块。
然后求出相邻两个块之间有多少个 0,存入数组 cnt 中。接着把 cnt 从小到大排序。贪心地选择 0 尽量少的一块,求出 k 能够表示成多少个 cnt 数组中的数之和。
代码细节较多,注意特判全是 0 的情况。

B

简单结论题。
分情况讨论:

  • 若两个矩形 a,b 不相交,则它们之间的距离为 \max\{a_{x0}-b_{x1},b_{x0}-a_{x1},a_{y0}-b_{y1},b_{y1}-a_{y0}\}
  • 若两个矩形 a,b 相交,则它们之间的距离为 0

这两个情况是可以合并的,若情况二成立,则用情况一的式子算出的结果为负数。所以对于两个矩形 a,b,它们之间的距离为 \max\{0,a_{x0}-b_{x1},b_{x0}-a_{x1},a_{y0}-b_{y1},b_{y0}-a_{y1}\}
现在我们要将这个式子的结果最大化,显然仅需取最大的 x0,y0,最小的 x1,y1 即可。

C

n 为偶数且 m 为奇数,无解。
否则若 m 为偶数,把 n 分成两半,两边各取 \frac{m}{2} 个数,刚好为平均数,重复操作直到所有数均相等为指。
否则 m 为奇数,需多选一个中位数。
注意特判 m=1n>1

1 个赞