蓝桥杯 2023 训练四 Java 全解

注意

　　该博客是为了帮助同学学习，并非为了协助同学刷题，请读者保持自觉，请勿做CV工具人。

　　为了节省篇幅，在不影响阅读的前提下，代码中将省略import语句；同时，也不再给出输入和输出样例；过于简单的题也不再文字说明解题思路。

人与神

　　跨界大神 L. Peter Deutsch 有一句名言：“To iterate is human, to recurse divine.”（迭代的是人，递归的是神）。本题就请你直接在屏幕上输出这句话。

题解

public class Main {

    public static void main(String[] args) {
        System.out.println("To iterate is human, to recurse divine.");
    }

}

后天

　　如果今天是星期三，后天就是星期五；如果今天是星期六，后天就是星期一。我们用数字1到7对应星期一到星期日。给定某一天，请你输出那天的“后天”是星期几。

输入格式

　　输入第一行给出一个正整数 D（1 <= D <= 7），代表星期里的某一天。

输出格式

　　在一行中输出 D 天的后天是星期几。

题解

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int d = scanner.nextInt() + 2;
        System.out.println(d > 7 ? d % 7 : d);
    }

}

到底有多二

　　一个整数“犯二的程度”定义为该数字中包含2的个数与其位数的比值。如果这个数是负数，则程度增加 0.5 倍；如果还是个偶数，则再增加 1 倍。例如数字-13142223336是个 11 位数，其中有 3 个 2，并且是负数，也是偶数，则它的犯二程度计算为：3 / 11 × 1.5 × 2 × 100%，约为 81.82%。本题就请你计算一个给定整数到底有多二。

输入格式

　　输入第一行给出一个不超过 50 位的整数 N。

输出格式

　　在一行中输出 N 犯二的程度，保留小数点后两位。

题解

　　非常简单的字符串处理。

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.next();
        int count = 0;
        int length = input.length();
        for (int i = 0; i != length; ++i) {
            if (input.charAt(i) == '2') ++count;
        }
        double weight = 1;
        if ((input.charAt(length - 1) & 1) == 0) weight = 2;
        if (input.startsWith("-")) {
            --length;
            weight *= 1.5;
        }
        System.out.printf("%.2f%%", count * weight / length * 100);
    }

}

求特殊方程的正整数解

　　本题要求对任意给定的正整数 N，求方程 X² + Y² = N 的全部正整数解。

输入格式

　　输入在一行中给出正整数 N（<= 10000）。

输出格式

　　输出方程 X² + Y² = N 的全部正整数解，其中 X <= Y。每组解占 1 行，两数字间以 1 空格分隔，按X的递增顺序输出。如果没有解，则输出No Solution。

题解

　　提前计算出 10000 以内的平方数，然后枚举这些平方数即可。

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] square = new int[100];
        for (int i = 0; i != square.length; ++i) {
            square[i] = (i + 1) * (i + 1);
        }
        int n = scanner.nextInt();
        boolean flag = true;
        for (int i = 0; i != square.length; ++i) {
            int x = square[i];
            int y = n - x;
            if (y < x) break;
            int index = Arrays.binarySearch(square, y);
            if (index < 0) continue;
            flag = false;
            System.out.printf("%d %d\n", i + 1, index + 1);
        }
        if (flag) System.out.print("No Solution");
    }

}

判断题

　　判断题的评判很简单，本题就要求你写个简单的程序帮助老师判题并统计学生们判断题的得分。

输入格式

　　输入在第一行给出两个不超过 100 的正整数 N 和 M，分别是学生人数和判断题数量。第二行给出 M 个不超过 5 的正整数，是每道题的满分值。第三行给出每道题对应的正确答案，0 代表“非”，1 代表“是”。随后 N 行，每行给出一个学生的解答。数字间均以空格分隔。

输出格式

　　按照输入的顺序输出每个学生的得分，每个分数占一行。

题解

public class Main {

    public static void main(String[] args) throws IOException {
        int n = read();
        int m = read();
        int[] scores = new int[m];  // 每道题的分数
        int[] answer = new int[m];  // 每道题的正确答案
        for (int i = 0; i != m; ++i) {
            scores[i] = read();
        }
        for (int i = 0; i != m; ++i) {
            answer[i] = read();
        }
        for (int i = 0; i != n; ++i) {
            int ans = 0;
            for (int k = 0; k != m; ++k) {
                if (read() == answer[k])
                    ans += scores[k];
            }
            System.out.println(ans);
        }
    }

    static int read() throws IOException {
        int result = 0;
        int input = System.in.read();
        do {
            result = (result << 1) + (result << 3) + (input ^ 48);
            input = System.in.read();
        } while (Character.isDigit(input));
        return result;
    }

}

数列求和 - 加强版

　　给定某数字 A（1 <= A <= 9）以及非负整数 N（0 <= N <= 100000），求数列之和 S = A + AA + AAA + ⋯ + AA⋯A（N 个 A）。例如 A = 1, N = 3时，S = 1 + 11 + 111 = 123。

输入格式

　　输入数字 A 与非负整数 N。

输出格式

　　输出其 N 项数列之和 S 的值。

题解

　　这道题 Java 不能用BigInteger，会 TLE，手写一个简易的大数字即可。

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int a = scanner.nextInt();
        int n = scanner.nextInt();
        if (n == 0) {
            System.out.println(0);
            return;
        }
        int carry = 0;  // 进位
        for (int c = n; c != 0; --c) {
            int value = carry + a * c;
            carry = value / 10;
            sb.append(value % 10);
        }
        if (carry != 0) sb.append(carry);
        // 算出来的结果是反着的，需要倒序输出
        System.out.println(sb.reverse());
    }

}

大炮打蚊子

　　现在，我们用大炮来打蚊子：蚊子分布在一个 M × N 格的二维平面上，每只蚊子占据一格。向该平面的任意位置发射炮弹，炮弹的杀伤范围如下示意：

1
2
3

 O
OXO
 O

　　其中，X 为炮弹落点中心，O 为紧靠中心的四个有杀伤力的格子范围。若蚊子被炮弹命中（位于 X 格），一击毙命，若仅被杀伤（位于 O 格），则损失一半的生命力。也就是说，一次命中或者两次杀伤均可消灭蚊子。现在给出蚊子的分布情况以及连续 k 发炮弹的落点，给出每炮消灭的蚊子数。

输入格式

　　第一行为两个不超过 20 的正整数 M 和 N，中间空一格，表示二维平面有 M 行、N 列。

　　接下来M行，每行有 N 个 0 或者 # 字符，其中#表示所在格子有蚊子。

　　接下来一行，包含一个不超过 400 的正整数 k，表示发射炮弹的数量。

　　最后 k 行，每行包括一发炮弹的整数坐标 x 和 y（0 <= x <= M，0 <= y <= N），之间用一个空格间隔。

输出格式

　　对应输入的 k 发炮弹，输出共有 k 行，第 i 行即第 i 发炮弹消灭的蚊子数。

题解

　　注意这道题中 Y 轴是横着的，X 轴是竖着的。

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        scanner.nextLine();
        int[][] map = new int[m][n];    // 记录每个位置上的文字的血量
        for (int y = 0; y != m; ++y) {
            String input = scanner.nextLine();
            for (int x = 0; x != n; ++x) {
                map[y][x] = input.charAt(x) == '0' ? 0 : 2;
            }
        }
        int k = scanner.nextInt();
        for (int i = 0; i != k; ++i) {
            int y = scanner.nextInt();
            int x = scanner.nextInt();
            int count = 0;
            if (map[y][x] > 0) {
                map[y][x] = 0;
                ++count;
            }
            if (x != 0 && --map[y][x - 1] == 0) ++count;
            if (x + 1 != n && --map[y][x + 1] == 0) ++count;
            if (y != 0 && --map[y - 1][x] == 0) ++count;
            if (y + 1 != m && --map[y + 1][x] == 0) ++count;
            System.out.println(count);
        }
    }

}

静静的推荐

　　天梯赛结束后，某企业的人力资源部希望组委会能推荐一批优秀的学生，这个整理推荐名单的任务就由静静姐负责。企业接受推荐的流程是这样的：

只考虑得分不低于 175 分的学生；
一共接受 K 批次的推荐名单；
同一批推荐名单上的学生的成绩原则上应严格递增；
如果有的学生天梯赛成绩虽然与前一个人相同，但其参加过 PAT 考试，且成绩达到了该企业的面试分数线，则也可以接受。

　　给定全体参赛学生的成绩和他们的 PAT 考试成绩，请你帮静静姐算一算，她最多能向企业推荐多少学生？

输入格式

　　输入第一行给出 3 个正整数：N（<= 10⁵）为参赛学生人数，K（<= 5×10³）为企业接受的推荐批次，S（<= 100）为该企业的 PAT 面试分数线。

　　随后 N 行，每行给出两个分数，依次为一位学生的天梯赛分数（最高分 290）和 PAT 分数（最高分 100）。

输出格式

　　在一行中输出静静姐最多能向企业推荐的学生人数。

题解

　　注意理解题意，当如果不考虑 PAT 成绩，同一批次中不能存在成绩相等的学生。题目上第四个条件说明了 PAT 成绩达到分数线的话即使其成绩与另一个人相同，也可以接受。

　　所以我们尽量让 PAT 成绩和参赛成绩均达到要求的学生是一定可以被接受的，只需要计算参赛成绩达到要求但 PAT 成绩未达到要求的学生中有多少人能够被接受即可。

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int s = scanner.nextInt();
        Map<Integer, List<Integer>> input = new TreeMap<>();
        for (int i = 0; i != n; ++i) {
            int key = scanner.nextInt();
            int pat = scanner.nextInt();
            // 因为参赛成绩小于 175 的不可能被接受，直接忽略
            if (key >= 175)
                input.computeIfAbsent(key, t -> new ArrayList<>()).add(pat);
        }
        input.forEach((key, pats) -> pats.sort(Integer::compare));
        AtomicInteger ans = new AtomicInteger();
        input.forEach((key, pats) -> {
            int index = Collections.binarySearch(pats, s);
            if (index < 0)
                index = -(index + 1);
            ans.addAndGet(Math.min(pats.size() - index + k, pats.size()));
        });
        System.out.println(ans);
    }

}

朋友圈

　　某学校有 N 个学生，形成 M 个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出，如果 A 和 B 是朋友，且 B 和 C 是朋友，则 A 和 C 也是朋友。请编写程序计算最大朋友圈中有多少人。

输入格式

　　输入的第一行包含两个正整数 N（<= 30000）和 M（<= 1000），分别代表学校的学生总数和俱乐部的个数。后面的M行每行按以下格式给出 1 个俱乐部的信息，其中学生从 1 ~ N 编号：

　　第 i 个俱乐部的人数 M_i（空格）学生₁（空格）学生₂ … 学生M_i

输出格式

　　输出给出一个整数，表示在最大朋友圈中有多少人。

题解

　　使用并查集进行统计即可，这里我是维护了一个标记每个朋友圈人数的数组，也可以不使用这个数组，合并完毕后再进行统计。

public class Main {

    static int[] union;
    static int[] count;

    static int find(int i) {
        return union[i] == i ? i : (union[i] = find(union[i]));
    }

    static void merge(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (count[a] < count[b]) {
            union[a] = b;
            count[b] += count[a];
        } else {
            union[b] = a;
            count[a] += count[b];
        }
    }

    public static void main(String[] args) throws IOException {
        int n = read();
        int m = read();
        union = new int[n + 1];
        count = new int[n + 1];
        Arrays.fill(count, 1);
        for (int i = 1; i != union.length; ++i)
            union[i] = i;
        for (int i = 0; i != m; ++i) {
            int c = read();
            if (c == 0) continue;
            int key = read();
            for (int k = 1; k != c; ++k) {
                merge(read(), key);
            }
        }
        System.out.println(Arrays.stream(count).max().getAsInt());
    }

    static int read() throws IOException {
        int result = 0;
        int input = System.in.read();
        do {
            result = (result << 1) + (result << 3) + (input ^ 48);
            input = System.in.read();
        } while (Character.isDigit(input));
        return result;
    }

}

Windows 消息队列

　　消息队列是Windows系统的基础。对于每个进程，系统维护一个消息队列。如果在进程中有特定事件发生，如点击鼠标、文字改变等，系统将把这个消息加到队列当中。同时，如果队列不是空的，这一进程循环地从队列中按照优先级获取消息。请注意优先级值低意味着优先级高。请编辑程序模拟消息队列，将消息加到队列中以及从队列中获取消息。

输入格式

　　输入首先给出正整数 N（<= 10⁵），随后N行，每行给出一个指令——GET或PUT，分别表示从队列中取出消息或将消息添加到队列中。如果指令是PUT，后面就有一个消息名称、以及一个正整数表示消息的优先级，此数越小表示优先级越高。消息名称是长度不超过 10 个字符且不含空格的字符串；题目保证队列中消息的优先级无重复，且输入至少有一个GET。

输出格式

　　对于每个GET指令，在一行中输出消息队列中优先级最高的消息的名称和参数。如果消息队列中没有消息，输出EMPTY QUEUE!。对于PUT指令则没有输出。

题解

　　非常简单的优先级队列问题，但是 PTA 上用 Java 过不去。这里我给出两种写法，一种是使用 JDK 中的优先级队列，另一种是手动维护双向优先级队列。

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        PriorityQueue<Node> queue = new PriorityQueue<>(n);
        for (int i = 0; i != n; ++i) {
            String op = scanner.next();
            if (op.charAt(0) == 'G') {
                if (queue.isEmpty()) System.out.println("EMPTY QUEUE!");
                else System.out.println(queue.remove().message);
            } else {
                queue.add(new Node(scanner.next(), scanner.nextInt()));
            }
        }
    }

}

final class Node implements Comparable<Node> {

    String message;
    int priority;

    Node(String message, int priority) {
        this.message = message;
        this.priority = priority;
    }

    @Override
    public int compareTo(Node o) {
        return priority - o.priority;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Node[] deque = new Node[n << 1];
        int left = n, right = n;
        for (int i = 0; i != n; ++i) {
            String op = scanner.next();
            if (op.charAt(0) == 'G') {
                if (right - left == 0) System.out.println("EMPTY QUEUE!");
                else System.out.println(deque[left++].message);
            } else {
                Node node = new Node(scanner.next(), scanner.nextInt());
                // 二分查找插入点
                int index = -Arrays.binarySearch(deque, left, right, node) - 1;
                // 如果插入点右侧元素（包括插入点）数量少就让右侧元素向右移动
                // 否则让插入点左侧元素（不包括插入点）向左移动
                if (right - index < index - left) {
                    System.arraycopy(deque, index, deque, index + 1, right - index);
                    deque[index] = node;
                    ++right;
                } else {
                    System.arraycopy(deque, left, deque, left - 1, index - left);
                    deque[index - 1] = node;
                    --left;
                }
            }
        }
    }

}

final class Node implements Comparable<Node> {

    String message;
    int priority;

    Node(String message, int priority) {
        this.message = message;
        this.priority = priority;
    }

    @Override
    public int compareTo(Node o) {
        return priority - o.priority;
    }

}

列车调度

　　火车站的列车调度铁轨的结构如下图所示。

列车调度示意图

　　两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有 N 条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有 9 趟列车，在入口处按照 {8，4，2，5，3，9，1，6，7} 的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

输入格式

　　输入第一行给出一个整数 N（2 <= N <= 10⁵），下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

输出格式

　　在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

题解

　　这道题使用模拟 + 贪心算法就能解决，因为需要让列车按照从大到小的顺序出队，所以只要队中满足从左向右大小递增的规则，就不会出现有元素无法出队的情况。

　　因此元素入队时要保证它小于队尾的元素，如果大于队尾则不能进入当前队伍。同时基于贪心的原理，我们还应该让元素进入到与队尾元素差值最小的队伍中。

　　因为我们模拟的时候只需要知道队尾的元素，所以直接用一个数组维护即可，使用二分法可以快速的进行查找和修改。

　　同时注意，将旧的元素覆盖为新的更小的元素时并不会破坏数组的有序性，所以无需重新排序，这一点为什么会这样读者可以自行思考一下。

public class Main {

    public static void main(String[] args) throws IOException {
        int n = read();
        int[] array = new int[n];
        int size = 0;
        for (int i = 0; i != n; ++i) {
            int code = read();
            if (size == 0) {
                array[size++] = code;
                continue;
            }
            int index = -Arrays.binarySearch(array, 0, size, code) - 1;
            if (index == size) array[size++] = code;
            else array[index] = code;
        }
        System.out.println(size);
    }

    static int read() throws IOException {
        int result = 0;
        int input = System.in.read();
        do {
            result = (result << 1) + (result << 3) + (input ^ 48);
            input = System.in.read();
        } while (Character.isDigit(input));
        return result;
    }

}

拯救 007

　　在老电影“007之生死关头”（Live and Let Die）中有一个情节，007 被毒贩抓到一个鳄鱼池中心的小岛上，他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去！（据说当年替身演员被最后一条鳄鱼咬住了脚，幸好穿的是特别加厚的靴子才逃过一劫。）

　　设鳄鱼池是长宽为 100 米的方形，中心坐标为（0, 0），且东北角坐标为（50, 50）。池心岛是以（0, 0）为圆心、直径 15 米的圆。给定池中分布的鳄鱼的坐标、以及 007 一次能跳跃的最大距离，你需要告诉他是否有可能逃出生天。

输入格式

　　首先第一行给出两个正整数：鳄鱼数量 N（<= 100）和 007 一次能跳跃的最大距离 D。随后 N 行，每行给出一条鳄鱼的（x, y）坐标。注意：不会有两条鳄鱼待在同一个点上。

输出格式

　　如果 007 有可能逃脱，就在一行中输出Yes，否则输出No。

题解

　　这道题的本质其实是一个散点图，需要我们自行连边，然后判断能否由中心点走到边界，可以用并查集、BFS、DFS 中任意一种方法解决，不过因为我们只需要知道能否连通而不需要知道具体路径，使用并查集更优。

　　由于起点是一个半径为 7.5 的圆形，所以记得对其进行特殊处理，特殊处理的方法有很多，这里仅列出一种。

public class Main {

    static int[] union = new int[101];

    static int find(int code) {
        return union[code] == code ? code : (union[code] = find(union[code]));
    }

    static void merge(int a, int b) {
        union[find(a)] = find(b);
    }

    public static void main(String[] args) {
        for (int i = 1; i != union.length; ++i) union[i] = i;
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int d = scanner.nextInt();
        int d2 = d * d;
        int centerDistance = (int) Math.pow(d + 7.5, 2);
        if (d > 42) {
            System.out.println("Yes");
            return;
        }
        Point[] map = new Point[n + 1];
        map[0] = new Point(0, 0);
        for (int i = 1; i != map.length; ++i) {
            map[i] = new Point(scanner.nextInt(), scanner.nextInt());
            // 每个点都和其它所有点尝试进行连边
            if (map[0].distance(map[i]) <= centerDistance) {
                merge(0, i);
            }
            for (int k = 1; k != i; ++k) {
                if (map[i].distance(map[k]) <= d2) {
                    merge(i, k);
                }
            }
        }
        int center = find(0);
        for (int i = 1; i != map.length; ++i) {
            // 如果指定的点与起点值相同，则说明两点连通
            // 然后判断 007 能否从这个点跳出地图即可
            if (
                    find(i) == center &&
                            (50 - map[i].x <= d || 50 - map[i].y <= d || 50 + map[i].x <= d || 50 + map[i].y <= d)
            ) {
                System.out.println("Yes");
                return;
            }
        }
        System.out.println("No");
    }

}

final class Point {

    int x, y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    int distance(Point that) {
        int difX = x - that.x;
        int difY = y - that.y;
        return difX * difX + difY * difY;
    }

}

试题 I：消息的传递

　　我们的郭嘉大大在曹操这过得进遙自在, 但是有一天曹操给了他一个任务，在建邮城内有 N 个袁绍的奸细，将他们从 1 到 N 进行编号, 同时他们之间存在一种传递关系, 即若 C_i,j = 1, 则奸细 i 能将消息直接传递给奸细 j。

　　现在曹操要发布一个假消息, 需要传达给所有奸细，而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息, 问我们至少要传给几个奸细？

输入格式

　　第一行为 N, 第二行至第 N+1 行为 N×N 的矩阵 ( 若第 I 行第 J 列为 1, 则奸细 I 能将消息直接传递给奸细 J, 若第 I 行第 J 列为 0 , 则奸细 I 不能将消息直接传递给奸细 J) 。

输出格式

　　只有一行：即我们的郭嘉大大首先至少要传递的奸细个数。

题解

　　这道题有一定的难度，具体题解单独写一篇博文，这里给出简单思路和代码。

　　思路其实很简单，使用 tarjan 求强连通分量，然后数入度为 0 的分量就行。

public class Main {

    static int[][] map;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        int n = read();
        low = new int[n + 1];
        map = new int[low.length][low.length];
        for (int i = 1; i != low.length; ++i) {
            int[] linked = map[i];
            int size = 0;
            for (int j = 1; j != low.length; ++j) {
                if (read() == 1) linked[size++] = j;
            }
        }
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 1; i != low.length; ++i) {
            if (low[i] == 0)
                tarjan(i, stack);
        }
        boolean[] intake = new boolean[low.length];
        for (int i = 1; i != low.length; ++i) {
            for (int code : map[i]) {
                if (code == 0) break;
                int index = low[code];
                if (!intake[index] && index != low[i]) {
                    intake[index] = true;
                    --count;
                }
            }
        }
        System.out.println(count);
    }

    static int time = 0;
    static int[] low;

    static void tarjan(int point, Deque<Integer> stack) {
        stack.addLast(point);
        int dfn = low[point] = ++time;
        for (int code : map[point]) {
            if (code == 0) break;
            if (low[code] == 0) {
                tarjan(code, stack);
                low[point] = Math.min(low[point], low[code]);
            }
        }
        for (int code : map[point]) {
            if (code == 0) break;
            if (stack.contains(code))
                low[point] = Math.min(low[point], low[code]);
        }
        if (dfn == low[point]) {
            ++count;
            while (true) {
                int ele = stack.removeLast();
                if (ele == point) break;
                low[ele] = dfn;
            }
        }
    }

    static int read() throws IOException {
        int result = 0;
        int input = System.in.read();
        do {
            result = (result << 1) + (result << 3) + (input ^ 48);
            input = System.in.read();
        } while (Character.isDigit(input));
        return result;
    }

}

红色警报

　　战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的 k 个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。

输入格式

　　输入在第一行给出两个整数 N（0 < N <= 500）和M（<= 5000），分别为城市个数（于是默认城市从 0 到 N-1 编号）和连接两城市的通路条数。随后M行，每行给出一条通路所连接的两个城市的编号，其间以1个空格分隔。在城市信息之后给出被攻占的信息，即一个正整数K和随后的K个被攻占的城市的编号。

　　注意：输入保证给出的被攻占的城市编号都是合法的且无重复，但并不保证给出的通路没有重复。

输出格式

　　对每个被攻占的城市，如果它会改变整个国家的连通性，则输出Red Alert: City k is lost!，其中 k 是该城市的编号；否则只输出City k is lost.即可。如果该国失去了最后一个城市，则增加一行输出Game Over.。

题解

　　每次丢失一个节点后重新计算子图数量，如果增加了两个及以上的子图，说明这个节点的丢失改变了整个国家的连通性。

　　使用 BFS、DFS、并查集均能计算子图数量，并查集最优。

public class Main {

    // 邻接表存图
    // 使用 Set 处理重复输入
    static List<Set<Integer>> map;
    // 标记被攻占的城市，为 true 表示被攻占
    static boolean[] delete;

    public static void main(String[] args) throws IOException {
        int n = read(), m = read();
        union = new int[n];
        map = new ArrayList<>(n);
        delete = new boolean[n];
        for (int i = 0; i != n; ++i) map.add(new TreeSet<>());
        for (int i = 0; i != m; ++i) {
            int a = read(), b = read();
            map.get(a).add(b);
            map.get(b).add(a);
        }
        int last = count();
        int k = read();
        for (int i = 0; i != k; ++i) {
            int code = read();
            delete[code] = true;
            int next = count();
            // 注意输出结尾标点符号不一样
            if (next - last > 1)
                System.out.printf("Red Alert: City %d is lost!\n", code);
            else System.out.printf("City %d is lost.\n", code);
            last = next;
        }
        if (k == n)
            System.out.print("Game Over.");
    }

    static int[] union;

    static int count() {
        for (int i = 0; i != union.length; ++i) union[i] = i;
        for (int i = 0; i < map.size(); i++) {
            if (delete[i]) continue;
            int dist = find(i);
            for (int value : map.get(i)) {
                if (!delete[value])
                    union[value] = dist;
            }
        }
        int result = 0;
        for (int i = 0; i < union.length; i++) {
            if (find(i) == i) ++result;
        }
        return result;
    }

    static int find(int code) {
        return union[code] == code ? code : (union[code] = find(union[code]));
    }

    static int read() throws IOException {
        int result = 0;
        int input = System.in.read();
        do {
            result = (result << 1) + (result << 3) + (input ^ 48);
            input = System.in.read();
        } while (Character.isDigit(input));
        return result;
    }

}

单调栈

　　N 人们排队等着参加音乐会。人们等得很无聊，于是他们转身去排队寻找熟悉的人。

　　如果两个人 A 和 B 并排站在一起，或者如果他们中间没有人比 A 或 B 高，那么他们可以看到对方。

　　编写一个程序，确定可以看到彼此的成对人数。

输入格式

　　第一行输入包含一个整数 N（1 <= N <= 500000），排队的人数。

　　以下 N 行中的每一行都包含一个整数，即一个人的身高（以纳米为单位）。

　　每个人的身高都将小于 231 纳米。高度是按照人们排队的顺序给出的。

输出格式

　　输出可以看到对方的成对人数。

题解

　　我们仅计算每一个人能向左看到的人数，同时计算左右会重复计算。

　　理解题意后不难发现，如果一个人右边站了一个比他高的人，那么右边的人中除右边这一个人以外，所有人都无法看到他，所以一个人右边比他低的人计算后是可以直接删除掉的。

　　于是我们就形成了一个元素从栈底向栈顶单调递减的栈，也就是单调栈。同时注意两个等高的人站在一起是不影响可见度的，所以这是一个不严格单调递减的单调栈。

　　我们在一个人入栈和出栈时进行统计，就能算出能看到多少人。

　　当一个元素入栈时，有三种情况：

新元素比栈顶小，直接入栈，如果栈不为空则答案 +1（这个 +1 加的是相邻两个元素可以互相看见，所以如果入栈时栈为空就不能 +1）。
新元素与栈顶相等，直接入栈，答案加上与其相等的个数（这个加的是等高的人可以互相看见），同时如果去掉等高的人后栈中依然有人，答案还需再 +1（这个加的是新入栈的人能和左侧第一个不等高的人相互看见）。
新元素比栈顶小，将所有比新元素小的元素全部出栈，然后答案加上出栈人数（这个加的是出栈的人都能够和新入栈的相互看见），然后再按照规则 2 进行一次运算。

　　这里我们再考虑一下相邻等高元素的表达，真的是否需要重复入栈。答案是不需要，我们记录一下等高的人数即可，可以减少运算次数。

　　同时编写代码时可以进行一些逻辑上的优化，按照 3 2 1 的顺序进行运算，可以减少代码量。

public class Main {

    public static void main(String[] args) throws IOException {
        int n = read();
        long result = 0;
        // 使用双向队列模拟栈
        // Java 中不要使用 Stack 当作栈，Stack 是一个线程安全的类，基于 Vector 实现，效率很低，官方已经不再推荐使用该类
        Deque<Node> stack = new LinkedList<>();
        for (int i = 0; i != n; ++i) {
            int height = read();
            // 规则 3
            while (!stack.isEmpty()) {
                Node top = stack.getLast();
                if (top.height < height) {
                    // 本来这里是 +1，但是因为我们合并了相邻且等高的人，所以需要加 count
                    result += top.count;
                    stack.removeLast();
                } else break;
            }
            // 因为栈为空的时候没办法取元素，所以先特判一下，算是规则 1 的一部分
            if (stack.isEmpty()) stack.add(new Node(height));
            else {
                // 规则 2
                Node last = stack.getLast();
                if (last.height == height) {
                    result += last.count++;
                    if (stack.size() != 1) ++result;
                } else {
                    // 规则 1 的剩下一部分
                    stack.add(new Node(height));
                    ++result;
                }
            }
        }
        System.out.print(result);
    }

    static int read() throws IOException {
        int result = 0;
        int input = System.in.read();
        do {
            result = (result << 1) + (result << 3) + (input ^ 48);
            input = System.in.read();
        } while (Character.isDigit(input));
        return result;
    }

}

final class Node {

    // 身高
    int height;
    // 相邻且相等的人的数量
    int count = 1;

    Node(int height) {
        this.height = height;
    }

}

创作不易，扫描下方打赏二维码支持一下吧ヾ(≧▽≦*)o