当前位置： 首页 > article >正文

《从入门到精通：蓝桥杯编程大赛知识点全攻略》（十八）-倍数问题、距离

article 2025/2/23 19:11:04

前言

在算法学习过程中，我们经常遇到一些经典的问题，要求我们通过巧妙的算法设计来高效解决。这些问题不仅考验我们对数据结构和算法的理解，还帮助我们提高在实际场景中应用算法的能力。本篇博客将深入探讨两道涉及 倍数问题 和 距离计算问题 的算法题。通过分析这些问题的不同解法，我们可以更好地理解如何利用合适的数据结构和算法优化计算效率，解决复杂问题。

倍数问题

众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。
但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。
现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K
的倍数，且这个和最大。
数据保证一定有解。
输入格式
第一行包括 2 个正整数 n, K。
第二行 n 个正整数，代表给定的 n 个数。
输出格式
输出一行一个整数代表所求的和。
数据范围
1≤n≤105,
1≤K≤103,
给定的 n 个数均不超过 108
输入样例：

4 3
1 2 3 4

输出样例：

9

算法思路

在这里插入图片描述
数组arr：用来存储n个数
三位整型数组dp[i][j][k]：表示从前i个数且已经选了j个数且总和%K的余数为k的数的最大值。
初始化：

  • 对 dp 数组进行初始化，dp[i][j][k] = Integer.MIN_VALUE 表示无效状态，dp[i][0][0] = 0 表示没有选择任何数，和为 0 的状态下最大和为 0。

动态规划转移：

  • 遍历所有的元素，尝试选择和不选择当前元素。
  • 如果选择当前元素 arr[i]，那么更新状态 dp[i][j][k] 为：
    1. dp[i-1][j][k]：不选当前元素，保留前 i-1 个数时的状态。
    2. dp[i-1][j-1][(k - arr[i]) % K] + arr[i]：选当前元素，前 i-1 个数选择了 j-1 个数，且其和是 (k - arr[i]) % K 时的最大值。

最终的结果是从 dp[n][3][0] 中找出最大的值，即选择 3 个数，且它们的和是 K 的倍数时的最大和。
该算法的时间复杂度是 O(N * 3 * K)，其中 N 是元素个数，3 是子序列的选择个数（题目中固定选择3个数），K 是倍数的范围。（会超时）

优化后：
输入数据包含 n 个整数和一个整数 K，我们需要对这些整数进行分类。具体来说，根据每个数对 K 的取余值进行分类，将所有整数放到对应余数的桶中。

  • num 是一个长度为 K 的 ArrayList 数组，每个 num[i] 存放的是那些对 K 取余为 i 的数。
  • 对于每个输入的数 temp，我们将它放入 num[temp % K] 这个桶中。

在完成分类后，我们对每个余数桶中的数字进行降序排序。因为我们在后续的动态规划中需要获取这些余数桶中最大的数字来进行最大化计算。

  • 通过 Collections.sort() 对每个 num[i]（即每个余数桶中的数）进行降序排序，方便在后续的动态规划过程中尽可能选择较大的数。

二维数组 f，其中 f[j][k] 表示从前 j 个数中选择若干个数，且这些数的和对 K 取余为 k 时的最大和。
f[3][0] 最终存放的就是我们要找的结果——选择 3 个数且它们的和是 K 的倍数时的最大和。
初始化 f 数组时，我们设置所有值为 Integer.MIN_VALUE，表示那些不可能的状态。然后，我们将 f[0][0] 设为 0，表示没有选择任何数时，和为 0。

  • 对于每个数 x，我们尝试将它加入到已经选择的数中。对于每个选择的余数 k，我们通过计算 (k - x) % K 来确定新的余数，并更新状态 f[j][k]。
  • 状态转移公式为：f[j][k] = Math.max(f[j][k], f[j - 1][((k - x) % K + K) % K] + x)，表示我们选择当前数 x，更新了选择 j 个数，且其和对 K 取余为 k 时的最大和。

输出 f[3][0]，即选择 3 个数且它们的和是 K 的倍数时的最大和

代码如下

普通三位背包代码如下：


import java.io.*;
import java.util.Arrays;

public class 倍数问题 {
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static int N = 100010;
    static int M = 1000;
    static int[] arr = new int[N];
    static int[][][] dp = new int[N][5][M];
    static int n,K;
    public static void main(String[] args) throws Exception{
        n = nextInt();
        K = nextInt();
        for(int i = 1; i <= n; i++){
            arr[i] = nextInt();
        }
        for(int i = 0; i < N; i++){
            for(int j = 0; j < 5; j++){
                Arrays.fill(dp[i][j], Integer.MIN_VALUE);
            }
        }
        for(int i = 0;i <= n;i++){
            dp[i][0][0] = 0;
        }
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= 3;j++){
                for(int k = 0;k <= K;k++){
                    dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-1][((k-arr[i]) % K + K) % K] + arr[i]);
                }
            }
        }
        int res = 0;
        for(int i=1;i <= ;i++) {
            res=Math.max(res, dp[i][3][0]);
        }
        pw.println(res);
        pw.flush();
    }
    public static int nextInt()throws Exception{
        st.nextToken();
        return (int)st.nval;
    }
}

优化后：

import java.lang.reflect.Array;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int K = sc.nextInt();
        ArrayList<ArrayList<Integer>> num = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < 10010; i++) {
            num.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < n; i++) {
            int temp = sc.nextInt();
            num.get(temp % K).add(temp);
        }
        for (int i = 0; i < K; i++) {
            Collections.sort(num.get(i), new Comparator<Integer>() {
                public int compare(Integer i1, Integer i2) {
                    return i2 - i1;
                }
            });
        }
        // 输入处理完毕，并且按余数降序排序
        int[][] f = new int[4][1001];
        for (int i = 0; i < f.length; i++) {
            for (int j = 0; j < f[0].length; j++) {
                f[i][j] = Integer.MIN_VALUE;
            }
        }
        f[0][0]=0;
        for (int p = 0; p < 1001; p++) {
            for (int q = 0; q < Math.min(3, num.get(p).size()); q++) {
                int x = num.get(p).get(q);
                for (int j = 3; j >= 1; j--) {
                    for (int k = 0; k <= f[0].length-1; k++) {
                        f[j][k] = Math.max(f[j][k], f[j - 1][((k - x) % K + K) % K] + x);
                    }
                }
            }
        }
        System.out.println(f[3][0]);
    }

}

距离

给出 n 个点的一棵树，多次询问两点之间的最短距离。
注意：

  • 边是无向的。
  • 所有节点的编号是 1,2,…,n。

输入格式
第一行为两个整数 n 和 m。n 表示点数，m 表示询问次数；
下来 n−1 行，每行三个整数 x,y,k，表示点 x 和点 y 之间存在一条边长度为 k；
再接下来 m 行，每行两个整数 x,y，表示询问点 x 到点 y 的最短距离。
树中结点编号从 1 到 n。
输出格式
共 m 行，对于每次询问，输出一行询问结果。
数据范围
2≤n≤104,
1≤m≤2×104,
0<k≤100,
1≤x,y≤n
输入样例1：

2 2 
1 2 100 
1 2 
2 1

输出样例1：

100
100

输入样例2：

3 2
1 2 10
3 1 15
1 2
3 2

输出样例2：

10
25

算法思路

在这里插入图片描述
实现了一个基于树的 最近公共祖先（LCA） 算法，结合了深度优先搜索（DFS）和并查集（Union-Find）优化，通过离线查询方式来高效地计算任意两点之间的距离。
邻接表：h[], e[], w[], ne[] 作为图的邻接表表示，用于存储树的结构（即节点连接关系和边权重）。

  • h[]: 存储每个节点的邻接边的头节点索引。
  • e[]: 存储每条边的目标节点。
  • w[]: 存储边的权重。
  • ne[]: 存储每条边的下一个邻接边的索引。

dist[]：记录节点到根节点（节点 1）的距离。
p[]：并查集数组，用于维护并查集结构，处理LCA查询时的合并和路径压缩操作。
st[]：用于标记节点的状态，分为三种状态：0（未搜索）、1（正在搜索）、2（已搜索并回溯）。
query[]：存储每个节点的查询列表，记录每个节点的查询请求。
DFS 计算 dist[]

  • 通过 DFS 从根节点开始遍历树，计算每个节点到根节点的距离（dist[]）。这是通过递归的方式完成的，对于每条边的遍历，累加权重，并保证不往回走。

Tarjan 算法：通过 DFS 遍历整棵树，利用并查集结合回溯的方式离线处理 LCA 查询。具体步骤如下：

  • 对于每个节点 node，标记其为正在搜索状态（st[node] = 1）。
  • 遍历与当前节点相连的所有子节点，对于未搜索的子节点递归调用 tarjan()。
  • 在搜索完子节点后，将子节点合并到父节点，即 p[j] = node，表示子节点的祖先是当前节点。
  • 对于当前节点的查询列表 query[node]，逐一处理查询：
    • 对于每个查询 (y, id)，如果 y 已经回溯过（st[y] == 2），则可以确定 node 和 y 的最近公共祖先。
    • 使用 find(y) 查找 y 的祖先节点，通过 LCA 的定义，计算 dist[node] + dist[y] - dist[anc] * 2，得到两点之间的距离。
  • 标记当前节点为已搜索并回溯状态（st[node] = 2）。

最后遍历所有的查询结果 res[]，输出每个查询的结果，即节点 a 和节点 b 之间的距离。
并查集操作

  • 路径压缩：通过 find() 函数来实现路径压缩优化，查找祖先时递归地将路径上的每个节点直接连接到其祖先节点，从而加速后续的查询。

add(a, b, c)：向邻接表中添加一条边，表示节点 a 和 b 之间的边，边的权重为 c。
find(x)：并查集的查找操作，带路径压缩。
dfs(node, dad)：深度优先搜索，用于计算每个节点的 dist[] 数组。
tarjan(node)：Tarjan 算法核心函数，通过离线方式计算节点的 LCA，并处理所有查询。

代码如下

import java.io.*;
import java.util.*;
public class Main 
{
    static final int N = 10010, M = N * 2;
    static int h[] = new int[N], e[] = new int[M], w[] = new int[M], ne[] = new int[M], idx; //邻接表
    static int dist[] = new int[N]; //dist[i]：节点i到根节点（1号点）的距离
    static int p[] = new int[N]; //并查集
    static int st[] = new int[N]; //st[i]：0：还未搜索过节点i 1：正在搜索节点i这条分支 2：已经搜索且回溯过节点i
    static int res[] = new int[M]; //res[i]：编号为i的查询结果
    static List<PII> query[] = new List[N]; //所有查询
    static int n, m;

    public static void main(String[] args) throws IOException
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str1[] = in.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);

        //初始化h[]
        Arrays.fill(h, -1);

        //初始化query[]
        for(int i = 0; i < N; i ++)
            query[i] = new ArrayList<PII>();

        //初始化p[]
        for(int i = 1; i < N; i ++)
            p[i] = i;

        //读取n - 1条边
        for(int i = 0; i < n - 1; i ++)
        {
            String str2[] = in.readLine().split(" ");
            int a = Integer.parseInt(str2[0]);
            int b = Integer.parseInt(str2[1]);
            int c = Integer.parseInt(str2[2]);

            add(a, b, c);
            add(b, a, c);
        }

        //读取m次询问
        for(int i = 0; i < m; i ++)
        {
            String str3[] = in.readLine().split(" ");
            int a = Integer.parseInt(str3[0]);
            int b = Integer.parseInt(str3[1]);

            if(a != b) //当a = b时答案为0 可不加
            {
                query[a].add(new PII(b, i));
                query[b].add(new PII(a, i));
            }
        }

        //计算dist[]
        dfs(1, -1);

        //离线求LCA
        tarjan(1);

        //遍历res[0 ~ m] 输出每个询问结果
        for(int i = 0; i < m; i ++)
            System.out.println(res[i]);
    }

    //邻接表加边操作
    public static void add(int a, int b, int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }

    //并查集 查找祖先 + 路径压缩
    public static int find(int x)
    {
        if(p[x] != x)
            p[x] = find(p[x]);

        return p[x];
    }

    //遍历整棵树 计算dist[]
    public static void dfs(int node, int dad)
    {
        //遍历节点node的所有边
        for(int i = h[node]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(j != dad) //不是往回走
            {
                dist[j] = dist[node] + w[i];
                dfs(j, node);
            }
        }
    }

    //遍历整棵树 离线求LCA
    public static void tarjan(int node)
    {
        st[node] = 1; //更新节点node的状态：正在搜索节点node这条分支

        //遍历节点node的所有边
        for(int i = h[node]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(st[j] == 0) //还未搜索过节点j
            {
                tarjan(j);
                p[j] = node; //节点j后续已不可能作为最近公共祖先 后续所有关于节点j的询问的最近公共祖先都至少是父节点node 将节点i并入父节点node
            }
        }

        //遍历关于节点node的所有询问
        for(PII item : query[node])
        {
            int y = item.node, id = item.id; //y：另一个点 id：询问编号

            if(st[y] == 2) //已经搜索且回溯过节点y 可确定最近公共祖先
            {
                int anc = find(y); //找到节点node和节点y的最近公共祖先
                res[id] = dist[node] + dist[y] - dist[anc] * 2; //计算两点之间的距离
            }
        }

        st[node] = 2; //更新节点node的状态：已经搜索且回溯过节点node
    }
}

class PII
{
    int node, id;

    PII(int node, int id)
    {
        this.node = node;
        this.id = id;
    }
}

总结

希望通过这篇博客，你能获得一些有价值的思路和技巧，继续提升自己在算法与编程方面的能力。


http://www.kler.cn/a/557889.html

相关文章：

  • MySQL | MySQL库、表的基本操作01
  • 如何对比软件需求做的是否合格？
  • nlp 自然语言处理+bert model +问答系统 question answer system(python 完整代码)
  • 豪越科技消防安全重点单位管理：从传统到数字化的跨越
  • (java/Spring boot)使用火山引擎官方推荐方法向大模型发送请求
  • editor.md编辑器，图片跨域上传，前后端分离
  • 洛谷 P1102 A-B 数对（详解）c++
  • C++——list模拟实现
  • 某生产制造集团管理流程优化项目成功案例纪实
  • QQ登录测试用例报告
  • uniapp小程序自定义日历(签到、补签功能)
  • 助力DeepSeek私有化部署服务：让企业AI落地更简单、更安全
  • 线性模型 - Softmax 回归
  • 每日一题——验证IP地址
  • 使用pyinstaller对gradio和chromadb进行打包
  • AI大模型-提示工程学习笔记13—自动提示工程师 (Automatic Prompt Engineer)
  • 数据结构、算法和STL简介 【复习笔记】
  • C++/JavaScript ⭐算法OJ⭐下一个排列
  • SAP任命Simon Davies为亚太区总裁，领导重组后的亚太地区业务
  • 第15届 蓝桥杯 C++编程青少组中/高级选拔赛 202401 真题答案及解析