题解：P11046 [蓝桥杯 2024 省 Java B] 星际旅行

分析:只要是能传送过去并且传送次数不为0，就算可以到达，所以这里不能用dfs来，很明显的bfs算法，分层遍历，每一层会消耗一次传送次数，但是本题的数据过大，如果使用邻接矩阵来作为visited数组那么时间复杂度过高，只能通过部分测试用例1.使用邻接矩阵遍历传送阵时间复杂度为O(n)，假如有50万个星球，那么就需要遍历50万次2.使用邻接表寻找传送阵时间复杂度为O(1)

这道题首先要看懂题。就是看第一个盲盒，2，1初始在2号星球他只有一个传送门的机会，但后面题解说的他能旅行三个星球一共，其实意思是题目中说的。也就是从2传送到1是花费一次，他也有可能从2传送到3也是花费一次，所以说他有可能到达1和3，加上初始的2，所以就是有可能旅行的星球是3个。他说的是可能性一共有多少个可以实现旅行，所以这里就可以用到dfs的思路，也就是。接下来就把代码放上，不一定对，是个人的一点见解，有问题多谢大家指出来。

我给大家分享自己的做题情况，就是给参加蓝桥杯的宝子们一点基准，要达到一个什么样的程度才能省一，心里目标会更加明确。

2024年十五届蓝桥杯省赛大学B组真题（Java完整版）题解

所以我们这只要讨论3人寝室，能先放6人桌就先放6人桌。剩下的2人寝和4人寝室，先放满6人桌，再放4人桌。步最多能走几个星球，所以我们可以贪心的想，我们对每个点都走最短路，那么走的星球数量肯定是最多的，所以这时候我们可以把。因为有3人寝室，而桌子有4和6人桌，如果让3人寝室上4人桌的话这样就会空出一个位置，而其他4人2人寝室都可以凑满。这题需要先分析看到边和点很小，询问很大，第一反应是需要预处理。的最短距离，类似于多源汇最短路，第一时间想到的是。分组所需要的试剂，答案只用取个。，检测这些患病的宠物也需要。

给定一个 n × m 的迷宫，1 表示墙壁，0 表示可以走的路径，找到从起点 (0,0) 到终点 (n-1,m-1) 的最短路径长度（走一步算一步）。广度优先搜索（BFS）：是蓝桥杯的常考算法之一，常出现在图论、迷宫等问题中，考查选手对 BFS 思想和队列操作的理解。// (x, y, 步数)广度优先搜索（BFS）：一种用于遍历或搜索树或图的算法，使用队列来实现，能够保证找到的路径是最短路径。边界条件处理：在检查节点是否合法时，要考虑边界条件，如节点是否在地图范围内，避免数组越界错误。

这题是个dfs题，当时感觉条件太多了，一看就不会，采取了骗分的方法，因为t<=10,然后答案只会是Yes和No，所以我觉得可以骗，下面是骗分伪代码。​ 这题和去年的飞机降落有点像又不太像，总觉得太麻烦了我就没去多想，直接big胆骗分,下面是我的骗分伪代码(能过1个样例就满足了)​ 又是期望值，我的写法是floyd算法，一个传送门的距离算作1，算出每个点之间的最短传送门距离就好做了，这应该是正解？我直接不会，猜测答案区间范围直接输出打印。​ 纯暴力for循环，然后也知道给我4小时也跑不出来，所以不会做了。

本次应该是没考什么特别难的算法，除了有一两题看到就不想做的没细想，其他的基本就是基本算法（但不是偏向模板，感觉这次比较综合，都是要在模板的基础上改挺多的），希望别留下遗憾。思路：暴力两重循环就完事了，可能有几个样例过不了，需要一点优化，我这随便糊了手指针优化，也不一定对。我没学期望，用高中知识现推的，只验证了题目给的样例，但是不知道对不对。唉，可惜开学后，课太多了，进度贼慢，又不敢矿，可恶，上学真耽误学习。啊啊，读题读了40分钟，一直没懂，也是没谁了，状态是真的差。

这套题罗里吧嗦一大堆，不仔细看真的容易审题不清晰，而且很容易被误导，这道题难就难在题目理解上，这道题我们其实可以不用管副节点， 而且主节点添加了什么元素，以及副节点添加了什么元素，是否与主节点相等，你全都不用管，你只要在意主节点要添加元素的时候，你就往里面添加就好了，这个题目的意思就是，副节点会自动填充，我们不需要管，那这就好办了，我们只需要每次在显现元素的时候，找到所有队列中元素最少的就好了。由于副本的同步速度各异，因此为了保障数据的一致性，元素添加到主节点后，需要同步到所有的副节点后，才具有可见性。

小明国庆节准备去某星系进行星际旅行，这个星系里一共有 n 个星球，其中布置了 m 道双向传送门，第 i道传送门可以连接 ai​,bi​ 两颗星球（ai≠bi 且任意两颗星球之间最多只有一个传送门）。他看中了一款 “旅游盲盒”，一共有 Q个盲盒，第 i个盲盒里的旅行方案规定了旅行的起始星球 xi 和最多可以使用传送门的次数 yi。只要从起始星球出发，使用传送门不超过规定次数能到达的所有星球都可以去旅行。小明关心在每个方案中有多少个星球可以旅行到。

洛谷 P11045 题解

试题编号： 202012-5 试题名称： 星际旅行 时间限制： 3.0s 内存限制： 512.0MB 问题描述： 题目描述 乔帝要规划一次星际旅行，星际空间可以视为一个3维坐标系，乔帝有n(n≤1,000,000,000)个动力装置排成一行(下标从1到n)。 第i个动力装置可以让他的飞船3个维度的坐标分别增加xi,yi,zi。一开始这些动力装置的所有参数都是0。 在规划过程中，乔帝可能会对动力装置进行调整，也可能会对一些动力装置的动力进行评估。 具体来说，乔帝会进行m(m≤40000)次操作，每次操作可能是

算法训练 星际交流   时间限制：1.0s   内存限制：256.0MB        问题描述 　　人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样 的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果

本文详解了USACO挤牛奶问题(P1204)的解题思路与代码实现。题目要求计算N个农民挤奶时间区间的两个关键指标：最长连续挤奶时间和最长空闲时间。解题步骤包括：1)将时间区间按开始时间排序；2)遍历合并重叠区间，同时更新最长挤奶时间和最长空闲时间；3)输出结果。代码使用结构体存储区间，通过自定义排序和区间合并算法高效解决问题。文章还提供了样例解析，验证了算法正确性，并建议了可能的拓展方向。该方案时间复杂度为O(nlogn)，主要来自排序操作，适用于大规模数据。

摘要： 本文详解矩形面积并问题的扫描线算法解法。给定n个矩形（1≤n≤10⁴），每个矩形由对角坐标(x1,y1,x2,y2)表示，要求计算其覆盖的总面积（重叠部分只算一次）。算法核心步骤包括： 事件拆分：将矩形拆分为入边（y1）和出边（y2）事件； 离散化处理：对x坐标排序去重，建立映射关系； 线段树维护：动态追踪x轴覆盖长度，支持区间更新； 扫描计算：按y坐标扫描事件，累加相邻高度差与当前覆盖长度的乘积。 关键优化包含坐标标准化、离散化压缩、线段树动态维护覆盖长度。C++实现通过事件排序（O(nlogn)