第九届蓝桥杯

日志统计

时间复杂度：O(nlogn)
这道题主要是在输入数据的时候就分好类，然后再根据升序排序来排好ts时刻的顺序。
然后把map中的元素取出来，进行操作。
从list的0开始一直到结尾，进行二分操作的到另一个下标，看看在时间间隔为d时，两个下标的间隔是不是大于等于d
是的话就直接跳出，不是就一直遍历到结尾。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//n行日志
        int d = sc.nextInt();//时间长度d
        int k = sc.nextInt();//k个赞
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            int ts = sc.nextInt();
            int id = sc.nextInt();
            map.computeIfAbsent(id, K -> new ArrayList<>()).add(ts);
        }
        List<Integer> res = new ArrayList<>();
        for(Map.Entry<Integer, List<Integer>> entry : map.entrySet()){
            int id = entry.getKey();
            List<Integer> list = entry.getValue();
            list.sort((i, j) -> {
                return i - j;
            }); 
            for(int i = 0; i < list.size(); i++){
                int cur = find(list, i, d);
                if(cur - i + 1 >= k){
                    res.add(id);
                    break;
                }
            }
        }
        res.sort((i, j) -> {
            return i - j;
        });
        for(int i = 0; i < res.size(); i++){
            System.out.println(res.get(i));
        }

        sc.close();
    }

    public static int find(List<Integer> list, int m, int d) {
        int len = list.size();
        int l = m, r = len - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(Math.abs(list.get(m) - list.get(mid)) < d){
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        return l;
    }

}

全球变暖

先是通过dfs找到每一座岛屿的同时，把岛屿上的点给存进队列中，对队列进行遍历，处理之后，看看岛屿还有没有点是没有变成海洋的。
全变成海洋就+1

import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Vector;

public class Main {
    static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] matrix = new char[n][n];
        for(int i = 0; i < n; i++) {
            String s = sc.next();
            char[] array = s.toCharArray();
            for(int j = 0; j < n; j++) {
                matrix[i][j] = array[j];
            }
        }
        boolean[][] used = new boolean[n][n];
        int res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == '#' && !used[i][j]) {
                    Queue<int[]> queue = new LinkedList<int[]>();
                    dfs(matrix, i, j, queue, used);
                    int count = queue.size();
                    while(!queue.isEmpty()) {
                        int[] cur = queue.poll();
                        for(int[] dir : dirs) {
                            int x = cur[0] + dir[0];
                            int y = cur[1] + dir[1];
                            if(x < 0 || y < 0 || x > n || y > n || matrix[x][y] == '#') {
                                continue;
                            }
                            count--;
                            break;
                        }
                    }
                    if(count == 0) {
                        res++;
                    }
                }
            }
        }
        System.out.println(res);

        sc.close();
    }

    public static void dfs(char[][] matrix, int x, int y,
            Queue<int[]> queue, boolean[][] used) {
        int n = matrix.length;
        if(x < 0 || y < 0 || x > n || y > n || matrix[x][y] == '.' || used[x][y]) {
            return ;
        }
        used[x][y] = true;
        queue.offer(new int[] {x, y});
        dfs(matrix, x - 1, y, queue, used);
        dfs(matrix, x + 1, y, queue, used);
        dfs(matrix, x, y - 1, queue, used);
        dfs(matrix, x, y + 1, queue, used);

    }
}

第十届蓝桥杯

E：迷宫

第一遍通过bfs从终点开始一层一层的往起点前进，找到每一个点离终点有多远
第二次就是从起点出发，找到一个比起点少1的下一个点，沿着这个规律走，一直到终点，就是答案了

import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Vector;

public class Main {

    static int[][] dirs = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
    static String[] S = {"D", "L", "R", "U"};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] matrix = new int[n][m];
        for(int i = 0; i < n; i++) {
            String s = sc.next();
            char[] array = s.toCharArray();
            for(int j = 0; j < m; j++) {
                matrix[i][j] = array[j] - '0';
            }
        }
        int[][] dist = new int[n][m];
        dist = bfs(dist, matrix);
        handle(dist, matrix);
        sc.close();
    }

    public static int[][] bfs(int[][] dist, int[][] matrix) {
        for(int[] i : dist) {
            Arrays.fill(i, -1);
        }
        Queue<int[]> queue = new LinkedList<int[]>();
        int n = matrix.length;
        int m = matrix[0].length;
        boolean[][] used = new boolean[n][m];
        queue.offer(new int[] {29, 49});
        used[29][49] = true;
        int conut = 0;
        while(!queue.isEmpty()) {
            int s = queue.size();
            for(int i = 0; i < s; i++) {
                int[] cur = queue.poll();
                dist[cur[0]][cur[1]] = conut;
                for(int[] dir : dirs) {
                    int x = cur[0] + dir[0];
                    int y = cur[1] + dir[1];
                    if(x < 0 || y < 0 || x > 29 || y > 49 || used[x][y] || matrix[x][y] == 1) {
                        continue;
                    }
                    queue.offer(new int[] {x, y});
                    used[x][y] = true;
                }
            }
            conut++;
        }
        return dist;
    }

    public static void handle(int[][] dist, int[][] matrix) {
        boolean flag = true;
        int[] cur = {0, 0};
        while(flag) {
            int x = cur[0];
            int y = cur[1];
            int pre = dist[x][y];
            int nx = 0;
            int ny = 0;
            for(int i = 0; i < 4; i++) {
                nx = x + dirs[i][0];
                ny = y + dirs[i][1];
                String s = S[i];
                if(nx < 0 || ny < 0 || nx > 29 || ny > 49) {
                    continue;
                }
                if(pre == dist[nx][ny] + 1) {
                    System.out.print(s);
                    break;
                }
            }
            cur[0] = nx;
            cur[1] = ny;
            if(cur[0] == 29 && cur[1] == 49) {
                break;
            }
        }
    }

}

G：外卖店优先级

暴力解法，能过80% O(n * n)
遍历每一个时刻，看看这个时刻有没有订单，要是某一家店铺有订单的话就+2，然后标记这个店铺有订单。
然后在当前时刻内，遍历每一家店铺，要是这家店铺在当前时刻没有订单的话就-1；
这样遍历完时刻后，就能知道最后有多少家店铺是在优先级里的。

import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Vector;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int t = sc.nextInt();
        PriorityQueue<Pair> priority = new PriorityQueue<Main.Pair>((i, j) -> {
            return i.time - j.time;
        });
        for(int i = 0; i < m; i++) {
            int time = sc.nextInt();
            int id = sc.nextInt();
            priority.offer(new Pair(time, id));
        }
        int[][] q = new int[n + 1][2];
        for(int i = 1; i <= n; i++) {
            q[i] = new int[] {i, 0};
        }
        boolean[] flag = new boolean[n + 1];
        for(int i = 1; i <= t; i++) {
            boolean[] used = new boolean[n + 1];
            while(!priority.isEmpty()) {
                Pair curPair = priority.peek();
                if(curPair.time != i) {
                    break;
                }
                curPair = priority.poll();
                int id = curPair.id;
                used[id] = true;
                q[id][1] += 2;
            }
            for(int j = 1; j <= n; j++) {
                if(!used[j] && q[j][1] > 0) {
                    q[j][1]--;
                }
            }
            for(int[] k : q) {
                int id = k[0];
                int pri = k[1];
                if(pri > 5) {
                    flag[id] = true;
                }
                if(flag[id] && pri <= 3) {
                    flag[id] = false;
                }
            }

        }
        int res = 0;
        for(int i = 1; i <= n; i++) {
            if(flag[i]) {
                res++;
            }
        }
        System.out.println(res);
        sc.close();
    }


    static class Pair{
        int time;
        int id;
        public Pair(int time, int id) {
            this.time = time;
            this.id = id;
        }

    }

}

十一届蓝桥杯

寻找2020

import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] matrix = new int[n][n];
        for(int i = 0; i < n; i++) {
            String s = sc.next();
            char[] array = s.toCharArray();
            for(int j = 0; j < n; j++) {
                matrix[i][j] = array[j] - '0';
            }
        }
        int res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == 2) {
                    res += find(matrix, i, j);
                }
            }
        }
        System.out.println(res);
        sc.close();
    }

    public static int find(int[][] matrix, int x, int y) {
        int n = matrix.length;
        int res = 0;
        if(x + 3 < n) {
            if(matrix[x + 1][y] == 0 && matrix[x + 2][y] == 2 && matrix[x + 3][y] == 0) {
                res++;
            }
        }
        if(y + 3 < n) {
            if(matrix[x][y + 1] == 0 && matrix[x][y + 2] == 2 && matrix[x][y + 3] == 0) {
                res++;
            }
        }
        if(x + 3 < n && y + 3 < n) {
            if(matrix[x + 1][y + 1] == 0 && matrix[x + 2][y + 2] == 2 && matrix[x + 3][y + 3] == 0) {
                res++;
            }
        }
        return res;
    }


}

蛇形填数

import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        int cur = 0;
        for(int i = 1; i <= 39; i++) {
            cur += i;
            System.out.println(cur + " " + (cur - i + 1));
        }
    }


}

七段码

F： 成绩分析

import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Vector;


public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        int sum = 0;
        for(int i : nums) {
            sum += i;
            min = Math.min(min, i);
            max = Math.max(max, i);
        }
        double p = sum / (n + 0.0);
        System.out.println(max);
        System.out.println(min);
        System.out.printf("%.2f", p);
        sc.close();
    }


}

G:单词分析

import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Vector;


public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int[] nums = new int[26];
        char[] array = s.toCharArray();
        for(char c : array) {
            nums[c - 'a']++;
        }
        int a = 0;
        int b = 0;
        for(int i = 0; i < 26; i++) {
            if(nums[i] > b) {
                b = nums[i];
                a = i;
            }
        }
        System.out.println((char) ('a' + a));
        System.out.println(b);
        sc.close();
    }


}

H:数字三角形

第一次用的是dfs然后超时，过了4个用例
正解应该是动态规划

import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Vector;


public class Main {
    static List<Integer> res = new ArrayList<Integer>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] matrix = new int[n][n];
        for(int[] i : matrix) {
            Arrays.fill(i, -1);
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        if(n == 1) {
            System.out.println(matrix[0][0]);
        }else {
            dfs(matrix, 1, 0, 1, 0, matrix[0][0]);
            dfs(matrix, 1, 1, 0, 1, matrix[0][0]);
            int result = 0;
            for(int i : res) {
                result = Math.max(result, i);
            }
            System.out.println(result);
        }



        sc.close();
    }

    public static void dfs(int[][] matrix, int x, int y, int cur0, int cur1, int sum) {
        int n = matrix.length;
        if(x >= n || y >= n ||matrix[x][y] == -1) {
            return;
        }
        if(x == n - 1 && Math.abs(cur0 - cur1) <= 1) {
            res.add(sum + matrix[x][y]);
            return ;
        }
        dfs(matrix, x + 1, y + 1, cur0, cur1 + 1, sum + matrix[x][y]);
        dfs(matrix, x + 1, y, cur0 + 1, cur1, sum + matrix[x][y]);  
    }

}

应该用的是dp
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + matrix[i][j];

import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Vector;


public class Main {
    static List<Integer> res = new ArrayList<Integer>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] matrix = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        int[][] dp = new int[n][n];
        dp[0][0] = matrix[0][0];
        for(int i = 1; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                if(j == 0) {
                    dp[i][j] = dp[i - 1][j] + matrix[i][j];
                }else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1]) + matrix[i][j]; 
                }
            }
        }
        if(n % 2 == 0) {
            System.out.println(Math.max(dp[n - 1][(n / 2) - 1], dp[n - 1][(n / 2)]));
        }else {
            System.out.println(dp[n - 1][n / 2]);
        }

        sc.close();
    }
}