第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP?

这篇具有很好参考价值的文章主要介绍了第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

                                                                                 🍏🍐🍊🍑🍒🍓🫐🥑🍋🍉🥝

                                              第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP          

时间:🍏2023年4月28日09:32:16 此题属于线性DP问题(正确题解附在文末),由于位置存储的难度,此题不再考虑dijkstra。

时间:🍏2023年4月11日10:28:22发现问题,致歉大家,我的纵坐标存储方式是错误的,但是总体思路没问题。🍑错误原因:
   今天突然发现了一个问题,我存储的纵坐标的方式的错误的,按照之前发的题解我是这样来存储的:x + N + y,我记错了,应该是x * N + y,为什么是错误的呢?
   首先,N是横纵坐标中最值较大的那一个,那么在此题,很明显是xi,它最大是1
e9,而纵坐标ai、bi只有1e4,那么此时N就是1e9,而x * N + y的最大就是1e18+1e4。显然超出了数组的容量,当时没注意,误把N看作是站点个数1e5了,所以想到了这样的办法。给大家说声抱歉。

   这样做有什么好处呢?这样可以把二维坐标用一维来存,什么原理?令index = x * N + y;那么x = index / N;y = index % N;确实好用,但是此题数据范围过大,如果这样存储不能过全部样例
   当时没做出来也是不知道怎么存储纵坐标,所以我还是认为此题难在如何存储传送门的位置,因为传送门的位置是二维的,如果开二维数组,在编译的时候一样的堆溢出的,很懊恼,看看之后有没有其他大神的题解吧。



🍋前言

🍐小伙伴们大家好,好久没更新文章了,最近一直在准备蓝桥杯。为什么我要先发这道题的题解呢?不是因为我当时做出来了,而是因为我当时大意了没做出来。如果这道题的纵坐标存好了或许还有机会,说多了都是泪…唉,一言难尽。话不多说,先看解析吧!

🍋题目描述

第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP?

第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP?
第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP?

🍐没看懂题意?看到“传送门”“魔法蜗牛”怕了吗,哈哈哈哈哈哈哈哈哈! 来,我手把手教你用魔法打败魔法。咱们先来捋捋题目到底是啥意思,看个图↓
第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP?

🍋解题思路

🍐图中方框代表传送门,箭头线代表可走的路径,注意,这些路线都是有方向的。我们可以把所有的位置看作是一个一个的站点,题意就变为了从原点出发,到终点的最短时间,而这个时间就等同于我们最短路径问题的距离。(还是不清楚怎么走的同学,可以配合着我的图画,看看在图片最后的坐标走向是怎么样的。

🍐这道题的难点之一在于如何存储杆子上传送门的位置,通过思考我们可以得知,杆子的位置与杆子的横坐标有关,与传送门的纵坐标有关,我当时太笨了,用了一个类去存,结果在写链式前向星的时候人傻了… 正确的做法是y = idx(杆子的横坐标)+ N(最大站点数目) + ai(传送门的高度) ,这样可以保证传送门的位置是唯一确定的,如果不加N,有可能会与后面的杆子位置重复。

🍐站点位置存好了,那边呢?一共就这么几种边:①水平边,水平边很好办,枚举前n-1个杆子的位置,距离(时间)就是横坐标相减,建立起来就好。②竖直边,传送门与地面的距离,这个刚才说了,注意一点,他们的距离不是直接写高度,上去和下来的速度是不一样的,于是我们有:

static double levelTime = 1.0, downTime = 1.0 / 1.3, upTime = 1.0 / 0.7;

🍐levelTime 表示水平的单位时间,downTime 表示下落的单位时间,upTime 表示爬上杆子的单位时间。③传送门的边,这个边很特殊,因为是瞬移,所以权值为0。


🍋Code分析

🍋我们不妨先看看用例范围:1e5?标准的dijkstra堆优化链式前向星建图时间复杂度是O(n logn),稳的!那么边的数目是多少呢?dis[]数组开多大呢?我们从刚才是这个地方“y = idx(杆子的横坐标)+ N(横纵坐标较大的那个范围) + ai(传送门的高度)”以及题目的样例范围可以得出,我们给他开3倍大小的N就足够,边呢?应该是这么多:N(水平)+2N(竖直来回)+N(传送门) = 4N,管他呢,反正N最大才1e5,我们待会儿直接直接开十倍。然后就是输出那里,这里用printf来控制一下输出就行,详情看代码。

🍋Code实现

堆优化的dijkstra(error)

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

/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: LiangXinRui
 * @Date: 2023/4/8 17:33
 * @Description: 输入
 * 3
 * 1 10 11
 * 1 1
 * 2 1
 * 输出
 * 4.20
 */

public class Main {
    final static int N = (int) (1e5 + 10), M = 10 * N;
    static int n, total;
    static double levelTime = 1.0, downTime = 1.0 / 1.3, upTime = 1.0 / 0.7;
    static double[] dis = new double[3 * N];//每个站点到原点的最短距离(时间)
    static int[] idx = new int[N];//存每个杆子的横坐标
    static int[] head = new int[M], ends = new int[M], next = new int[M];
    static double[] weights = new double[M];
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static void add(int start, int end, double weight) {
        ends[total] = end;
        weights[total] = weight;
        next[total] = head[start];
        head[start] = total++;
    }

    public static void main(String[] args) {
        n = nextInt();
        Arrays.fill(head, -1);
        for (int i = 0; i < n; i++) idx[i] = nextInt();
        //存水平的边,上下的边,传送门的边,纵坐标用横坐标+n+ai来表示
        //添加水平边
        add(0, idx[0], levelTime);
        for (int i = 0; i < n - 1; i++) {
            add(idx[i], idx[i + 1], levelTime * (idx[i + 1] - idx[i]));
        }
        for (int i = 0; i < n - 1; i++) {//竖直边
            int ai = nextInt();
            int bi = nextInt();
            //传送门的单向边
            add(idx[i] + N + ai, idx[i + 1] + N + bi, 0);
            //第一个传送门与地面的边
            add(idx[i], idx[i] + N + ai, upTime);
            add(idx[i] + N + ai, idx[i], downTime);
            //第二个传送门与地面的边
            add(idx[i + 1], idx[i + 1] + N + bi, upTime);
            add(idx[i + 1] + N + bi, idx[i + 1], downTime);
        }
        dijkstra();
        System.out.printf("%.2f", dis[idx[n - 1]]);
    }

    static void dijkstra() {
        Queue<Node> queue = new PriorityQueue<>((o1, o2) -> (int) (o1.dis - o2.dis));//优先队列堆优化
        Arrays.fill(dis, Double.MAX_VALUE);
        dis[0] = 0;
        queue.offer(new Node(0, weights[0]));
        while (!queue.isEmpty()) {
            Node hh = queue.poll();
            for (int i = head[hh.num]; i != -1; i = next[i]) {
                int j = ends[i];
                if (dis[j] > dis[hh.num] + weights[i]) {
                    dis[j] = dis[hh.num] + weights[i];
                    queue.offer(new Node(j, dis[j]));
                }
            }
        }
    }

    static class Node {
        int num;
        double dis;

        public Node(int num, double dis) {
            this.num = num;
            this.dis = dis;
        }
    }

    static int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) in.nval;
    }
}


线性dp(pass)

dp[i][j] 表示蜗牛走到第 i 根杆子的最短用时,j 表示状态。
j = 0 : 走到杆子底部
j = 1 :走到杆子的传送门处
P.S.由于只与前一个杆子状态有关,其实用两个变量就行,用二维数组便于理解
时间复杂度: O(n)

import java.io.*;
import java.util.*;
public class Main{
    static int maxn = 200005,n,m;
    static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;
    static Scanner sc = new Scanner (System.in);
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st  =new StreamTokenizer(bf);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[]args) throws IOException{
        int T = 1;
        //T = Integer.parseInt(S());
        while(T-->0) solve();
        pw.flush();
    }
    static final int I() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
    static void solve() throws IOException{
        n = I();
        long x[] = new long [n+1];
        for(int i=1;i<=n;i++) x[i] = I();
        int []a = new int [n+1];
        int []b = new int [n+1];
        for(int i=1;i<n;i++) {
            a[i] = I();b[i] = I();
        }
        double dp[][] = new double[n+1][2];
        dp[1][0] = x[1]; //底端最小用时
        dp[1][1] = x[1] + a[1] / 0.7;  //传送门用时
        for(int i=2; i<=n ; i++) {
            dp[i][0] = Math.min(dp[i-1][0]+x[i]-x[i-1], dp[i-1][1] + b[i-1]/1.3);
            dp[i][1] = Math.min(dp[i][0] + a[i] / 0.7, dp[i-1][1] + ((b[i-1]>a[i])?(b[i-1]-a[i])/1.3: (a[i]-b[i-1])/0.7));
        }
        pw.printf("%.2f",dp[n][0]);
    }
}

🌹🌹🌹大家觉得今年的题更难一点吗?在评论区`说说自己的看法吧。💐💐💐


🐳结语

🐬初学一门技术时,总有些许的疑惑,别怕,它们是我们学习路上的点点繁星,帮助我们不断成长。

🐟文章粗浅,希望对大家有帮助!

🐟参考文章:蓝桥杯2023年第十四届省赛真题-蜗牛(线性dp)文章来源地址https://www.toymoban.com/news/detail-427863.html

到了这里,关于第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第十四届蓝桥杯省赛C++ B组(个人经历 + 题解)

    这是我第一次参加蓝桥杯的省赛,虽然没什么参赛经验,但是自己做了很多前几届蓝桥杯的题,不得不说,这一届蓝桥杯省赛的难度相较于之前而言还是比较大的。之前很流行蓝桥杯就是暴力杯的说法,但是随着参赛人数的增多,比赛认可度的提升,比赛题目的质量也明显越

    2024年02月03日
    浏览(44)
  • 第十四届蓝桥杯省赛c/c++大学B组题解

    个人答案,有错漏感谢指正哈 本题总分:5 分 【问题描述】   小蓝现在有一个长度为 100 的数组,数组中的每个元素的值都在 0 到 9 的范围之内。数组中的元素从左至右如下所示: 5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3

    2023年04月12日
    浏览(57)
  • 第十四届蓝桥杯省赛 Python B 组 D 题——管道(AC)

    有一根长度为 len text{len} len 的横向的管道,该管道按照单位长度分为 len text{len} len 段,每一段的中央有一个可开关的阀门和一个检测水流的传感器。 一开始管道是空的,位于 L i L_i L i ​ 的阀门会在 S i S_i S i ​ 时刻打开,并不断让水流入管道。 对于位于 L i L_i L i ​ 的阀

    2024年02月07日
    浏览(41)
  • 第十三届蓝桥杯省赛与国赛真题题解大汇总(十四届参赛者必备)

      大家好,我是执梗。本文汇总了我写的第十三届蓝桥杯所有省赛真题与国赛真题,会针对每道题打出我自己的难度评星⭐️,也会给出每道题的算法标签,帮助大家更有针对性的去学习和准备,当然许多题目由于难度或时间的原因暂未更新,如果有不懂的问题也可以在评

    2024年02月11日
    浏览(78)
  • 第十四届蓝桥杯省赛 C/C++ A 组 H 题——异或和之和(AC)

    给定一个数组 A i A_i A i ​ ,分别求其每个子段的异或和,并求出它们的和。或者说,对于每组满足 1 ≤ L ≤ R ≤ n 1 leq L leq R leq n 1 ≤ L ≤ R ≤ n 的 L , R L, R L , R ,求出数组中第 L L L 至第 R R R 个元素的异或和。然后输出每组 L , R L, R L , R 得到的结果加起来的值。 输入的第

    2024年02月13日
    浏览(49)
  • 2023年第十四届蓝桥杯javaB组 蜗牛解题思路(动态规划 O(n))

     E、蜗牛(时间限制: 1.0s 内存限制: 512.0MB) 【问题描述】 这天,一只蜗牛来到了二维坐标系的原点。 在 x 轴上长有 n 根竹竿。它们平行于 y 轴,底部纵坐标为 0 ,横坐标分别 为 x 1 , x 2 , ..., x n 。竹竿的高度均为无限高,宽度可忽略。蜗牛想要从原点走到第 n 个竹竿的底部

    2023年04月27日
    浏览(43)
  • 第十四届蓝桥杯大赛软件赛省赛-试题 B---01 串的熵 解题思路+完整代码

    欢迎访问个人网站来查看此文章:http://www.ghost-him.com/posts/db23c395/ 对于一个长度为 n 的 01 串 S = x 1 x 2 x 3 . . . x n S = x_{1} x_{2} x_{3} ... x_{n} S = x 1 ​ x 2 ​ x 3 ​ ... x n ​ ,香农信息熵的定义为 H ( S ) = − ∑ 1 n p ( x i ) l o g 2 ( p ( x i ) ) H(S ) = − {textstyle sum_{1}^{n}} p(x_{i})log_{2} (p

    2023年04月10日
    浏览(45)
  • 第十四届蓝桥杯大赛青少年省赛C++组试题真题 2023年5月

    一、选择题 第 1 题 单选题 C++中,bool类型的变量占用字节数为 ( )。 A. 1 B. 2 C. 3 D. 4 第 2 题 单选题 以下关于C++结构体的说法,正确的是 ( )。 A. 结构体中只能包含成员变量,不能包含成员函数 B. 结构体不能从另一个结构体继承 C. 结构体里面可以包含静态成员变量 D. 结构体里

    2024年02月15日
    浏览(54)
  • 十四届蓝桥杯省赛CB

    写的时候没跑出来,仅仅是因为给 (i*i) 加了括号,爆了int!!! 双精度浮点的表示范围:-1.79E+308 ~ +1.79E+308 基本类型:int 二进制位数:32(4字节) 最小值:Integer.MIN_VALUE= -2147483648 (-2的31次方) 最大值:Integer.MAX_VALUE= 2147483647 (2的31次方-1 double范围很大,基本不可能爆,不

    2024年02月08日
    浏览(46)
  • 2023第十四届蓝桥杯JavaB组

    目录 A、阶乘求和  Ⅰ、题目解读 Ⅱ、代码  B、幸运数字  Ⅰ、题目解读  Ⅱ、代码 C: 数组分割(时间限制: 1.0s 内存限制: 512.0MB)  Ⅰ、解题思路  Ⅱ、代码  D、矩形总面积(时间限制: 1.0s 内存限制: 512.0MB)  Ⅰ、题目解读 Ⅱ、代码   E、蜗牛(时间限制: 1.0s 内存限制

    2023年04月09日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包