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

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

D 小红的树上移动

不妨把树看做是以1为根的，可知，在停下来之前，移动方向是远离根节点的，因此只需要统计通往叶节点的概率即可，时间复杂度O(nlog(mod))

import java.util.*;
public class Main{
    static int mod=(int)1e9+7;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=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(1,1,1,path,new boolean[n+5]));
    }
    static long find(int k,int level,long p,List<Integer> path[],boolean has[]){
        has[k]=true;
        List<Integer> list=new ArrayList<>();
        for(int a:path[k]){
            if(!has[a]){
                list.add(a);
            }
        }
        if(list.size()==0){
            return level*pow(p,mod-2)%mod;
        }
        long ans=0;
        for(int a:list){
            ans+=find(a,level+1,p*list.size()%mod,path,has);
        }
        return ans%mod;
    }
    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;
    }
}

E 小红的中位数查询（easy） && F 小红的中位数查询（hard）

可离散值域后，主席树上二分，时间复杂度O(nlogn+q(logn)^2)

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]),a[]=new int[n+5],p=0,map2[]=new int[n];
        TreeSet<Integer> set=new TreeSet<>();
        arr=bf.readLine().split(" ");
        for(int i=1;i<=n;i++){
            a[i]=Integer.parseInt(arr[i-1]);
            set.add(a[i]);
        }
        Map<Integer,Integer> map1=new HashMap<>();
        for(int b:set){
            map1.put(b,p);
            map2[p]=b;
            p++;
        }
        SegTree st[]=new SegTree[n+1];
        st[0]=new SegTree(0,p-1);
        build(st[0]);
        for(int i=1;i<=n;i++){
            st[i]=new SegTree(0,p-1);
            insert(st[i-1],st[i],map1.get(a[i]));
        }
        for(int i=0;i<q;i++){
            arr=bf.readLine().split(" ");
            int l=Integer.parseInt(arr[0]),r=Integer.parseInt(arr[1]),low=0,high=p-1;
            while(low<high){
                int mid=(low+high)>>1;
                if((find(st[r],0,mid)-find(st[l-1],0,mid))*2>=r-l+1){
                    high=mid;
                }
                else{
                    low=mid+1;
                }
                if(low==high-1){
                    if((find(st[r],0,low)-find(st[l-1],0,low))*2>=r-l+1){
                        high=low;
                    }
                    break;
                }
            }
            bw.write(map2[high]+"\n");
        }
        bw.flush();
    }
    static int find(SegTree st,int a,int b){
        int l=st.l,r=st.r;
        if(l==a&&r==b){
            return st.count;
        }
        int mid=(l+r)>>1;
        return b<=mid?find(st.left,a,b):a>mid?find(st.right,a,b):find(st.left,a,mid)+find(st.right,mid+1,b);
    }
    static void insert(SegTree st1,SegTree st2,int a){
        st2.count=st1.count+1;
        int l=st1.l,r=st1.r;
        if(l<r){
            int mid=(l+r)>>1;
            if(a<=mid){
                st2.left=new SegTree(l,mid);
                st2.right=st1.right;
                insert(st1.left,st2.left,a);
            }
            else{
                st2.right=new SegTree(mid+1,r);
                st2.left=st1.left;
                insert(st1.right,st2.right,a);
            }
        }
    }
    static void build(SegTree st){
        int l=st.l,r=st.r;
        st.count=0;
        if(l<r){
            int mid=(l+r)>>1;
            st.left=new SegTree(l,mid);
            st.right=new SegTree(mid+1,r);
            build(st.left);
            build(st.right);
        }
    }
}
class SegTree{
    int l,r,count;
    SegTree left,right;
    public SegTree(int l,int r){
        this.l=l;
        this.r=r;
    }
}

G 小红的数轴移动（二）

最小距离保证的是中间不会提前到0，事假复杂度O(nC),其中C==1e4

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),x=sc.nextInt(),a[]=new int[n+1],sum=0,dis[][]=new int[n+1][20005],last[][][]=new int[n+1][20005][3];
        Arrays.fill(dis[0],(int)1e9);
        dis[0][10000+x]=0;
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
            sum+=a[i];
            dis[i]=dis[i-1].clone();
            for(int j=0;j<=20000;j++){
                last[i][j]=last[i-1][j].clone();
            }
            //先考虑加的
            for(int p=a[i];p<=20000;p++){
                int d=dis[i-1][p-a[i]]+a[i];
                if(d<dis[i][p]){
                    dis[i][p]=d;
                    last[i][p]=new int[]{i-1,p-a[i],i};
                }
            }
            //再考虑减的：
            for(int p=0;p<=20000-a[i];p++){
                int d=dis[i-1][p+a[i]]+a[i];
                if(d<dis[i][p]){
                    dis[i][p]=d;
                    last[i][p]=new int[]{i-1,p+a[i],-i};
                }
            }
        }
        if(dis[n][10000]>1e6){
            System.out.println(sum);
            for(int i=1;i<=n;i++){
                System.out.print(i+" ");
            }
        }
        else{
            boolean has[]=new boolean[n+1];
            System.out.println(dis[n][10000]);
            Queue<Integer> q1=new PriorityQueue<>((u,v)->a[v]-a[u]),q2=new PriorityQueue<>((u,v)->a[v]-a[u]);
            int p1=n,p2=10000;
            while(p1>0){
                int b[]=last[p1][p2];
                if(b[2]<0){
                    q2.add(-b[2]);
                }
                else{
                    q1.add(b[2]);
                }
                has[Math.abs(b[2])]=true;
                p1=b[0];
                p2=b[1];
            }
            while(x!=0){
                if(x<0){
                    System.out.print(q1.peek()+" ");
                    x+=a[q1.poll()];
                }
                else{
                    System.out.print(q2.peek()+" ");
                    x-=a[q2.poll()];
                }
            }
            for(int i=1;i<=n;i++){
                if(!has[i]){
                    System.out.print(i+" ");
                }
            }
        }
    }
}