题解 | 牛客周赛 Round 60 DEF Java题解

DEF Java题解~~代码已去除冗余

D 我们N个真是太厉害了

求第一个空白区间的问题，需要从小数开始累加，假如已经遍历过的数字最大值为max，那么假如一个新数字a，则能表示的心得区间的最小数为a，其中区间(max,a)之间的数字是无法表示的，倘若区间不空，其中的最小数即为不能表示的最小数值，时间复杂度O(Tnlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int n=sc.nextInt(),a[]=new int[n];
            for(int j=0;j<n;j++){
                a[j]=sc.nextInt();
            }
            Arrays.sort(a);
            long max=0;
            for(int b:a){
                if(b>max+1){
                    break;
                }
                max+=b;
            }
            System.out.println(max+1<=n?max+1:"Cool!");
        }
    }
}

E 折返跑

一共需要选择中间的m-1个杆子，假如选定了杆子，那么每个边杆子是左边杆子呆过的地方还是右边杆子就一定确定了，因此是一个组合问题，计算中需要预处理，并处理逆元，时间复杂度 O(C+Tlog(mod))，其中C==1e6，mod==1e9+7

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

F 口吃

参考资料，时间复杂度O(nlog(mod))

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 n=sc.nextInt();
        long ans=1,a[]=new long[n],b[]=new long[n],p[]=new long[n],q[]=new long[n];
        for(int i=0;i<n-1;i++){
            a[i]=sc.nextInt();
        }
        for(int i=0;i<n-1;i++){
            b[i]=sc.nextInt();
        }
        p[0]=1;
        q[0]=(b[0]*pow(a[0],mod-2)+1)%mod;
        for(int i=1;i<n-1;i++){
            p[i]=pow(a[i],2)*pow((pow(a[i],2)+pow(b[i],2)+mod-p[i-1]*pow(b[i],2)%mod)%mod,mod-2)%mod;
            q[i]=(pow(a[i]+b[i],2)+pow(b[i],2)*q[i-1])%mod*pow((pow(a[i],2)+pow(b[i],2)+mod-p[i-1]*pow(b[i],2)%mod)%mod,mod-2)%mod;
        }
        for(int i=n-2;i>=0;i--){
            ans=(ans*p[i]+q[i])%mod;
        }
        System.out.println(ans);
    }
    static long pow(long a,long b){
        long ans=1;
        while(b!=0){
            if(b%2==1){
                ans=ans*a%mod;
            }
            b>>=1;
            a=a*a%mod;
        }
        return ans;
    }
}