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

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

C 绿 && F 紫

在这个数据范围下，需要用到矩阵快速幂。。。先求出字符串重复一次的转移矩阵，再将其变成n次方，最后乘初始向量，时间复杂度O(27Tnlogn)

import java.util.*;
public class Main{
    static long mod=(int)1e9+7,mat[][][]={{{2,0,1},{0,1,0},{0,0,1}},{{1,0,0},{1,2,1},{0,0,1}}};
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            long n=sc.nextLong(),matrix[][]={{1,0,0},{0,1,0},{0,0,1}},ans[]=new long[]{0,0,1};
            for(char c:sc.next().toCharArray()){
                matrix=multiply(mat[c-'0'],matrix);
            }
            for(;n!=0;n>>=1,matrix=multiply(matrix,matrix)){
                if(n%2==1){
                    ans=multiply(matrix,ans);
                }
            }
            System.out.println((ans[0]+ans[1])%mod);
        }
    }
    static long[][] multiply(long a[][],long b[][]){
        long ans[][]=new long[3][3];
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                for(int k=0;k<3;k++){
                    ans[i][j]=(ans[i][j]+a[i][k]*b[k][j])%mod;
                }
            }
        }
        return ans;
    }
    static long[] multiply(long a[][],long b[]){
        long ans[]=new long[3];
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                ans[i]=(ans[i]+a[i][j]*b[j])%mod;
            }
        }
        return ans;
    }
}

D 青

此题主要参考了官解的思路，首先就是特判k等于1的情况；其他时候，需要固定首尾为错题，二分答案，时间复杂度O(Tnlog(sum(a)))

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--){
            int n=sc.nextInt(),k=sc.nextInt(),a[]=new int[n];
            long sum=0;
            for(int j=0;j<n;j++){
                a[j]=sc.nextInt();
                sum+=a[j];
            }
            if(k==0){
                System.out.println(sum);
            }
            else if(k==1){
                System.out.println(sum-Math.min(a[0],a[n-1]));
            }
            else{
                long l=1,r=sum-a[0]-a[n-1];
                while(l<r){
                    long mid=(l+r)>>1;
                    if(find(a,mid)>=k-2){
                        l=mid;
                    }
                    else{
                        r=mid-1;
                    }
                    if(l==r-1){
                        if(find(a,r)>=k-2){
                            l=r;
                        }
                        break;
                    }
                }
                System.out.println(l);
            }
        }
    }
    static int find(int a[],long min){
        int ans=0;
        long cur=0;
        for(int i=1;i<a.length-1;i++){
            cur+=a[i];
            if(cur>=min&&i<a.length-2){
                ans++;
                cur=0;
                i++;
                if(i==a.length-2){
                    ans--;
                }
            }
            else if(cur<min&&i==a.length-2){
                ans--;
            }
        }
        return ans;
    }
}

E 蓝

对于乘1，是对答案没有贡献的，因此只需考虑不为1的乘数，而这样的操作次数不超过16，不妨将1e5以内的答案都预处理出来，时间复杂度O(ABlogB+T)，A==16，B==1e5

import java.util.*;
public class Main{
    static int ans[][]=new int[18][100005];
    static{
        for(int i=0;i<18;i++){
            Arrays.fill(ans[i],(int)1e9);
        }
        ans[0][1]=0;
        for(int j=0;j<17;j++){
            for(int i=1;i<=100000;i++){
                for(int k=1;k*i<=100000;k++){
                    ans[j+1][i*k]=Math.min(ans[j+1][i*k],ans[j][i]+k-1);
                }
            }
        }
    }
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            System.out.println(ans[Math.min(17,sc.nextInt())][sc.nextInt()]);
        }
    }
}