题解 | 牛客周赛 Round 110 CDEF Java题解

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

C 小苯的麦克斯

对于一个序列来说，如果最大值确定，那么数列越短mex就不会增大，因此只需检查长度为2的子数组即可，时间复杂度O(Tn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int t=sc.nextInt();t!=0;t--){
            int n=sc.nextInt(),pre=0,ans=-1;
            for(int i=0;i<n;i++){
                int a=sc.nextInt();
                ans=Math.max(ans,find(pre,a));
                pre=a;
            }
            System.out.println(ans);
        }
    }
    static int find(int a,int b){
        return a>b?find(b,a):a==b?(a==0?-1:a):a==0?(b==1?-1:b-1):b;
    }
}

D 小苯的平衡序列

按照顺序从小到大排列并计算前缀和，枚举删除的位置分段计算即可，时间复杂度O(Tnlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int t=sc.nextInt();t!=0;t--){
            int n=sc.nextInt();
            long a[]=new long[n+1],ans=(long)1e18;
            for(int i=0;i<n;i++){
                a[i]=sc.nextInt();
            }
            Arrays.sort(a);
            for(int i=1;i<=n;i++){
                a[i]+=a[i-1];
            }
            for(int i=1;i<=n;i++){
                ans=Math.min(ans,i*2>=n+1?a[n]-a[i]+a[i-1]-a[n/2-1]-a[n/2]+(n/2L*2-n)*(a[n/2]-a[n/2-1]):a[n]-a[n/2-i+2]*2+a[i]-a[i-1]+((n/2L-i+2)*2-1-n)*(a[n/2-i+2]-a[n/2-i+1]));
            }
            System.out.println(ans);
        }
    }
}

其实类似于方差的计算，想要是的目标最小，只需让删除最小的或者最大的即可（不知如何证明），时间复杂度O(Tnlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int t=sc.nextInt();t!=0;t--){
            int n=sc.nextInt(),a[]=new int[n];
            for(int i=0;i<n;i++){
                a[i]=sc.nextInt();
            }
            Arrays.sort(a);
            System.out.println(Math.min(find(a,0,n-2),find(a,1,n-1)));
        }
    }
    static long find(int a[],int l,int r){
        long ans=0;
        for(int i=l;i<=r;i++){
            ans+=Math.abs(a[i]-a[(l+r)>>1]);
        }
        return ans;
    }
}

E 小苯的数字变换

根据小学数学知识，一个正整数的数根就是其对9取模的值（特殊的，9的倍数的根为9），因此遍历每个字符，找到以每个字符结尾的字串的根即可，另外要减去连续0形成的额外的9，时间复杂度O(9Tsum(len(x)))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int t=sc.nextInt();t!=0;t--){
            int count[]=new int[9],num=0;
            long ans=0;
            for(char c:sc.next().toCharArray()){
                num=c=='0'?num+1:0;
                count[0]++;
                int cur[]=new int[9];
                for(int i=0;i<9;i++){
                    cur[(i+c-'0')%9]=count[i];
                    ans+=(long)cur[(i+c-'0')%9]*((i+c-'0')%9==0?9:(i+c-'0')%9);
                }
                count=cur;
                ans-=num*9L;
            }
            System.out.println(ans);
        }
    }
}

F 小苯的序列合并

重要结论：假如答案确定且数组分成若干段，其中连续的三段一定可以合并成一段，因为三段合并一定是的异或结果是答案的超集，且两段取与操作也一定是答案的超集，那么数组只需分成1或2段，时间复杂度O(Tn)

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