D~F Java题解，代码已去除冗余~~~

D mex

首先需要特判：数组本来就全部相同，无需操作；数组最小值是不是0，此时mex恒定为0，操作无效，返回-1,；；下边考虑普通情况，数组去重，初始的时候一定是一段段连续的自然数，每次减掉的mex是第一段最后一个数大1的数，可以将最小的一段一次性“删除”，导致mex变为1，可以将第二段减至最小值为0，，此时原先的第二段变为第一段，重复上述操作即可，时间复杂度O(nlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long a[]=new long[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextLong();
        }
        Arrays.sort(a);
        if(a[0]==a[n-1]){
            System.out.println(0);
        }
        else if(a[0]!=0){
            System.out.println(-1);
        }
        else{
            long ans=1;
            for(int i=1;i<n;i++){
                ans+=Math.max(0,a[i]-a[i-1]-1);
            }
            System.out.println(ans);
        }
    }
}

E 可划分数组

考虑区间动态规划，定义ans[i]表示前i项以a[i]为末尾的最大分割，那么最后一段的内每个数字，需要保证每一个数字都至少在区间内与左边和右边最近的不不互质的数字中的一个，因此需要预处理出每个位置左边和右边最近的非互质位置，在向前遍历左端点的时候需要用范围可用的左端点金星更新，时间复杂度O(n^2logC),C==1e9

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),a[]=new int[n+5],l[]=new int[n+5],r[]=new int[n+5],ans[]=new int[n+5];
        Arrays.fill(l,-1);
        Arrays.fill(r,n+5);
        Arrays.fill(ans,-n-5);
        ans[0]=0;
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
            for(int j=i-1;j>0;j--){
                if(gcd(a[i],a[j])>1){
                    l[i]=j;
                    break;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(gcd(a[i],a[j])>1){
                    r[i]=j;
                    break;
                }
            }
        }
        for(int i=1;i<=n;i++){
            int low=l[i];
            for(int j=i-1;j>0;j--){
                if(i<r[j]){
                    low=Math.min(low,l[j]);
                }
                if(low>=j){
                    ans[i]=Math.max(ans[i],1+ans[j-1]);
                }
            }
        }
        System.out.println(Math.max(-1,ans[n]));
    }
    static int gcd(int a,int b){
        return a<b?gcd(b,a):b==0?a:gcd(a%b,b);
    }
}

F 最小差值

前缀和+划分区间+推一次函数表达式，时间复杂度O((n+m)log(n+m))

import java.util.*;
public class Main{
    static long inf=(int)2e9;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        long a[]=new long[n+1],b[]=new long[m+1],ans=-inf,min=(long)8e18,cur=ans;
        List<Long> list=new ArrayList<>();
        list.add(inf);
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
            list.add(a[i]);
        }
        for(int i=1;i<=m;i++){
            b[i]=sc.nextInt();
            list.add(b[i]);
        }
        Arrays.sort(a,1,n+1);
        Arrays.sort(b,1,m+1);
        for(int i=1;i<=n;i++){
            a[i]+=a[i-1];
        }
        for(int i=1;i<=m;i++){
            b[i]+=b[i-1];
        }
        Collections.sort(list);
        for(long p:list){
            if(p==cur){
                continue;
            }
            long p1[]=find(cur,a),p2[]=find(cur,b);
            if(p1[0]-p2[0]==0){
                long q=Math.abs(p1[1]-p2[1]);
                if(q<min){
                    min=q;
                    ans=cur;
                }
            }
            else{
                List<Long> candidates=new ArrayList<>();
                candidates.add(cur);
                candidates.add(p);
                long zero=(p2[1]-p1[1])/(p1[0]-p2[0]);
                for(int i=-1;i<=1;i++){
                    if(zero+i>=cur&&zero+i<=p){
                        candidates.add(zero+i);
                    }
                }
                Collections.sort(candidates);
                for(long w:candidates){
                    long q=Math.abs((p1[0]-p2[0])*w+p1[1]-p2[1]);
                    if(q<min){
                        min=q;
                        ans=w;
                    }
                }
            }
            cur=p;
        }
        System.out.println(ans);
    }
    static long[] find(long p,long a[]){
        //寻找出数组中不大于p的最大位置
        int n=a.length-1;
        if(p<a[1]){
            return new long[]{-n,a[n]};
        }
        int l=0,r=n-1;
        while(l<r){
            int mid=(l+r)>>1;
            if(p>=a[mid+1]-a[mid]){
                l=mid;
            }
            else{
                r=mid-1;
            }
            if(l==r-1){
                if(p>=a[r+1]-a[r]){
                    l=r;
                }
                break;
            }
        }
        return new long[]{l*2+2-n,a[n]-a[l+1]*2};
    }
}