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

C~F Java

C 爱音开灯

折半枚举所有x的约数，看是否不大于n，时间复杂度O(sqrt(x))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        long n=sc.nextLong(),x=sc.nextLong();
        int ans=0;
        for(int i=1;(long)i*i<=x;i++){
            if(x%i==0){
                if(i<=n){
                    ans^=1;
                }
                if((long)i*i<x&&x/i<=n){
                    ans^=1;
                }
            }
        }
        System.out.println(ans==0?"OFF":"ON");
    }
}

D 小灯做题

暴力深搜，次数应该不会超过3，时间复杂度O(能过)

import java.util.*;
public class Main{
    static int ans;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            ans=100;
            int a=sc.nextInt(),b=sc.nextInt(),c=sc.nextInt(),k=sc.nextInt();
            find(new int[]{a,b,c},k,0);
            System.out.println(ans==100?-1:ans);
        }
    }
    static void find(int arr[],int k,int count){
        if(count>3){
            return;
        }
        for(int a:arr){
            if(a==k){
                ans=Math.min(ans,count);
                return;
            }
        }
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(i!=j){
                    find(new int[]{arr[i],arr[j],mex(arr[i],arr[j])},k,count+1);
                }
            }
        }
    }
    static int mex(int a,int b){
        for(int i=0;;i++){
            if(i!=a&&i!=b){
                return i;
            }
        }
    }
}

E 立希喂猫

按照b升序排列，并求得a的前缀和以及加权了b的前缀和，对于每个查询，二分得到分界点，分段相加，时间复杂度O((n+q)logn)

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],b[]=new int[n];
        Integer idx[]=new Integer[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
            idx[i]=i;
        }
        for(int i=0;i<n;i++){
            b[i]=sc.nextInt();
        }
        Arrays.sort(idx,(p,q)->Integer.compare(b[p],b[q]));
        long pre1[]=new long[n+1],pre2[]=new long[n+1];
        for(int i=1;i<=n;i++){
            pre1[i]=pre1[i-1]+(long)a[idx[i-1]]*b[idx[i-1]];
            pre2[i]=pre2[i-1]+a[idx[i-1]];
        }
        int q=sc.nextInt();
        for(int i=0;i<q;i++){
            int k=sc.nextInt();
            if(b[idx[n-1]]<k){
                System.out.println(pre1[n]);
            }
            else{
                int l=0,r=n-1;
                while(l<r){
                    int mid=(l+r)>>1;
                    if(b[idx[mid]]>=k){
                        r=mid;
                    }
                    else{
                        l=mid+1;
                    }
                    if(l==r-1){
                        if(b[idx[l]]>=k){
                            r=l;
                        }
                        break;
                    }
                }
                System.out.println(pre1[r]+(pre2[n]-pre2[r])*k);
            }
        }
    }
}

F 祥子拆团

插板法，各个质因数独立操作，时间复杂度O(T*能过)

import java.util.*;
public class Main{
    static int mod=(int)1e9+7;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int x=sc.nextInt(),y=sc.nextInt();
            long ans=1;
            for(int j=2;j*j<=x;j++){
                if(x%j==0){
                    int count=0;
                    while(x%j==0){
                        count++;
                        x/=j;
                    }
                    ans=ans*comb(y+count-1,count)%mod;
                }
            }
            if(x!=1){
                ans=ans*y%mod;
            }
            System.out.println(ans);
        }
    }
    static long pow(long a,int b){
        long ans=1;
        while(b!=0){
            if(b%2==1){
                ans=ans*a%mod;
            }
            a=a*a%mod;
            b>>=1;
        }
        return ans;
    }
    static long comb(int a,int b){
        long ans=1;
        for(int i=1;i<=b;i++){
            ans=ans*(a-i+1)%mod*pow(i,mod-2)%mod;
        }
        return ans;
    }
}