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

D K

最多有n个极大不同区间，且每个区间的长度为n-k+1，依次为周期构造数组即可，时间复杂度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();
        if(k>n){
            System.out.println("NO");
        }
        else{
            System.out.println("YES");
            for(int i=0;i<n;i++){
                System.out.print(i%(n+1-k)+" ");
            }
        }
    }
}

E 小苯的区间选数

方法一：数位动态规划+前缀和思想，处理出不大于某个数的所有可能的数位和的数字个数，上下界作差，差不为零的数位和最大值即为答案，时间复杂度O(10Tlog(r1+r2)+C)，其中C==10*10*190，为预处理20位以内所有数字的数位和的时间

import java.util.*;
public class Main{
    static long count[][]=new long[20][190];
    static{
        count[0][0]=1;
        for(int i=1;i<20;i++){
            for(int j=0;j<10;j++){
                for(int k=189;k>=j;k--){
                    count[i][k]+=count[i-1][k-j];
                }
            }
        }
    }
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            long l1=sc.nextLong(),r1=sc.nextLong(),l2=sc.nextLong(),r2=sc.nextLong(),count1[]=find(r1+r2),count2[]=find(l1+l2-1);
            for(int j=189;;j--){
                if(count1[j]!=count2[j]){
                    System.out.println(j);
                    break;
                }
            }
        }
    }
    static long[] find(long a){
        List<Integer> list=new ArrayList<>();
        while(a!=0){
            list.add((int)(a%10));
            a/=10;
        }
        long ans[]=new long[190];
        int size=list.size(),sum=0;
        for(int i=size-1;i>=0;i--){
            int b=list.get(i);
            for(int j=0;j<b;j++){
                for(int k=189;k-sum-j>=0;k--){
                    ans[k]+=count[i][k-sum-j];
                }
            }
            sum+=b;
        }
        ans[sum]++;
        return ans;
    }
}

方法二：贪心，固定上界，从高位到低位分别尝试每一位保持或者减少一位，其他后边全是9的情况，若所得不小于下界，即可更新答案，时间复杂度O(Tlog(r1+r2))

import java.util.*;
public class Main{
    static long pow[]=new long[20];
    static{
        pow[0]=1;
        for(int i=1;i<20;i++){
            pow[i]=pow[i-1]*10;
        }
    }
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            long l1=sc.nextLong(),r1=sc.nextLong(),l2=sc.nextLong(),r2=sc.nextLong();
            System.out.println(find(l1+l2,r1+r2));
        }
    }
    static long find(long a,long b){
        String s=b+"";
        int n=s.length();
        long ans=0,sum=0;
        for(int i=0;i<n;i++){
            long c=b/pow[n-i-1]%10;
            for(int j=Math.max(0,(int)c-1);j<=c;j++){
                long cur=b/pow[n-i]*pow[n-i]+(j+1)*pow[n-1-i]-1;
                if(cur>=a&&cur<=b){
                    ans=Math.max(ans,sum+j+9*(n-1-i));
                }
            }
            sum+=s.charAt(i)-'0';
        }
        return ans;
    }
}

F 小Z的树迁移

记录每个节点的DFS序，以及子树的顺序上界，在考虑某点的的时候，在顺序范围内的指定深度内找即可，其中区间最大值查询利用了线段树，动态开点，时间复杂度O((n+q)logn)，由于本代码使用的是指针线段树，常数较大，耗时方面，个别时间提交有可能TLE，若要常数减小，可用数组模拟

import java.util.*;
import java.io.*;
public class Main{
    static int idx=0;
    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()),range[][]=new int[n+5][2],dep[]=new int[n+5];
        List<int[]> path[]=new List[n+5];
        List<Integer> level[]=new List[n+5];
        SegTree st[]=new SegTree[n+5];
        for(int i=1;i<=n;i++){
            path[i]=new ArrayList<>();
            level[i]=new ArrayList<>();
            st[i]=new SegTree(1,n);
        }
        for(int i=0;i<n-1;i++){
            String arr[]=bf.readLine().split(" ");
            int a=Integer.parseInt(arr[0]),b=Integer.parseInt(arr[1]),w=Integer.parseInt(arr[2]);
            path[a].add(new int[]{b,w});
            path[b].add(new int[]{a,w});
        }
        dep[1]=1;
        long sum[]=new long[n+5];
        find(st,1,dep,range,0,sum,path,level,new boolean[n+5]);
        int q=Integer.parseInt(bf.readLine());
        for(int i=0;i<q;i++){
            String arr[]=bf.readLine().split(" ");
            int u=Integer.parseInt(arr[0]),d=Integer.parseInt(arr[1]);
            if(dep[u]+d>n){
                bw.write("-1\n");
            }
            else{
                long ans=find(st[dep[u]+d],range[u][0],range[u][1]);
                bw.write(ans>=0?ans-sum[u]+"\n":"-1\n");
            }
        }
        bw.flush();
    }
    static long find(SegTree st,int a,int b){
        if(st==null){
            return -(long)1e18;
        }
        int l=st.l,r=st.r;
        if(l==a&&b==r){
            return st.max;
        }
        int mid=(l+r)>>1;
        if(b<=mid){
            return find(st.left,a,b);
        }
        if(a>mid){
            return find(st.right,a,b);
        }
        return Math.max(find(st.left,a,mid),find(st.right,mid+1,b));
    }
    static void insert(SegTree st,int a,long b){
        int l=st.l,r=st.r;
        st.max=Math.max(st.max,b);
        if(l<r){
            int mid=(l+r)>>1;
            if(a<=mid){
                if(st.left==null){
                    st.left=new SegTree(l,mid);
                }
                insert(st.left,a,b);
            }
            else{
                if(st.right==null){
                    st.right=new SegTree(mid+1,r);
                }
                insert(st.right,a,b);
            }
        }
    }
    static void find(SegTree st[],int k,int dep[],int range[][],long cur,long sum[],List<int[]> path[],List<Integer> level[],boolean has[]){
        has[k]=true;
        sum[k]=cur;
        insert(st[dep[k]],idx,cur);
        idx++;
        level[dep[k]].add(idx);
        range[k][0]=idx;
        for(int a[]:path[k]){
            if(!has[a[0]]){
                dep[a[0]]=1+dep[k];
                find(st,a[0],dep,range,cur+a[1],sum,path,level,has);
            }
        }
        range[k][1]=idx;
    }
}
class SegTree{
    int l,r;
    long max;
    SegTree left,right;
    public SegTree(int l,int r){
        max=-(long)1e18;
        this.l=l;
        this.r=r;
    }
}