跳至主要內容

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

大约 15 分钟

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

T1. 新生【算法赛】

问题描述

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

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

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

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

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

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

输入格式

无。

输出格式

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

参考实现

解题思路

略。

参考代码

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×32\times 3 规格的地砖，小蓝家的地板是 n×mn\times m 规格的，小蓝想问你，能否用这些 2×32\times 3 的地砖铺满地板。

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

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

图片描述
图片描述

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

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

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

输入格式

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

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

输出格式

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

样例输入

4
7 6
2 2
12 8
1 12

样例输出

Yes
No
Yes
No

说明

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

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

祝大家 10241024 快乐。

评测数据范围

1≤T≤104,1≤n,m≤1041\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. 摆玩具【算法赛】

问题描述

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

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

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

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

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

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

输入格式

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

第二行输入 nn 个整数 {h1,h2,...,hn}\lbrace h_1,h_2,...,h_n\rbrace，代表每个玩具的高度。

输出格式

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

样例输入

5 2
2 5 7 10 13

样例输出

8

说明

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

  1. {2}∣{5,7,10,13}\lbrace 2\rbrace |\lbrace 5,7,10,13\rbrace，极差和为 0+8=80 + 8 = 8。
  2. {2,5,7}∣{10,13}\lbrace 2,5,7\rbrace |\lbrace 10,13\rbrace，极差和为 5+3=85 + 3 = 8。
  3. {2,5,7,10}∣{13}\lbrace 2,5,7,10\rbrace |\lbrace 13\rbrace，极差和为 8+0=88 + 0 = 8。

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

评测数据范围

1≤k≤n≤1051\le k\le n\le 10^5 。

1≤h1≤h2≤h3≤...≤hn≤1091\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. 通关【算法赛】

问题描述

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

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

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

输入格式

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

接下来 nn 行，每行输入三个整数 fi,si,kif_i, s_i, k_i，fif_i 表示每一关的前置关卡（ f1f_1 一定为 00 ），sis_i 表示经验值，kik_i 表示挑战成功最少需要的经验值。

输出格式

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

样例输入

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

样例输出

3

说明

游戏地图如下：

关卡描述
关卡描述

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

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

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

  2. 此时经验为 88，满足 22 号关卡要求，但是不满足 33 号要求，所以可以直接挑战成功 22 号关卡，获得 22 经验值，此时经验值为 1010。

  3. 此时经验为 1010，满足 33 号关卡要求，所以对 33 号关卡挑战成功，获得 33 经验值，此时经验值为 1313，并且获得挑战 44 号关卡的机会。

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

评测数据范围

f1=0<fi≤n≤105,0≤P,si,ki≤109f_1 = 0\lt f_i\le n\le 10^5, 0\le P,s_i,k_i\le 10^9。

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

参考实现

解题思路

堆/优先队列。

维护一个小根堆，每个节点维护两个值：节点编号和节点需要的经验值，以经验值为关键字建立堆，通过节点 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. 串门【算法赛】

问题描述

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

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

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

输入格式

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

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

输出格式

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

样例输入

4
1 2 3
1 3 4
1 4 5

样例输出

15

说明

路径为：4→51→32→31→434\overset{5}{\to} 1\overset{3}{\to} 2\overset{3}{\to} 1\overset{4}{\to} 3，路径和值为 1515。

评测数据范围

1≤n≤105,1≤vi,ui≤n,1≤wi≤1091\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. 神奇数【算法赛】

问题描述

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

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

例如 453453 就是神奇数，因为 4+5=94+5=9，99 对 33 取模为 00。

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

输入格式

第一行输入一个整数 ll。

第二行输入一个整数 rr。

输出格式

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

样例输入

100
130

样例输出

5

说明

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

评测数据范围

10≤l≤r≤1020010\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. 小蓝的疑问【算法赛】

问题描述

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

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

我们称节点 vv 为 xx 的 kk 层子节点满足：

  1. vv 是 xx 为根的子树中的节点。
  2. depv−depx=kdep_v - dep_x = k，depvdep_v 为 vv 在树中的深度。

例如：

k层
k层

{2,3}\lbrace 2,3\rbrace 为 11 号点的 11 层子节点，{4,5,6,7}\lbrace 4,5,6,7\rbrace 为 11 号点的 22 层子节点，{4,6}\lbrace 4,6\rbrace 为 22 号点的 11 层子节点。

输入格式

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

第二行输入 nn 个正整数 w1,w2,...,wnw_1,w_2,...,w_n，表示每个点的权值。

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

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

输出格式

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

样例输入

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
shuom

评测数据范围

1≤vi,ui,k,x≤n≤105,1≤wi≤109,1≤q≤1051\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。

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

参考实现

解题思路

考察数据结构（堆、线段树），图（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();
    }
}

（全文完）

Copyright © 2018-2023 gdut-yy