题解 | 牛客周赛 Round 90 CDEF Java题解

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

C Tk的构造数组

对于配对儿的数字，一个是ai*i，一个是bi，按照大数乘大数，小数乘小数的顺序重排即可，时间复杂度O(nlogn)

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));
        int n=Integer.parseInt(bf.readLine()),b[]=new int[n];
        StringTokenizer st=new StringTokenizer(bf.readLine());
        long a[]=new long[n];
        Integer idx[]=new Integer[n];
        for(int i=0;i<n;i++){
            a[i]=Long.parseLong(st.nextToken())*(i+1);
            idx[i]=i;
        }
        Queue<Integer> q=new PriorityQueue<>();
        st=new StringTokenizer(bf.readLine());
        for(int i=0;i<n;i++){
            q.add(Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(idx,(a1,a2)->Long.compare(a[a1],a[a2]));
        for(int i=0;i<n;i++){
            b[idx[i]]=q.poll();
        }
        StringBuilder ans=new StringBuilder();
        for(int c:b){
            ans.append(c+" ");
        }
        bw.write(ans.toString());
        bw.flush();
    }
}

D 真爱粉Tk（三）

二分答案即可，求子序列贡献的方法略，时间复杂度O(nlogC),C==1e18

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();
        long count[][]=new long[n][3],l=0,r=(long)1e18;
        for(int i=0;i<n;i++){
            for(char c:sc.next().toCharArray()){
                if(c=='2'){
                    count[i][0]++;
                }
                else if(c=='5'){
                    count[i][2]+=count[i][0];
                    count[i][1]++;
                }
            }
        }
        while(l<r){
            long mid=(l+r)>>1;
            if(find(count,mid)<=k){
                r=mid;
            }
            else{
                l=mid+1;
            }
            if(l==r-1){
                if(find(count,l)<=k){
                    r=l;
                }
                break;
            }
        }
        System.out.println(r);
    }
    static int find(long count[][],long max){
        int ans=1;
        long cur=0,two=0;
        for(long a[]:count){
            if(cur+a[2]+two*a[1]>max){
                ans++;
                two=a[0];
                cur=a[2];
            }
            else{
                cur+=a[2]+two*a[1];
                two+=a[0];
            }
            if(cur>max){
                return (int)1e9;
            }
        }
        return ans;
    }
}

E Tk的染色树

由题意可知，所有叶子结点，即度数为1的几点必然会染色至少一次，且两两结合，必然可以将树全部涂色，因此可将这些点配对染色，若这样的总点数为奇数，那么需要再加上一个权值最小的点，时间复杂度O(nlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),degree[]=new int[n+5],a[]=new int[n+5],num=0;
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
        }
        for(int i=0;i<n-1;i++){
            degree[sc.nextInt()]++;
            degree[sc.nextInt()]++;
        }
        long ans=0;
        for(int i=1;i<=n;i++){
            if(degree[i]<=1){
                ans+=a[i];
                num++;
            }
        }
        if(num%2==1){
            Arrays.sort(a,1,n+1);
            ans+=a[1];
        }
        System.out.println(ans);
    }
}

F Tk的排列间异或

方法一：字典树贪心配对儿，注意需要从大到小配对儿，时间复杂度O(nC),C==19

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),a[]=new int[n+5],b[]=new int[n+5];
        Trie trie=new Trie();
        for(int i=1;i<=n;i++){
            a[sc.nextInt()]=i;
            Trie t=trie;
            for(int j=18;j>=0;j--){
                int p=i>>j&1;
                if(t.children[p]==null){
                    t.children[p]=new Trie();
                }
                t=t.children[p];
                t.count++;
            }
        }
        for(int i=n;i>0;i--){
            Trie t=trie;
            for(int j=18;j>=0;j--){
                int p=i>>j&1;
                if(t.children[p^1]==null||t.children[p^1].count==0){
                    t=t.children[p];
                    b[a[i]]|=p<<j;
                }
                else{
                    t=t.children[p^1];
                    b[a[i]]|=(p^1)<<j;
                }
                t.count--;
            }
        }
        for(int i=1;i<=n;i++){
            System.out.print(b[i]+" ");
        }
    }
}
class Trie{
    Trie children[]=new Trie[2];
    int count=0;
}

方法二：参考官解思路，时间内复杂度O(能过)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),a[]=new int[n+5],b[]=new int[n+5];
        for(int i=1;i<=n;i++){
            a[sc.nextInt()]=i;
        }
        for(int i=n,j=n;i!=0;i=j*2-i,j=i){
            int h=findHigh(i);
            while(j>0&&h==findHigh(j)){
                j--;
            }
            for(int l=j,r=j+1;r<=i;r++,l--){
                b[a[l]]=r;
                b[a[r]]=l;
            }
        }
        for(int i=1;i<=n;i++){
            System.out.print(b[i]+" ");
        }
    }
    static int findHigh(int a){
        int ans=19;
        while(a<(1<<ans)){
            ans--;
        }
        return ans;
    }
}