题解 | 第44场小白月赛

第一题：贪心找到最长进步序列求差值： 大规模数据读入不要使用Scanner，要用BufferedReader

//运行时间1722ms占用内存37532KB
import java.util.*;
import java.io.*;
public class Main{
    public static void main(String args[])throws IOException{
        int arr[]=new int[100005];
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(System.out);
        Scanner sc=new Scanner(System.in);
        int t=Integer.parseInt(bf.readLine());
        for(int i=0;i<t;i++){
            int n=Integer.parseInt(bf.readLine());
            String s[]=bf.readLine().split(" ");
            for(int j=0;j<n;j++){arr[j]=Integer.parseInt(s[j]);}
            int d=-1;
            int l=0,r=1;
            List<Integer> list=new ArrayList<>();
            while(r<=n){
                if(r<n&&arr[r]>=arr[r-1]){r++;}
                else{
                    int k=arr[r-1]-arr[l];
                    if(k>d){
                        list=new ArrayList<>();
                        list.add(l+1);
                        list.add(r);
                        d=k;
                    }
                    else if(k==d){
                        list.add(l+1);
                        list.add(r);
                    }
                    l=r;
                    r++;
                }
            }
            for(int j=0;j<list.size();j++){
                System.out.print(list.get(j));
                System.out.print(" ");
            }
            System.out.println("");
        }
    }
}

第二题：枚举每个点判断周围即可：

//运行时间1270ms占用内存62200KB
import java.io.*;
import java.util.*;
public class Main{
    static int[][] d={{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
    public static void main(String args[])throws IOException{
        //P：植物；*：保护伞；Z：僵尸
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        //PrintWriter pw = new PrintWriter(System.out);
        int t=Integer.parseInt(bf.readLine());
        for(int i=0;i<t;i++){
            Set<Long> set=new HashSet<>();//记录被保护的植物
            String s[]=bf.readLine().split(" ");
            int n=Integer.parseInt(s[0]);
            int m=Integer.parseInt(s[1]);
            char c[][]=new char[n][m];
            for(int j=0;j<n;j++){c[j]=bf.readLine().toCharArray();}
            int count=0;//植物的数量
            for(int x=0;x<n;x++){
                for(int y=0;y<m;y++){
                    char ch=c[x][y];
                    if(ch=='P'){count++;}
                    else if(ch=='*'){
                        for(int p=0;p<8;p++){addPlants(x+d[p][0],y+d[p][1],n,m,c,set);}
                    }
                }
            }
            System.out.println(count-set.size());
        }
    }
    public static void addPlants(int x,int y,int n,int m,char c[][],Set<Long> set){
        if(x==-1||y==-1||x==n||y==m||c[x][y]!='P'){return;}
        //System.out.println(x+" "+y);
        set.add((long)10000000*(long)x+(long)y);
    }
}