设 $c$ 是不在 $b$ 中的数组成的序列，将 $c$ 排序，然后将 $b$ 和 $c$ 归并即可。时间复杂度：$O(n)$
枚举每个前缀，考虑维护两个set，一个是在前缀里的数的集合，一个是不在前缀里的数的集合。每次交换肯定是用前缀里最小的数去换不在前缀里的最大的数，模拟一下即可，时间复杂度：$O(nk\log{n})$
考虑传统的筛法，枚举$10^6$以内的质因子，去筛这些数，例如枚举到了质数$x$，只要枚举区间$[l,r]$内$x$的倍数即可，时间复杂度是$O((r-l)\log{l})$的
考虑在第$i$步时$x$改变的概率，那么$p[i]$一定是$p[1..i]$中的最大值，这个概率是$\frac{1}{i}$。
所以答案是$n!*\sum_{i=1}^{n}\frac{1}{i}$
时间复杂度：$O(n)$
有个疑问，B题按照你的思路写的，但是有个小细节搞不明白，就是下面注释的那行代码，为什么不加max[i+1][j]>min[i][j]判断就会WA，我感觉不需要加也能AC。 是不是OJ有啥Corner case？多谢
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt(), k=sc.nextInt();
long[]a=new long[n];
for(int i=0;i<n;i++)a[i]=sc.nextLong();
long[][]min=new long[n][k], max=new long[n][k];
for(int i=0;i<n;i++) Arrays.fill(min[i], Long.MAX_VALUE);
for(int i=0;i<n;i++) Arrays.fill(max[i], Long.MIN_VALUE);
PriorityQueue<Long>pq=new PriorityQueue<Long>();
for(int i=0;i<n;i++) {
pq.add(a[i]);
List<Long>tmp=new ArrayList<Long>();
for(int j=0;j<Math.min(i+1, k);j++) {
long t = pq.remove();
tmp.add(t);
min[i][j]=((j==0?0:min[i][j-1])+t);
}
for(long t:tmp) pq.add(t);
}
PriorityQueue<Long>pq2=new PriorityQueue<Long>();
for(int i=n-1;i>=0;i--) {
pq2.add(-a[i]);
List<Long>tmp=new ArrayList<Long>();
for(int j=0;j<Math.min(n-i, k);j++) {
long t = pq2.remove();
tmp.add(t);
max[i][j]=((j==0?0:max[i][j-1])-t);
}
for(long t:tmp) pq2.add(t);
}
long res = Long.MIN_VALUE, sum = 0;
for(int i=0;i<n;i++) {
sum += a[i];
res = Math.max(res, sum);
for(int j=0;j<Math.min(i+1, k);j++) {
if(i+1<n && max[i+1][j]>min[i][j]) // **为什么这里需要额外判断一下max[i+1][j]>min[i][j]才能AC**
res = Math.max(res, sum-min[i][j]+max[i+1][j]);
}
}
System.out.println(Math.max(res, 0));
}
本次比赛个人解答，还算详细