「蓝桥」1024 第 2 场算法双周赛

• 比赛时间：2023-10-24 19:00 ~ 21:00。
• 比赛链接：https://www.lanqiao.cn/oj-contest/challenge-2/
• 题解回放：https://www.bilibili.com/video/BV19u4y1a7rc/

T1. 新生【算法赛】

问题描述

新一届蓝桥杯大赛即将在 $2024$ 年拉开序幕！

作为大一新生的小蓝，在听说了这场盛大的比赛后，对其充满了期待与热情。但作为初次参赛的新手，他对蓝桥杯的相关赛制和历史并不了解。于是，他决定寻求上届蓝桥杯总冠军小桥的指导。

小桥的实力不容小觑，她只参加过一次蓝桥杯，就斩获了第 $14$ 届的总冠军。

小桥可以指导小蓝，但她要先确认小蓝对蓝桥杯的热爱是否真挚。于是她向小蓝提出了一个问题：即将开始的蓝桥杯是第几届的。

作为新生的小蓝自然不知道答案，因此请你帮助小蓝回答这个问题。

注意：请使用阿拉伯数字表示答案。

输入格式

无。

输出格式

输出一个整数，表示答案。

参考实现

解题思路

略。

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println(solve());
    }

    private static String solve() {
        return "15";
    }
}

T2. 铺地板【算法赛】

问题描述

小蓝家要装修了，小蓝爸爸买来了很多块（你可以理解为数量无限）$2\times 3$ 规格的地砖，小蓝家的地板是 $n\times m$ 规格的，小蓝想问你，能否用这些 $2\times 3$ 的地砖铺满地板。

铺满地板：对于地板的每个区域，都有且只有一块地砖覆盖，地砖可以旋转，但不能切割。

例如：对于 $7\times 6$ 的地板，一种铺地板方式是：

图片描述

当然，也存在其他别的铺法。

小蓝家是个多层小别墅，每一层的规格不一样，所以他会多次询问你不同规格的地板。

注意：请仔细读题，不要弄混地板和地砖。

输入格式

第一行输入一个整数 $T$，代表询问数量。

接下来 $T$ 行，每行两个正整数 $n_i,m_i$，代表小蓝询问的地板规格。

输出格式

对于每次询问，如果 $2\times 3$ 的地砖可以铺满地板，输出 Yes，否则输出 No。

样例输入

4
7 6
2 2
12 8
1 12

样例输出

Yes
No
Yes
No

说明

• 对于第一组询问，题干中存在正确铺法。
• 对于第二组询问，不存在任何铺法可以铺满。

作为一个程序员，应该有 $666$ 分的勇气。如果你觉得这是一个简单得很 $6$ 的结论，但是你不知道如何证明，不妨提交一发试一试。

祝大家 $1024$ 快乐。

评测数据范围

$1\le T\le 10^4, 1\le n,m\le 10^4$。

参考实现

解题思路

猜结论/分类讨论：

1、n * m 不是 6 的倍数，不能铺满；
2、如果是 6 的倍数，并且 n 是 2 的倍数，m 是 3 的倍数，可以铺满（或者反过来）；
3、如果 n 既不是 2 也不是 3 的倍数，那么说明 m 一定是 6 的倍数，那么只要 n > 1，即可铺满。

总结：如果 n * m 是 6 的倍数，并且 n > 1 并且 m > 1，就是合法的。

参考代码

import java.util.Scanner;

public class Main {
    static int n, m;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            n = scanner.nextInt();
            m = scanner.nextInt();
            System.out.println(solve());
        }
    }

    private static String solve() {
        boolean ans = n * m % 6 == 0 && (n > 1 && m > 1);
        return ans ? "Yes" : "No";
    }
}

T3. 摆玩具【算法赛】

问题描述

小蓝是一个热爱收集玩具的小伙子，他拥有 $n$ 个不同的玩具。

这天，他把 $n$ 个玩具按照高度顺序从矮到高摆放在了窗台上，然后，他希望将这些玩具分成 $k$ 个段，使得所有分段的极差之和尽可能小。

具体来说，你需要将一个长度为 $n$ 的序列分为 $k$ 段，我们定义 $G_i$ 为第 $i$ 个分段的极差，你要最小化 $\sum _{i=1} ^k G_i$。

你能帮助小蓝找到最小值是多少吗？

极差：是指每个分段中最高和最矮玩具高度之差，例如有一段为：$\lbrace 3,6,10,12\rbrace$，那么极差为 $12-3=9$。

分段：即每一段在原始序列中是一段连续区间，例如将 $\lbrace 1,2,3,4,5\rbrace$ 分为两段，$\lbrace 1,2,3\rbrace |\lbrace 4,5\rbrace$ 是合法的，但是 $\lbrace 1,2,4\rbrace |\lbrace 3,5\rbrace$ 不是合法的。

输入格式

第一行输入两个整数 $n, k$，代表玩具数量和需要分段的数量。

第二行输入 $n$ 个整数 $\lbrace h_1,h_2,...,h_n\rbrace$，代表每个玩具的高度。

输出格式

输出一个整数，表示最小的极差和。

样例输入

5 2
2 5 7 10 13

样例输出

8

说明

存在多种分段方式，其结果都是最小值：

1. $\lbrace 2\rbrace |\lbrace 5,7,10,13\rbrace$，极差和为 $0 + 8 = 8$。
2. $\lbrace 2,5,7\rbrace |\lbrace 10,13\rbrace$，极差和为 $5 + 3 = 8$。
3. $\lbrace 2,5,7,10\rbrace |\lbrace 13\rbrace$，极差和为 $8 + 0 = 8$。

不存在其他方案使得答案小于 $8$。

评测数据范围

$1\le k\le n\le 10^5$ 。

$1\le h_1\le h_2\le h_3\le ...\le h_n\le 10^9$ 。

参考实现

解题思路

贪心。

在不分组的情况下，极差是 (h[n] - h[1])，可以等价于 (h[2] - h[1]) + (h[3] - h[2]) + (h[4] - h[3]) + ... + (h[n] - h[n-1])，分出一个组，等价于取出一个 (h[i] - h[i-1])，去掉 k-1 个最大值即可。

参考代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n, k;
    static int[] h;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        k = scanner.nextInt();
        h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = scanner.nextInt();
        }
        System.out.println(solve());
    }

    private static String solve() {
        long ans = 0;
        int[] diff = new int[n];
        for (int i = 1; i < n; i++) {
            diff[i] = h[i] - h[i - 1];
            ans += diff[i];
        }
        Arrays.sort(diff);

        for (int i = 0; i < k - 1; i++) {
            ans -= diff[n - 1 - i];
        }
        return String.valueOf(ans);
    }
}

T4. 通关【算法赛】

问题描述

小蓝最近迷上了一款电玩游戏“蓝桥争霸”。这款游戏由很多关卡和副本组成，每一关可以抽象为一个节点，整个游戏的关卡可以抽象为一棵树形图，每一关会有一道算法题，只有当经验值不低于第 $i$ 关的要求 $k_i$ 时，小蓝才能挑战成功通过此关，并且获得 $s_i$ 的经验值，每关的经验值只能获得一次。每个关卡（除了 $1$ 号点），都会有一个前置关卡，只有通过了前置关卡，才能挑战后续关卡。

小蓝初始在 $1$ 号点，也就是游戏开局初始点，同时具有一个初始经验值 $P$，他可以任意规划挑战顺序，他想问你最多能够挑战成功多少道题。

小蓝会告诉你关卡的所有信息，以及他的初始经验值，你需要回答他最多能够挑战成功多少关卡。

输入格式

第一行输入两个整数 $n,P$，表示关卡的数量以及小蓝的初始经验值。

接下来 $n$ 行，每行输入三个整数 $f_i, s_i, k_i$，$f_i$ 表示每一关的前置关卡（ $f_1$ 一定为 $0$ ），$s_i$ 表示经验值，$k_i$ 表示挑战成功最少需要的经验值。

输出格式

一个整数，表示在最优的规划下，最多能挑战成功的关卡数量。

样例输入

4 5
0 3 5
1 2 8
1 3 9
3 1 15

样例输出

3

说明

游戏地图如下：

关卡描述

小蓝初始点在 $1$ 号关卡，初始经验为 $5$。每个关卡具有挑战前提：$1$ 号关卡可以直接挑战，如果要挑战 $2$ 号关卡，必须通过 $1$ 号关卡，$3,4$号关卡类似。

小蓝的一种挑战顺序如下：

1. 由于初始经验为 $5$，满足 $1$ 号关卡要求，所以可以直接挑战成功 $1$ 号关卡，获得 $3$ 经验值，此时经验值为 $8$，并且获得挑战 $2,3$ 号关卡的机会。

2. 此时经验为 $8$，满足 $2$ 号关卡要求，但是不满足 $3$ 号要求，所以可以直接挑战成功 $2$ 号关卡，获得 $2$ 经验值，此时经验值为 $10$。

3. 此时经验为 $10$，满足 $3$ 号关卡要求，所以对 $3$ 号关卡挑战成功，获得 $3$ 经验值，此时经验值为 $13$，并且获得挑战 $4$ 号关卡的机会。

4. 此时经验为 $13$，小于 $4$ 号关卡要求，所以无法成功挑战 $4$ 号关卡，游戏无法继续。

评测数据范围

$f_1 = 0\lt f_i\le n\le 10^5, 0\le P,s_i,k_i\le 10^9$。

数据保证输入为一棵树，并且根节点为 $1$。

参考实现

解题思路

堆/优先队列。

维护一个小根堆，每个节点维护两个值：节点编号和节点需要的经验值，以经验值为关键字建立堆，通过节点 u 后，将 u 的所有直系儿子放入堆，每次取出堆顶尝试，成功后完成获得奖励经验，并且将该节点的后继节点加入小根堆中。如此反复即可。

参考代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static int n, p;
    static int[][] fsk;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        p = scanner.nextInt();
//        fsk = new int[n][3];
//        for (int i = 0; i < n; i++) {
//            fsk[i][0] = scanner.nextInt();
//            fsk[i][1] = scanner.nextInt();
//            fsk[i][2] = scanner.nextInt();
//        }

        g = new ArrayList[n + 1];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int i = 1; i <= n; i++) {
            int f = scanner.nextInt();
            int s = scanner.nextInt();
            int k = scanner.nextInt();
            // f->i
            g[f].add(new int[]{i, s, k});
        }
        System.out.println(solve());
    }

    static List<int[]>[] g;

    private static String solve() {
        // i,s,k
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        minHeap.addAll(g[0]);
        long exp = p;
        int ans = 0;
        while (!minHeap.isEmpty()) {
            int[] tuple = minHeap.remove();
            int y = tuple[0], s = tuple[1], k = tuple[2];
            if (exp >= k) {
                exp += s;
                minHeap.addAll(g[y]);
                ans++;
            }
        }
        return String.valueOf(ans);
    }
}

T5. 串门【算法赛】

问题描述

过年了，小蓝想要回家串门。

蓝桥村可以抽象为 $n$ 个节点， $n-1$ 条边的一棵树，每条边有边权长度 $w_i$。

小蓝可以选择任意一个点作为起点，然后选择一条路径，可以访问每个节点至少一次。他想知道最短的路径长度是多少。

输入格式

第一行输入一个整数 $n$，表示节点数量。

接下来 $n-1$ 行，每行三个整数 $v_i,u_i,w_i$，表示 $(v_i,u_i)$ 存在一条 $w_i$ 的边。

输出格式

输出一个整数，表示最短路径。

样例输入

4
1 2 3
1 3 4
1 4 5

样例输出

15

说明

路径为：$4\overset{5}{\to} 1\overset{3}{\to} 2\overset{3}{\to} 1\overset{4}{\to} 3$，路径和值为 $15$。

评测数据范围

$1\le n\le 10^5,\quad 1\le v_i,u_i\le n,\quad 1\le w_i\le 10^9$。

保证输入数据是一棵树。

参考实现

解题思路

树形 DP。

结论：
1、从起点到终点的最短路上的边，只需要经过一次；
2、其他边，都需要至少两次；
我们利用容斥，假设每条边都需要访问两次，那么我们减去只需要访问一次的，就是结果。

所以实际上就是求树的直径。

参考代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int n;
    static List<int[]>[] g;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        g = new ArrayList[n + 1];
        Arrays.setAll(g, e -> new ArrayList<>());
        tot = 0;
        for (int i = 0; i < n - 1; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            g[u].add(new int[]{v, w});
            g[v].add(new int[]{u, w});
            tot += w * 2;
        }
        System.out.println(solve());
    }

    static long[] dist;
    static long treeD;
    static long tot;

    private static String solve() {
        treeD = 0;
        dist = new long[n + 1];
        dfs(1, 0);
        long ans = tot - treeD;
        return String.valueOf(ans);
    }

    static void dfs(int x, int fa) {
        for (int[] tuple : g[x]) {
            int y = tuple[0], wt = tuple[1];
            if (y != fa) {
                dfs(y, x);
                treeD = Math.max(treeD, dist[x] + dist[y] + wt);
                dist[x] = Math.max(dist[x], dist[y] + wt);
            }
        }
    }
}

T6. 神奇数【算法赛】

问题描述

我们定义神奇数：一个长度为 $n$ 的十进制数 $S_1S_2...S_n$，且不包含前导 $0$，满足以下条件：

1. $n\ge 2$。
2. $S_n\gt 0$。
3. $\sum _1 ^{n-1} S_i $ 对 $S_n$ 取模等于 $0$。

例如 $453$ 就是神奇数，因为 $4+5=9$，$9$ 对 $3$ 取模为 $0$。

小蓝问你区间 $[l, r]$ 中，有多少神奇数。你需要回答他这个问题，由于答案可能会很大，答案请对 $998244353$ 取模。

输入格式

第一行输入一个整数 $l$。

第二行输入一个整数 $r$。

输出格式

输入一个整数，代表区间内神奇数的数量，答案对 $998244353$ 取模。

样例输入

100
130

样例输出

5

说明

如下整数为神奇数：$\lbrace 101, 111, 112, 121, 123\rbrace$。

评测数据范围

$10\le l\le r\le 10^{200}$ 。

参考实现

解题思路

数位 DP。

枚举最后一位是多少。

参考代码

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static String l, r;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        l = scanner.next();
        r = scanner.next();
        System.out.println(solve());
    }

    private static String solve() {
        l = new BigInteger(l).subtract(BigInteger.ONE).toString();
        long ans1 = 0, ans2 = 0;
        for (int i = 1; i <= 9; i++) {
            last = i;
            ans1 = (ans1 + count(l)) % MOD;
            ans2 = (ans2 + count(r)) % MOD;
        }
        long ans = ((ans2 - ans1) % MOD + MOD) % MOD;
        return String.valueOf(ans);
    }

    static final int MOD = 998244353;
    static char[] s;
    static long[][] dp;
    static int last;

    static long count(String num) {
        s = num.toCharArray();
        int n = num.length();
        dp = new long[n][last];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        return f(0, 0, true, false);
    }

    static long f(int i, int remain, boolean isLimit, boolean isNum) {
        if (i == s.length - 1) {
            if (!isNum) return 0;
            int up = isLimit ? s[i] - '0' : 9;
            return (last <= up && remain % last == 0) ? 1 : 0;
        }
        if (!isLimit && isNum && dp[i][remain] != -1) {
            return dp[i][remain];
        }
        long ans = 0L;
        if (!isNum) {
            ans += f(i + 1, remain, false, false);
            ans %= MOD;
        }
        int down = isNum ? 0 : 1;
        int up = isLimit ? s[i] - '0' : 9;
        for (int d = down; d <= up; d++) {
            ans += f(i + 1, (remain + d) % last, isLimit && d == up, true);
            ans %= MOD;
        }
        if (!isLimit && isNum) {
            dp[i][remain] = ans;
        }
        return ans;
    }
}

T7. 小蓝的疑问【算法赛】

问题描述

小蓝和小桥上完课后，小桥回顾了课上教的树形数据结构，他在地上画了一棵根节点为 $1$ 的树，并且对每个节点都赋上了一个权值 $w_i$。

小蓝对小桥多次询问，每次询问包含两个整数 $x, k$，表示询问节点为 $x$ 的所有 $k$ 层子节点中，最大值是多少。

我们称节点 $v$ 为 $x$ 的 $k$ 层子节点满足：

1. $v$ 是 $x$ 为根的子树中的节点。
2. $dep_v - dep_x = k$，$dep_v$ 为 $v$ 在树中的深度。

例如：

k层

$\lbrace 2,3\rbrace$ 为 $1$ 号点的 $1$ 层子节点，$\lbrace 4,5,6,7\rbrace$ 为 $1$ 号点的 $2$ 层子节点，$\lbrace 4,6\rbrace$ 为 $2$ 号点的 $1$ 层子节点。

输入格式

第一行输入两个正整数 $n,q$，表示树的节点数量和询问数量。

第二行输入 $n$ 个正整数 $w_1,w_2,...,w_n$，表示每个点的权值。

接下来 $n-1$ 行，每行输入两个整数 $v_i,u_i$，表示存在一条由 $v_i$ 指向 $u_i$ 的边。

接下来 $q$ 行，每行输入两个整数 $x,k$，表示询问 $x$ 的 $k$ 层子节点中，最大值是多少。

输出格式

输出 $q$ 行，每行输出一个整数，表示每个询问的最大值。

样例输入

7 4
2 9 8 7 8 6 4
1 2
1 3
2 4
2 6
3 5
3 7
1 2
1 1
3 1
2 1

样例输出

8
9
8
7

说明

样例如下图：

shuom

评测数据范围

$1\le v_i,u_i,k, x\le n\le 10^5, 1\le w_i\le 10^9, 1\le q\le 10^5$。

数据保证是一棵以 $1$ 为根的有向树，并且每次询问的 $k$ 一定合法。

参考实现

解题思路

考察数据结构（堆、线段树），图（DFS 序），二分查找

1、离线做法，启发式合并 + 优先队列，同时对于每层的节点都维护一个大根堆，每次询问，查询堆中最大值。时间复杂度：O(nloglogn)。
2、在线做法，DFS 序 + 线段树（ST 表） + 二分查找，对每层按照 DFS 序相对顺序建立线段树（或者 ST 表），当查询到 u 时，通过二分找到 k 层的左右端点，查询最大值。时间复杂度：O(nlogn)。

参考代码

官方提供的标程：

import java.util.*;
import java.lang.Math;

class RMQ {
    private int[][] f;
    private final int N, LOGN;

    public RMQ(ArrayList<Integer> init) {
        N = init.size();
        LOGN = (int) (Math.log(N) / Math.log(2)) + 1;
        f = new int[LOGN][N];
        for (int i = 0; i < N; i++) {
            f[0][i] = init.get(i);
        }
        for (int i = 1; i < LOGN; i++) {
            for (int j = 0; j + (1 << i) - 1 < N; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    public int query(int l, int r) {
        int k = (int) (Math.log(r - l) / Math.log(2));
        return Math.max(f[k][l], f[k][r - (1 << k)]);
    }
}

public class std {
    static final int N = 100005;
    static ArrayList<Integer>[] G = new ArrayList[N];
    static ArrayList<Integer>[] val = new ArrayList[N];
    static ArrayList<Integer>[] dfsQ = new ArrayList[N];
    static int[] w = new int[N];
    static int n, q;
    static int DFN = 0;
    static int[] dfn = new int[N];
    static int[] dep = new int[N];
    static int[] Siv = new int[N];
    static int MaxDpt = 0;
    static RMQ[] res = new RMQ[N];

    public static void dfs(int u, int fa, int dpt) {
        MaxDpt = Math.max(MaxDpt, dpt);
        dfn[u] = ++DFN;
        dep[u] = dpt;
        Siv[u] = 1;
        val[dpt].add(w[u]);
        dfsQ[dpt].add(dfn[u]);
        for (int v : G[u]) {
            if (v == fa) continue;
            dfs(v, u, dpt + 1);
            Siv[u] += Siv[v];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        q = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
        }
        for (int i = 0; i < N; i++) {
            G[i] = new ArrayList<>();
            val[i] = new ArrayList<>();
            dfsQ[i] = new ArrayList<>();
        }
        int u, v, x, k;
        for (int i = 1; i < n; i++) {
            u = sc.nextInt();
            v = sc.nextInt();
            G[u].add(v);
            G[v].add(u);
        }
        dfs(1, 0, 1);
        for (int i = 1; i <= MaxDpt; i++) {
            res[i] = new RMQ(val[i]);
        }
        while (q-- > 0) {
            x = sc.nextInt();
            k = sc.nextInt();
            int l = Collections.binarySearch(dfsQ[k + dep[x]], dfn[x]);
            int r = Collections.binarySearch(dfsQ[k + dep[x]], dfn[x] + Siv[x]);
            if (l < 0) l = (-l) - 1;
            if (r < 0) r = (-r) - 1;
            System.out.println(res[k + dep[x]].query(Math.abs(l), Math.abs(r)));
        }
        sc.close();
    }
}

（全文完）