题解 | 牛客周赛 Round 51 DEF Java

DEF Java~

D 小红的 gcd

先把a按位求得对于b的余数，再利用辗转相除法求结果，时间复杂度O(len(a)+logb)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        long a=0;
        String s=sc.next();
        long b=sc.nextLong();
        for(char c:s.toCharArray()){
            a=(a*10+c-'0')%b;
        }
        System.out.println(gcd(a,b));
    }
    static long gcd(long a,long b){
        return a<b?gcd(b,a):b==0?a:gcd(a%b,b);
    }
}

E 小红走矩阵

把路径的最小值看做最短路，按规矩求，这里采用的是堆优化方法，时间复杂度O(n^2logn)

import java.util.*;
public class Main{
    static int move[][]={{0,1},{-1,0},{1,0},{0,-1}};
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),a[][]=new int[n][n],ans[][]=new int[n][n];
        for(int i=0;i<n;i++){
            Arrays.fill(ans[i],(int)2e9);
            for(int j=0;j<n;j++){
                a[i][j]=sc.nextInt();
            }
        }
        ans[0][0]=a[0][0];
        Queue<int[]> q=new PriorityQueue<>((b,c)->Integer.compare(b[2],c[2]));
        q.add(new int[]{0,0,a[0][0]});
        while(!q.isEmpty()){
            int b[]=q.poll();
            if(ans[b[0]][b[1]]<b[2]){
                continue;
            }
            for(int mo[]:move){
                int x=b[0]+mo[0],y=b[1]+mo[1];
                if(x>=0&x<n&&y>=0&&y<n){
                    int d=Math.max(b[2],a[x][y]);
                    if(d<ans[x][y]){
                        ans[x][y]=d;
                        q.add(new int[]{x,y,d});
                    }
                }
            }
        }
        System.out.println(ans[n-1][n-1]);
    }
}

F 小红的数组

先求得数组的前缀和数组，一个区间的和的绝对值最大，也就是区间内最大值减去最小值，线段树求解，时间复杂度O((n+q)logn)

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());
        long pre[]=new long[n+1];
        String arr[]=bf.readLine().split(" ");
        for(int i=1;i<=n;i++){
            pre[i]=pre[i-1]+Integer.parseInt(arr[i-1]);
        }
        SegTree st=new SegTree(0,n);
        build(st,pre);
        int q=Integer.parseInt(bf.readLine());
        for(int i=0;i<q;i++){
            arr=bf.readLine().split(" ");
            long a[]=find(st,Integer.parseInt(arr[0])-1,Integer.parseInt(arr[1]));
            bw.write(a[0]-a[1]+"\n");
        }
        bw.flush();
    }
    static long[] find(SegTree st,int a,int b){
        int l=st.l,r=st.r;
        if(l==a&&r==b){
            return new long[]{st.max,st.min};
        }
        else{
            int mid=(l+r)>>1;
            if(b<=mid){
                return find(st.left,a,b);
            }
            else if(a>mid){
                return find(st.right,a,b);
            }
            long arr1[]=find(st.left,a,mid),arr2[]=find(st.right,mid+1,b);
            return new long[]{Math.max(arr1[0],arr2[0]),Math.min(arr1[1],arr2[1])};
        }
    }
    static void build(SegTree st,long pre[]){
        int l=st.l,r=st.r;
        if(l==r){
            st.max=st.min=pre[l];
        }
        else{
            int mid=(l+r)>>1;
            st.left=new SegTree(l,mid);
            st.right=new SegTree(mid+1,r);
            build(st.left,pre);
            build(st.right,pre);
            st.max=Math.max(st.left.max,st.right.max);
            st.min=Math.min(st.left.min,st.right.min);
        }
    }
}
class SegTree{
    long max,min;
    int l,r;
    SegTree left,right;
    public SegTree(int l,int r){
        this.l=l;
        this.r=r;
    }
}

当然对于区间求最值，方法有很多，比如还可以倍增求，时间复杂度同上

//略