A

题意:给定一个长度为n的数组,可以做K次合并(合并后删除其中一个元素),要使得经过这K次操作后中位数最小。输出这个中位数。
思路:操作只会让元素变大,所以最小的这个中位数就是排序后的第图片说明 个数,特判掉K=n-1即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48618026

B

题意:给定长度为n的排列,求有多少对区间满足第K小数恰为X。
思路:现在假设区间[L,R]是满足条件的最小区间,现在想要扩大区间,但是又不能改变新区间满足第K小数恰为X,所以只有a[L-1]>X 或者 a[R+1]>X区间端点才能向左侧或右侧移动。所以我们可以从X所在的位置P开始,统计左右两侧各有多少个数小于X。然后做一个简单计数即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48649113

E

题意:给你长度为n的数组,每秒可以做无数次合并(合并后使其中一个变为0,且X秒后又会恢复为最后的大小),问M秒后这个数组的元素最大能达到多少。
思路:因为0元素是恢复成最后的大小,使得我们知道每次数组中0元素个数不为n-1的时刻,都要尽可能的最大化所有元素。也就是最大的元素被加最多的次数。设a是从小到大排好序的数组。在第一秒,可以进行以下操作:a[n-1]+=a[n],a[n-2]+=a[n-1],如此一来就满足了最大元素倍加最多的次数的条件,接着翻转数组重复操作就行。
翻转数组重复操作这个过程又恰好可以看成一个如下图的矩阵。矩阵
然后整个题就变成矩阵快速幂的裸题了。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48648778

写在最后:
我对这次我写的题意很满意啊!只要把题意清晰的讲给队友,队友就能提交一发AC代码(/滑稽)