题解 | 牛客练习赛138 Java题解

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

A 小s的签到题

按照题意寻找即可，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),idx[]=new int[n],max=-1,ans=200;
        for(int i=0;i<n;i++){
            idx[i]=sc.next().charAt(0);
        }
        for(int i=0;i<n;i++){
            String s=sc.next();
            int count=Integer.parseInt(s.substring(0,s.indexOf("/")));
            if(count>max||count==max&&ans>idx[i]){
                max=count;
                ans=idx[i];
            }
        }
        System.out.println((char)ans);
    }
}

B 行列改写

越靠后的修改，越能代表最终值，那么就将行列的修改值降序排列，较大的值优先赋值给矩阵额对应剩余的位置，时间复杂度O(nm+log(m+n))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        long ans=0;
        Queue<int[]> q=new PriorityQueue<>((a,b)->Integer.compare(b[0],a[0]));
        for(int i=0;i<n;i++){
            q.add(new int[]{sc.nextInt(),0});
        }
        for(int i=0;i<m;i++){
            q.add(new int[]{sc.nextInt(),1});
        }
        while(!q.isEmpty()){
            int a[]=q.poll();
            if(a[1]==0){
                ans+=(long)a[0]*m;
                n--;
            }
            else{
                ans+=(long)a[0]*n;
                m--;
            }
        }
        System.out.println(ans);
    }
}

C 树上替身追赶游戏

最佳的方案一定是向着最远的叶子结点一路走去，因此找到深度最大的就好了，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt();
        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);
        }
        System.out.println(find(k,0,0,path)+1);
    }
    static int find(int k,int p,int len,List<Integer> path[]){
        int ans=len;
        for(int a:path[k]){
            if(a!=p){
                ans=Math.max(ans,find(a,k,len+1,path));
            }
        }
        return ans;
    }
}

D 全对！

最终结果一定是以所有长度的最小公倍数为最短周期的，因此可以用多个16的二进制mask来代表每种长度的答案，再依据最长周期来判断每个位置是否可能为全1，时间复杂度O(sum(len(s))+nlog(max(len(s)))+lcm(s))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),lcm=1,mask[]=new int[18];
        Arrays.fill(mask,(1<<20)-1);
        for(int i=0;i<n;i++){
            String s=sc.next();
            lcm=lcm/gcd(lcm,s.length())*s.length();
            int cur=0;
            for(int j=s.length()-1;j>=0;j--){
                cur=(cur<<1)|(s.charAt(j)-'0');
            }
            mask[s.length()]&=cur;
        }
        for(int i=0;i<lcm;i++){
            boolean ok=true;
            for(int j=1;j<=16;j++){
                ok&=(mask[j]>>(i%j)&1)==1;
            }
            if(ok){
                System.out.println(i+1);
                return;
            }
        }
        System.out.println(-1);
    }
    static int gcd(int a,int b){
        return a<b?gcd(b,a):b==0?a:gcd(a%b,b);
    }
}

以下题目思路均自于参考资料，并使用Java实现

E 图上替身追赶游戏

时间复杂度O(n)

import java.util.*;
public class Main{
    static long ans=0;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt();
        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,0,path);
        System.out.println(ans);
    }
    static int[] find(int k,int p,List<Integer> path[]){
        int arr[]=new int[6];
        arr[0]=1;
        for(int a:path[k]){
            if(a!=p){
                int cur[]=find(a,k,path);
                //3，4，5 长度的路径
                for(int i=3;i<=5;i++){
                    for(int j=0;j<=i;j++){
                        ans+=(long)arr[j]*(i-j-1>=0?cur[i-j-1]:0);
                    }
                }
                for(int i=1;i<6;i++){
                    arr[i]+=cur[i-1];
                }
            }
        }
        return arr;
    }
}

F 奇素数回路

时间复杂度O((C+Tn)logC),C==2e5

import java.util.*;
public class Main{
    static boolean isPrime[]=new boolean[100005];
    static{
        Arrays.fill(isPrime,true);
        for(int i=2;i<=100000;i++){
            if(isPrime[i]){
                for(int j=i*2;j<=100000;j+=i){
                    isPrime[j]=false;
                }
            }
        }
        isPrime[0]=isPrime[1]=isPrime[2]=false;
    }
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
             int n=sc.nextInt(),p=-1;
             List<Integer> ans=new ArrayList<>();
             ans.add(1);
             for(int j=3;j<n;j++){
                 if(isPrime[j]&&isPrime[n-j]&&gcd(n,j)==1){
                     p=j;
                     break;
                 }
             }
             if(p==-1){
                 System.out.println(-1);
             }
             else{
                 for(int j=2;j<=n;j++){
                     ans.add((ans.get(j-2)-1+p)%n+1);
                 }
                 for(int a:ans){
                     System.out.print(a+" ");
                 }
                 System.out.println();
             }
        }
    }
    static int gcd(int a,int b){
        return a<b?gcd(b,a):b==0?a:gcd(a%b,b);
    }
}

G k人训练方阵

时间复杂度O(24C^2+Tk^2logn)

import java.util.*;
public class Main{
    static long mod=(int)1e9+7,mat[][][]=new long[105][][];
    static{
        for(int i=2;i<=100;i++){
            mat[i]=new long[24][];
            mat[i][0]=new long[i];
            mat[i][0][0]=mat[i][0][1]=1;
            for(int j=1;j<24;j++){
                mat[i][j]=multiply(mat[i][j-1],mat[i][j-1],i);
            }
        }
    }
    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();
            if(k==1){
                System.out.println(pow(2,n)-1);
            }
            else{
                long ans[]=new long[k];
                ans[0]=1;
                for(int j=0;j<26;j++){
                    if((n>>j&1)==1){
                        ans=multiply(ans,mat[k][j],k);
                    }
                }
                System.out.println(ans[1]);
            }
        }
    }
    static long[] multiply(long a[],long b[],int k){
        long ans[]=new long[k];
        for(int i=0;i<k;i++){
            for(int j=0;j<k;j++){
                ans[(i+j)%k]=(ans[(i+j)%k]+a[i]*b[j])%mod;
            }
        }
        return ans;
    }
    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;
    }
}