赛题要求选手找出连接磁带上特定点的最短路径，而两点之间的距离与两点顺序、所在wrap、所在band相关。我们可以将赛题抽象化为不对称的旅行商问题。本次赛题要求使用python且时间低于5s，这就要求需要对代码进行一定的优化。事实上简单计算所有点的两两距离耗时就远超5s。以下将主要讲下我是如何解决距离计算问题的。不同于这个帖子和这个帖子中选择使用numpy加速距离计算，我在实验后决定在KNN图上求解原问题。图1 针对某个目标点(wrap,distance)=(15,66)，可能的入边距离（耗时）分布和出边距离分布情况。其中横坐标为distance，纵坐标为wrap，颜色为距离，某个点的颜色代表该点到达目标点或从目标点到达该点的耗时。观察图1，我们可以发现对于某个点而言，每个可能的三元组 (band, direction, closest_anchor) 都对应了一个距离（耗时）区间。由此，我们可以对每组 (band, direction, closest_anchor) 都记录所包含的点，之后对于给定的目标点（这里包括题目的requests和 (0,0) 点），我们按照三元组对应的入边距离区间的最小值排序（预先计算），并记录这些三元组包含的前K个点，计算得到不精确的前K条入边及其距离，最后用这些边构建图。其他诸如记忆化，压缩点等技巧想必大家都会，就不赘述了。之后就是比较常规的求一个初始解并优化。初始解参考了Savings算法，优化主要用了3-opt。

题目要求只能使用python语言解题，使用常规方案计算两两锚点之间的移动代价将会是非常耗时的操作，在此分享一下如何使用numpy进行快速计算两两锚点之间的移动代价，整体思路是将需求转换成：从当前锚点出发到达任意一个锚点之间的移动代价，将需求转换后看似并没有减少运算的时间复杂度，但是可以利用numpy进行批量计算，对于从任意一个锚点出发的具体的计算如下，设当前锚点到达任意一个锚点的代价都为7.5(4 + 1 + 2.5),即cost[:,:]=7.5对于在相同带子的锚点则不需要4s的罚时，即cost[band_id==cur_band_id]-=4.0 可以进一步替换成cost[当前锚点带子所有行]-=4.0，对于相同包裹的锚点则不需要1s罚时，即cost[当前锚点包裹所在行]-=1.0，对于同向移动的锚点则不需要换向2.5s罚时，即当前锚点正向移动时cost[当前锚点右侧列]-=2.5，当前锚点反向移动时cost[当前锚点左侧列]-=2.5伪代码如下：# last_request：当前锚点下的最后一个请求# wrap_num_per_band = 52cost = np.full((wrap_num, anchor_num_per_warp), 7.5, dtype=np.float32)cur_b_id = last_request.b_ids = cur_b_id * wrap_num_per_bande = s + wrap_num_per_bandcost[s:e] -= 4.0 # 相同带子不需要跨带子罚时cost[last_request.w_id] -= 1.0 # 相同包裹不需要跨包裹罚时if last_request.w_id % 2 == 0: cost[(last_request.w_id % 2)::2, last_request.a_id + 1:] -= 2.5 # 右侧且同向行不需要换向else: cost[(last_request.w_id % 2)::2, :last_request.a_id] -= 2.5 # 左侧且同向行不需要换向 

整体思路本项目目标是实现建筑物轮廓的检测（分割）和高度估计两项任务，整体流程包括以下两部分：建筑物轮廓检测：通过 MobileNet-based Unet 模型进行建筑物分割，生成建筑物轮廓的二值掩码。建筑物高度估计：基于分割结果，利用原图和分割掩码预测建筑物的平均高度值。两部分任务相互衔接，分割结果直接作为高度估计的输入之一，确保建筑物检测的高效性与准确性。建筑物轮廓检测数据与方法数据准备数据集包含约 2000 张标注图像，标注格式为 labelme，通过脚本转换为二值分割掩码。数据集划分：80% 用于训练，20% 用于验证，确保训练与验证集分布一致。模型选择使用 MobileNet V2 作为编码器，结合 Unet 架构的解码器部分。编码器采用在 ImageNet 上预训练的权重，以加速收敛。训练配置输入大小：512x512（统一缩放）损失函数：Jaccard Loss优化器：Adam学习率：初始值为 0.0001，采用 Cosine Annealing 调度器逐步衰减数据增强：包括随机旋转、水平翻转、颜色扰动（亮度、对比度调整）和随机裁剪。后处理使用 cv2.findContours 提取分割结果中的轮廓线，并通过 cv2.approxPolyDP 对边界进行平滑，生成最终的建筑物轮廓文件。建筑物高度估计方法描述输入设计高度估计模型输入包括原始 RGB 图像及第一步生成的分割掩码（作为第四通道）。采用分割掩码对原始图像中的建筑物区域进行裁剪，排除非建筑物区域的干扰。模型结构使用 U-Net 架构，输出每个像素的高度值。编码器部分同样采用 MobileNet V2，以减少参数量和计算复杂度。训练配置损失函数：MSE Loss优化器：Adam学习率：0.0001（固定）训练数据增强：仅限几何变换（旋转、裁剪等），避免颜色增强对高度估计结果的干扰。结果后处理对每个建筑物区域内的像素高度取平均值，生成每栋建筑物的最终高度估计值。主要脚本train_segmentation.py：分割模型训练脚本train_height.py：高度估计模型训练脚本inference.py：推断脚本，整合两部分任务模型文件分割模型mobilenet_unet.pth：MobileNet-based Unet 训练好的权重文件高度估计模型height_estimation.pth：高度估计模型权重文件项目总结分割模型实现了轻量化设计，适用于实时任务，推理速度显著提升。高度估计依赖分割结果的精度，分割性能的优化是进一步提升整体效果的关键。 

😀前言在程序设计和算法竞赛中，丑数问题是一个经典的动态规划题目。丑数（Ugly Number）定义为只包含质因子 2、3 和 5 的数。举例来说，数字 6（因子为 2 和 3）、数字 8（因子为 2）都是丑数，而数字 14 不是丑数，因为它包含质因子 7。在这种定义下，1 通常被视为第一个丑数。🥰丑数NowCoder😊题目描述把只包含因子 2、3 和 5 的数称作丑数（Ugly Number）。例如 6、8 都是丑数，但 14 不是，因为它包含因子 7。习惯上我们把 1 当做是第一个丑数。求按从小到大的顺序的第 N 个丑数。例子输入：N = 10输出：12解释：前10个丑数依次是 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]，因此第10个丑数为12。😄解题思路解决该问题的常见方法是动态规划。动态规划的基本思想是从第一个丑数开始，逐步生成下一个丑数，直到得到第 N 个。核心思想定义状态：使用一个长度为 N 的数组 dp，其中 dp[i] 表示从小到大第 i+1 个丑数。初始化 dp[0] = 1，即第一个丑数是 1。生成丑数：由于丑数的定义，新的丑数可以通过已知的丑数乘以 2、3 或 5 来生成。因此，我们在每一步都计算下一个可以生成的丑数。三个指针：维护三个指针 i2, i3, i5，分别表示当前丑数数组中，乘以 2、3、5 后最小值的索引。每次选择这三个数中的最小值作为下一个丑数，并更新相应的指针。避免重复：如果当前生成的丑数等于多个最小值中的某个，我们需要将对应的指针后移，避免重复计算。例如，如果 dp[i] 既是 dp[i2] * 2，又是 dp[i3] * 3，我们需要同时更新 i2 和 i3。💖代码实现public int GetUglyNumber_Solution(int N) { if (N <= 6) return N; // 特殊情况：如果 N 小于等于6，直接返回 N，因为前6个丑数为 [1, 2, 3, 4, 5, 6] int i2 = 0, i3 = 0, i5 = 0; // 初始化三个指针，分别指向当前乘以2、3、5的丑数索引 int[] dp = new int[N]; // 创建数组存储前N个丑数 dp[0] = 1; // 第一个丑数是1 for (int i = 1; i < N; i++) { // 计算下一个可能的丑数，分别为2、3、5的倍数 int next2 = dp[i2] * 2, next3 = dp[i3] * 3, next5 = dp[i5] * 5; // 当前丑数是这三个数中的最小值 dp[i] = Math.min(next2, Math.min(next3, next5)); // 如果当前最小值是乘以2得到的，更新指针i2 if (dp[i] == next2) i2++; // 如果当前最小值是乘以3得到的，更新指针i3 if (dp[i] == next3) i3++; // 如果当前最小值是乘以5得到的，更新指针i5 if (dp[i] == next5) i5++; } // 返回第N个丑数 return dp[N - 1]; } 详解代码特殊处理：首先判断 N 是否小于等于 6，因为前 6 个丑数就是 [1, 2, 3, 4, 5, 6]，直接返回即可。初始化指针和数组：i2, i3, i5 分别指向乘以 2、3、5 后可以得到的最小丑数索引。数组 dp 用于存储从小到大生成的丑数，初始值为 dp[0] = 1。计算最小值：每次循环中，分别计算 next2 = dp[i2] * 2，next3 = dp[i3] * 3，next5 = dp[i5] * 5，然后取这三个值的最小值作为下一个丑数。更新指针：如果当前生成的丑数是乘以 2 得到的，则指针 i2 向后移动，以便下次循环使用更新的丑数；如果是乘以 3 或 5 得到的，也分别移动指针 i3 和 i5。复杂度分析时间复杂度：O(N)，因为我们只需要生成 N 个丑数，每次生成一个丑数的操作时间是常数。空间复杂度：O(N)，因为我们使用了一个长度为 N 的数组来存储丑数。😄总结丑数问题通过动态规划的方式，巧妙地利用三个指针生成新的丑数，并且保证了每个丑数都是按顺序生成的。通过这种方式，我们可以在 O(N) 的时间内得到第 N 个丑数，是一种高效的解决方案。

12期获奖名单和提交顺序一致，未进行复测。这个获奖名单是最终版吗？ 不可能前排选手都是满分吧，请问主办方最后有没有进行多组数据复测？就算都是满分情况下，性能以及运行时间也都一致？

请问最终排名顺序和提交时间顺序一模一样，最终分数不可能和提交时间顺序一模一样吧？由于精度问题，得分乘以系数后差别较小，所以最终就直接按照提交时间排名了是吗？

榜单几乎没变换，应该没有跑新数据吧，np问题数据稍微复杂点很难满分的，榜单不可能一点变化没有吧，此外，还淘汰个今年华为软挑的冠军。。。能解释下嘛

数据集不是按任务书上命名的，没法的得到label啊，请检查下吧

请问输入是读取的in文件还是说得自己input。

赛题描述是 底库数据量/耗时   测出来是  查询向量个数/耗时  ，请确认一下 

12期这么多满分，线上数据集有点简单，最后会用大量数据集跑分然后排名嘛

有关AffinityScore，题面原文为其中preceeded单词错误，请问应该是什么呢？此外，请问AffinityScore增加是要求同类Message必须相邻，还是位于同一个core就行呢？

目前的得分计算方式是在三个数据集上QPS的累加和，奖项设置规定得分大于68504分才有奖品，确定不是多打了个0吗？

编译环境pdf中提到可用的Python包包括：python 3.7.3  numpy: 1.21.6  faiss-cpu: 1.7.4  scipy: 1.7.3，补充说明中又说道除numpy外，不允许引用其他第三方库，感觉二者相互冲突了。除此以外，还有一些编程和运行程序的规则也不是很明确。请问faiss和scipy在比赛中是否能使用呢？还是说算法的全部代码都必须由python的默认库和numpy来实现？实验环境只提到了x86，请问允许使用多核心/多线程吗？一共有三个样例，三个样例一共允许运行12分钟，还是说一个样例允许运行12分钟呢？

请问，第十期问题可以用Python/Matlab编程语言吗