题解 | 牛客小白月赛119 BCDEF Java题解

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

B 抽我选的效率曲

按照题目要求计数输出即可，注意化简，时间复杂度O(T*5)

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--){
            Map<Integer,Integer> map=new HashMap<>();
            int num=0;
            for(int j=0;j<5;j++){
                int a=sc.nextInt();
                if(a!=0){
                    map.put(a,map.getOrDefault(a,0)+1);
                    num++;
                }
            }
            int numOfk=map.getOrDefault(sc.nextInt(),0);
            System.out.println(num==0?"1/1000":numOfk/gcd(num,numOfk)+"/"+num/gcd(num,numOfk));
        }
    }
    static int gcd(int a,int b){
        return a<b?gcd(b,a):b==0?a:gcd(a%b,b);
    }
}

C 睡前床边看LIVE

首先容易判断，数字种类大于2的绝对有人说谎；；其次有可能全部都说一样的数字，要么这个数字是n-1（次数所有人的颜色一样），要么这个数字不大于n的一半（有至少两中颜色是并列最多的）；；最后，两种数字，此时最多的数字是唯一的，简称组内最多cur个人，那么在组内的人的回答是cur-1，其余人回答cur，，，时间复杂度O(Tn)

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(),cur1=-1,cur2=-1;
            Map<Integer,Integer> map=new HashMap<>();
            for(int j=0;j<n;j++){
                int a=sc.nextInt();
                map.put(a,map.getOrDefault(a,0)+1);
            }
            if(map.size()>2){
                System.out.println("Lie");
            }
            else{
                for(int a:map.keySet()){
                    if(cur1==-1){
                        cur1=a;
                    }
                    else{
                        cur2=a;
                    }
                }
                if(cur2==-1){
                    System.out.println(cur1==n-1||cur1*2<=n?"Other":"Lie");
                }
                else{
                    if(cur1<cur2){
                        cur1^=cur2;
                        cur2^=cur1;
                        cur1^=cur2;
                    }
                    System.out.println(cur1==cur2+1&&map.get(cur2)-cur1==0?"Other":"Lie");
                }
            }
        }
    }
}

D 世界树上找米库

直接多源广搜记录每个点的距离即可，时间复杂度O(Tn)

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(),count[]=new int[n+5],dis[]=new int[n+5];
            List<Integer> path[]=new List[n+5],points[]=new List[n];
            for(int j=1;j<=n;j++){
                path[j]=new ArrayList<>();
                points[j-1]=new ArrayList<>();
            }
            for(int j=0;j<n-1;j++){
                int u=sc.nextInt(),v=sc.nextInt();
                path[u].add(v);
                path[v].add(u);
                count[v]++;
                count[u]++;
            }
            Arrays.fill(dis,-1);
            Queue<Integer> q=new LinkedList<>();
            for(int j=1;j<=n;j++){
                if(count[j]==1){
                    q.add(j);
                    dis[j]=0;
                }
            }
            while(!q.isEmpty()){
                int a=q.poll();
                for(int b:path[a]){
                    if(dis[b]==-1){
                        dis[b]=1+dis[a];
                        q.add(b);
                        points[dis[b]].add(b);
                    }
                }
            }
            for(int j=n-1;;j--){
                if(points[j].size()>0||j==1){
                    System.out.println(points[j].size());
                    Collections.sort(points[j]);
                    for(int a:points[j]){
                        System.out.print(a+" ");
                    }
                    System.out.println();
                    break;
                }
            }
        }
    }
}

E 森友会里打音游

参考资料，，分别记录1-2e5内所有可能的前缀和后缀的为结尾的最长子序列的长度，最后再统计出现过的数字的数据，时间复杂度O(Tn*sqrt(n))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int pre[]=new int[200005],suf[]=new int[200005];
        for(int i=sc.nextInt();i!=0;i--){
            int n=sc.nextInt(),a[]=new int[n],ans=0;
            for(int j=0;j<n;j++){
                a[j]=sc.nextInt();
            }
            for(int b:a){
                int cur=1;
                for(int j=1;j*j<=b;j++){
                    if(b%j==0){
                        cur=Math.max(cur,1+Math.max(pre[j],pre[b/j]));
                    }
                }
                pre[b]=Math.max(cur,Math.max(pre[b],suf[b]));
                for(int j=1;j*j<=b;j++){
                    if(b%j==0){
                        suf[j]=Math.max(suf[j],1+pre[b]);
                        suf[b/j]=Math.max(suf[b/j],1+pre[b]);
                    }
                }
            }
            for(int b:a){
                ans=Math.max(ans,pre[b]);
            }
            System.out.println(ans);
            Arrays.sort(a);
            for(int j=0;j<n;j++){
                if(j==0||a[j]!=a[j-1]){
                    for(int k=1;k*k<=a[j];k++){
                        if(a[j]%k==0){
                            pre[k]=pre[a[j]/k]=suf[k]=suf[a[j]/k]=0;
                        }
                    }
                }
            }
        }
    }
}

F 这招太狠了烤学妹

参考资料，，是贪心但又不完全是常规贪心，具体需要预判没一段连续o，假如被多切一刀后减少的分数最多的那个，没次都切这样的一段，时间复杂度O(Tnlogn)

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();
            String s=sc.next();
            long ans=0;
            Queue<long[]> q=new PriorityQueue<>((a,b)->Long.compare(b[2],a[2]));
            //[长度，分割刀数，多一刀的增加的减少数]
            for(int j=0;j<n;j++){
                if(s.charAt(j)=='o'){
                    int p=j;
                    while(p<n&&s.charAt(p)=='o'){
                        p++;
                    }
                    ans+=cal(p-j);
                    q.add(new long[]{p-j,0,find(p-j,0)-find(p-j,1)});
                    j=p-1;
                }
            }
            for(;k>0&&!q.isEmpty();k--){
                long a[]=q.poll();
                if(a[1]==a[0]-1){
                    ans-=cal(a[0]);
                }
                else{
                    q.add(new long[]{a[0],a[1]+1,find(a[0],a[1]+1)-find(a[0],a[1]+2)});
                }
            }
            while(!q.isEmpty()){
                long a[]=q.poll();
                ans-=cal(a[0])-find(a[0],a[1]);
            }
            System.out.println(ans);
        }
    }
    static long find(long len,long cut){
        //计算长度为len的段，再分割了cut次的结果
        len-=cut;
        long r=len%(cut+1),d=len/(cut+1);
        return r*cal(d+1)+(cut+1-r)*cal(d);
    }
    static long cal(long a){
        return a*(a+1)/2;
    }
}