题解 | 牛客周赛 Round 64 DEFG Java题解

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

D 小红和小紫的博弈游戏

每次相当于从两个对角线中的数字各取一个数，计算哪一个先取到0即可，时间复杂度O(T)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt(),a[]=new int[4];
        for(int i=0;i<t;i++){
            for(int j=0;j<4;j++){
                a[j]=sc.nextInt();
            }
            System.out.println(Math.min(a[0]+a[3],a[2]+a[1])%2==0?"yukari":"kou");
        }
    }
}

E 小红的字符串重排

最大频数不能超过字符串长度一半，否则直接返回1

方法一：相同字符下标集合后排序，新字符串总体右移max(频数)个位置，时间复杂度:O(nlogn+C)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        String s=sc.next();
        int n=s.length(),count[]=new int[200],max=0;
        for(char c:s.toCharArray()){
            count[c]++;
        }
        for(int a:count){
            max=Math.max(max,a);
        }
        if(max*2>n){
            System.out.println("-1");
        }
        else{
            Integer idx[]=new Integer[n];
            char ans[]=new char[n];
            for(int i=0;i<n;i++){
                idx[i]=i;
            }
            Arrays.sort(idx,(a,b)->Integer.compare(s.charAt(a),s.charAt(b)));
            for(int i=0;i<n;i++){
                ans[idx[i]]=s.charAt(idx[(i+max)%n]);
            }
            System.out.println(new String(ans));
        }
    }
}

方法二：按照方法一排序后，首尾双指针互相替换，直到中间遇到同组后，重新从首或者尾替换，时间复杂度:O(nlogn+C)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        String s=sc.next();
        int n=s.length(),count[]=new int[26],max=0;
        for(char c:s.toCharArray()){
            count[c-'a']++;
        }
        for(int a:count){
            max=Math.max(max,a);
        }
        if(max*2>n){
            System.out.println("-1");
        }
        else{
            Integer idx[]=new Integer[n];
            for(int i=0;i<n;i++){
                idx[i]=i;
            }
            Arrays.sort(idx,(a,b)->Integer.compare(s.charAt(a),s.charAt(b)));
            char ans[]=new char[n];
            int l=0,r=n-1;
            for(;l<r&&s.charAt(idx[l])!=s.charAt(idx[r]);l++,r--){
                ans[idx[l]]=s.charAt(idx[r]);
                ans[idx[r]]=s.charAt(idx[l]);
            }
            if(l<=r){
                for(int i=l,j=0,k=n-1;i<=r;i++){
                    if(s.charAt(idx[i])!=s.charAt(idx[j])&&ans[idx[j]]!=s.charAt(idx[i])){
                        ans[idx[i]]=ans[idx[j]];
                        ans[idx[j]]=s.charAt(idx[i]);
                        j++;
                    }
                    else{
                        ans[idx[i]]=ans[idx[k]];
                        ans[idx[k]]=s.charAt(idx[i]);
                        k--;
                    }
                }
            }
            System.out.println(new String(ans));
        }
    }
}

F 小红的树上路径查询（easy） && G 小红的树上路径查询（hard）

参考资料，时间复杂度O(n+qlogn)

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        String arr[]=bf.readLine().split(" ");
        int n=Integer.parseInt(arr[0]),q=Integer.parseInt(arr[1]),p[][]=new int[n+5][17],level[]=new int[n+5],count[]=new int[n+5];
        long sum1[]=new long[n+5],sum2[]=new long[n+5];
        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++){
            arr=bf.readLine().split(" ");
            int u=Integer.parseInt(arr[0]),v=Integer.parseInt(arr[1]);
            path[v].add(u);
            path[u].add(v);
        }
        find(1,path,count,p,level,sum1);
        find(1,n,path,count,0,sum1,sum2);
        for(int i=1;i<17;i++){
            for(int j=1;j<=n;j++){
                p[j][i]=p[p[j][i-1]][i-1];
            }
        }
        for(int i=0;i<q;i++){
            arr=bf.readLine().split(" ");
            int x=Integer.parseInt(arr[0]),y=Integer.parseInt(arr[1]),lca=lca(x,y,p,level);
            bw.write((sum2[x]+sum2[y]-(long)n*(level[x]+level[y]-level[lca]*2))/2+"\n");
        }
        bw.flush();
    }
    static int lca(int a,int b,int p[][],int level[]){
        if(level[a]<level[b]){
            return lca(b,a,p,level);
        }
        for(int i=16;i>=0;i--){
            if(level[a]-level[b]>=1<<i){
                a=p[a][i];
            }
        }
        for(int i=16;i>=0;i--){
            if(p[a][i]!=p[b][i]){
                a=p[a][i];
                b=p[b][i];
            }
        }
        return a==b?a:p[a][0];
    }
    static void find(int k,int n,List<Integer> path[],int count[],long pre,long sum1[],long sum2[]){
        sum2[k]=sum1[k]+pre;
        for(int a:path[k]){
            if(sum2[a]==0){
                find(a,n,path,count,pre+sum1[k]-sum1[a]+n-count[a]*2,sum1,sum2);
            }
        }
    }
    static void find(int k,List<Integer> path[],int count[],int p[][],int level[],long sum[]){
        count[k]=1;
        for(int a:path[k]){
            if(count[a]==0){
                level[a]=1+level[k];
                p[a][0]=k;
                find(a,path,count,p,level,sum);
                count[k]+=count[a];
                sum[k]+=sum[a]+count[a];
            }
        }
    }
}