题解 | 牛客小白月赛117 CDEF Java题解

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

C 质数

可以发现，当区间长度不小于3的时候，可以将奇数放入S1，偶数放入S2，当区间长度为2时，[1,2]也可以，因此直接判断即可，时间复杂度O(q)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            long l=sc.nextLong(),r=sc.nextLong();
            System.out.println(l==1||r-l>=2?(r-l)&1^1:-1);
        }
    }
}

D 众数

枚举被修改的两个数字，用有序映射来维护，时间复杂度O(n^2logn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        Map<Integer,Integer> map1=new HashMap<>();//记录每个数的次数
        TreeMap<Integer,Integer> map2=new TreeMap<>();//记录每个数的次数的次数
        Map<Integer,TreeSet<Integer>> map3=new HashMap<>();//记录每种次数的集合
        int n=sc.nextInt(),a[]=new int[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
            map1.put(a[i],map1.getOrDefault(a[i],0)+1);
            map3.put(i,new TreeSet<>());
        }
        map3.put(n,new TreeSet<>());
        for(int b:map1.keySet()){
            modify(map2,map1.get(b),1);
            map3.get(map1.get(b)).add(b);
        }
        List<Integer> ans=new ArrayList<>();
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i!=j){
                    inc(map1,map2,map3,a[i],-1);
                    inc(map1,map2,map3,a[j],-1);
                    inc(map1,map2,map3,a[i]+1,1);
                    inc(map1,map2,map3,a[j]-1,1);
                    ans.add(map3.get(map2.lastKey()).last());
                    inc(map1,map2,map3,a[i],1);
                    inc(map1,map2,map3,a[j],1);
                    inc(map1,map2,map3,a[i]+1,-1);
                    inc(map1,map2,map3,a[j]-1,-1);
                }
            }
        }
        for(int b:new TreeSet<>(ans)){
            System.out.print(b+" ");
        }
    }
    static void inc(Map<Integer,Integer> map1,TreeMap<Integer,Integer> map2,Map<Integer,TreeSet<Integer>> map3,int a,int b){
        int p=map1.getOrDefault(a,0);
        map1.put(a,p+b);
        modify(map2,p,-1);
        modify(map2,p+b,1);
        map3.get(p).remove(a);
        map3.get(p+b).add(a);
    }
    static void modify(TreeMap<Integer,Integer> map,int a,int b){
        map.put(a,map.getOrDefault(a,0)+b);
        if(map.get(a)==0){
            map.remove(a);
        }
    }
}

E 种类数

每一轮变化（一轮过程中数字种类数不变），总会有一系列数字同时减少为0，因此直接按照从小到大哦的顺序操作即可，时间复杂度O(nlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        TreeSet<Long> set=new TreeSet<>();
        for(int i=sc.nextInt();i!=0;i--){
            set.add(sc.nextLong());
        }
        long ans=0,size=set.size(),dec=0,has0=0;
        if(size!=1){
            if(set.first()==0){
                size--;
                has0=1;
                set.pollFirst();
            }
            while(!set.isEmpty()){
                long cur=(set.pollFirst()-1-dec)/(size+has0)+1;
                ans+=cur;
                dec+=cur*(size+has0);
                while(!set.isEmpty()&&set.first()<=dec){
                    set.pollFirst();
                    size--;
                }
                has0=1;
                size--;
            }
        }
        System.out.println(ans);
    }
}

F 中位数

计算每种数字的贡献，并利用欧拉定理将幂次降下来，时间复杂度O(C^2+n(n+log(mod))),C==6000,mod==1610612741

import java.util.*;
public class Main{
    static long mod=1610612741,fac[]=new long[6005],comb[][]=new long[6005][6005];
    static{
        fac[0]=comb[0][0]=1;
        for(int i=1;i<=6000;i++){
            fac[i]=fac[i-1]*i%(mod-1);
            comb[i][0]=1;
            for(int j=1;j<=i;j++){
                comb[i][j]=(comb[i-1][j]+comb[i-1][j-1])%(mod-1);
            }
        }
    }
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long ans=1;
        for(int i=1;i<=n;i++){
            long tol=0;
            for(int j=1;j<=n;j++){
                //j是枚举区间的长度，i-1个比i小的，选其中j-1-(j-1)/2个，n-i个比j大的，选其中的(j-1)/2个
                tol=(tol+find(n-i,(j-1)/2,i-1,j-1-(j-1)/2,n-j))%(mod-1);
            }
            ans=ans*pow(i,tol)%mod;
        }
        System.out.println(ans);
    }
    static long find(int a1,int a2,int b1,int b2,int c){
        //a个大于，b个小于，c个其他的
        return a2<0||a1<a2||b2<0||b1<b2?0:comb[a1][a2]*comb[b1][b2]%(mod-1)*fac[a2+b2+1]%(mod-1)*fac[c]%(mod-1)*(c+1)%(mod-1);
    }
    static long pow(long a,long b){
        long ans=1;
        for(;b!=0;b>>=1,a=a*a%mod){
            if(b%2==1){
                ans=ans*a%mod;
            }
        }
        return ans;
    }
}