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=1 且 n>1。