题解 | 牛客周赛 Round 42 BCDEF Java

B~F题解

B 小红的数组移动

按照题目模拟就好了，时间复杂度O(n)

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(),a[]=new int[n],cur=0;
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        long ans=0;
        for(char c:sc.next().toCharArray()){
            cur=c=='L'?Math.max(0,cur-1):Math.min(cur+1,n-1);
            ans+=a[cur];
        }
        System.out.println(ans%mod);
    }
}

C 小红的素数合并

我不是数学家，不会证明为什么这么做，瞎吉巴试就行了：先排序，偶数数组的话，首尾依次向中间靠拢相乘，否则空出最大的数字，剩下的首尾依次向中间靠拢相乘，时间复杂度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.nextInt();
        }
        Arrays.sort(a);
        long max=-(long)1e18,min=-max;
        if(n%2==1){
            max=min=a[n-1];
        }
        for(int i=0,j=n-1-n%2;i<j;i++,j--){
            max=Math.max(max,a[i]*a[j]);
            min=Math.min(min,a[i]*a[j]);
        }
        System.out.println(max-min);
    }
}

D 小红的树上删边

首先排除n为奇数的情况；；n为偶数的时候，需要看一条边连接的两个连通块，假如都是偶数个点的话，这个边就能删除，假如暴力删边再验证是平方度咋读会超时，因袭可以利用由底向上的递归来实现，记录每个节点子树方向的总点数情况，是偶数的可以删，这样只需一次遍历，时间复杂度O(n)

import java.util.*;
public class Main{
    static int ans=0;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        if(n%2==1){
            System.out.println("-1");
            return;
        }
        List<Integer> path[]=new List[n+5];
        for(int i=1;i<=n;i++){
            path[i]=new ArrayList<>();
        }
        for(int i=0;i<n-1;i++){
            int u=sc.nextInt(),v=sc.nextInt();
            path[u].add(v);
            path[v].add(u);
        }
        find(1,path,new int[n+5],new boolean[n+5]);
        System.out.println(ans);
    }
    static void find(int k,List<Integer> path[],int count[],boolean has[]){
        has[k]=true;
        count[k]=1;
        for(int a:path[k]){
            if(!has[a]){
                find(a,path,count,has);
                count[k]^=count[a];
                if(count[a]==0){
                    ans++;
                }
            }
        }
    }
}

E 小红的子序列求和

比较裸的前缀和+贡献量的思路，每个数字有选和不选两种情况，考虑到逆元的计算，本代码核心算法时间复杂度为O(n*klog(mod))，本题中mod==1e9+7

import java.util.*;
public class Main{
    static int mod=(int)1e9+7;
    static long fac[]=new long[1005];
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        fac[0]=1;
        for(int i=1;i<=1000;i++){
            fac[i]=fac[i-1]*i%mod;
        }
        int n=sc.nextInt(),k=sc.nextInt();
        String s=sc.next();
        long ans[][]=new long[n+1][k+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=k;j++){
                ans[i][j]=(ans[i-1][j]+ans[i-1][j-1]+comb(i-1,j-1)*(s.charAt(i-1)-'0')*pow(10,k-j))%mod;
            }
        }
        System.out.println(ans[n][k]);
    }
    static long comb(int a,int b){
        return a<b?0:fac[a]*pow(fac[b],mod-2)%mod*pow(fac[a-b],mod-2)%mod;
    }
    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;
    }
}

F 小红的扔骰子

参考资料

思路：状态(i,j)的定义为从有i个2和j个3，（其中i的最大值为count2，j的最大值为count3），到首次达到合法状态时好需要操作的次数期望，分类讨论各种转移，并且从大到小更新，，时间复杂度：小于O((logX)^2*log(mod))，本题中mod==1e9+7

import java.util.*;
public class Main{
    static int mod=(int)1e9+7;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        long x=sc.nextLong();
        int count2=0,count3=0;
        while(x%2==0){
            x/=2;
            count2++;
        }
        while(x%3==0){
            x/=3;
            count3++;
        }
        if(x!=1){
            System.out.println("-1");
            return;
        }
        long ans[][]=new long[count2+1][count3+1];
        for(int i=count2;i>=0;i--){
            for(int j=count3;j>=0;j--){
                if(i==count2&&j==count3){
                    continue;
                }
                if(i==count2){
                    ans[i][j]=(ans[i][j+1]+3)%mod;
                }
                else if(j==count3){
                    ans[i][j]=(ans[i+1][j]+3)%mod;
                }
                else{
                    ans[i][j]=(ans[i+1][j]+ans[i][j+1]+3)*pow(2,mod-2)%mod;
                }
            }
        }
        System.out.println(ans[0][0]);
    }
    static long pow(long a,int b){
        long ans=1;
        while(b!=0){
            if(b%2==1){
                ans=ans*a%mod;
            }
            b>>=1;
            a=a*a%mod;
        }
        return ans;
    }
}