题解 | 牛客周赛 Round 67 DEF Java题解

排序危机

https://ac.nowcoder.com/acm/contest/95016/A

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

最多有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，若要常数减小，可用数组模拟

题解 | 牛客周赛 Round 67 DEF Java题解

全站热榜