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

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

D 大预言家！！！！

就是一个螺旋图，找到规律即可，时间复杂度O(TlogC)，其中C==1e9

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            long t=sc.nextLong()-1,l=0,r=(long)1e9;
            while(l<r){
                long mid=(l+r)>>1;
                if(find(mid)<=t){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
                if(l==r-1){
                    if(find(r)<=t){
                        l=r;
                    }
                    break;
                }
            }
            t-=find(l);
            System.out.println(t<=l*2+1?t-l+" "+l:t<=l*4+2?l+1+" "+(l*3-t+1):t<=l*6+4?l*5+3-t+" "+(-l-1):-l-1+" "+(t-l*7-5));
        }
    }
    static long find(long p){
        return p*2*(p*2+1);
    }
}

E 全都要！！！！！

动态规划，时间复杂度O(nk)

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(),a[]=new int[n+5];
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
        }
        long max[][]=new long[n+5][k+5],ans=-(long)1e18;
        for(int i=0;i<=n;i++){
            Arrays.fill(max[i],-(long)1e18);
        }
        max[0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=k;j++){
                for(int p=i-1;p>=0&&p>=i-6;p--){
                    max[i][j]=Math.max(max[i][j],max[p][j-1]+a[i]);
                }
            }
            ans=Math.max(ans,max[i][k]);
        }
        System.out.println(ans);
    }
}

F 水题！！！！！！

找到水流的规律，能下则向下，否则先在时间上加上h再分别向下和左右，找到最短路，时间复杂度O(nmlog(nm))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),h=sc.nextInt(),start[]=null,des[]=null,dis[][][]=new int[n][m][2];
        String s[]=new String[n];
        for(int i=0;i<n;i++){
            s[i]=sc.next();
            for(int j=0;j<m;j++){
                Arrays.fill(dis[i][j],(int)2e9);
                if(s[i].charAt(j)=='*'){
                    start=new int[]{i,j};
                }
                else if(s[i].charAt(j)=='%'){
                    des=new int[]{i,j};
                }
            }
        }
        dis[start[0]][start[1]][1]=0;
        Queue<int[]> q=new PriorityQueue<>((a,b)->Integer.compare(a[3],b[3]));
        q.add(new int[]{start[0],start[1],1,0});
        while(!q.isEmpty()){
            int a[]=q.poll();
            //水流，如果下方是空白，则向下，如果是障碍物，且此时水流向下，则会多花h的时间向下
            if(a[0]+1<n&&(a[2]==1||s[a[0]+1].charAt(a[1])!='#')){
                int d=a[3]+(s[a[0]+1].charAt(a[1])=='#'?h+1:1);
                if(dis[a[0]+1][a[1]][1]>d){
                    dis[a[0]+1][a[1]][1]=d;
                    q.add(new int[]{a[0]+1,a[1],1,d});
                }
            }
            //向左右且下边是障碍物，则继续左右，或者向下但是下边石障碍物，也需要向左右分流
            if(a[0]+1<n&&s[a[0]+1].charAt(a[1])=='#'){
                for(int j=-1;j<=1;j+=2){
                    if(a[1]+j>=0&&a[1]+j<m&&s[a[0]].charAt(a[1]+j)!='#'){
                        int d=1+a[3];
                        if(dis[a[0]][a[1]+j][0]>d){
                            dis[a[0]][a[1]+j][0]=d;
                            q.add(new int[]{a[0],a[1]+j,0,d});
                        }
                    }
                }
            }
        }
        System.out.println(Math.min(dis[des[0]][des[1]][0],dis[des[0]][des[1]][1])<=1e9?Math.min(dis[des[0]][des[1]][0],dis[des[0]][des[1]][1]):-1);
    }
}