蓝桥杯2026年第十七届省赛真题-星座导航校准器

深空探测器在执行任务时需要依靠星座导航系统进行精确定位。该系统由若干颗导航卫星组成，每颗卫星都有固定的轨道位置和信号强度。

为了确保导航精度，需要选择一组卫星构成 “导航星座”，使得：

1. 两颗卫星距离过近会产生干扰，降低导航精度；

2. 星座必须保持连通性（通信半径为 R，任意两颗卫星都能通过直接或间接通信到达）；

3. 在综合考虑以上因素后，使总导航精度最大化。

导航精度计算规则

设选定的导航星座包含卫星集合 S = {s1, s2,. . . , sk}，每颗卫星 si 位于坐标(xi, yi)，信号强度为 pi。

基础精度：每颗卫星贡献的基础精度为其信号强度 pi。

几何加成：考虑星座的几何分布，计算所有卫星对之间的几何加成：

连通性约束：

• 如果两颗卫星距离 dij ≤ R，则它们可以直接通信。

• 整个星座必须保持连通（任意两颗卫星都能通过直接或间接通信到达）。

干扰惩罚：如果两颗卫星距离过近（dij < T），会产生信号干扰，精度减少：

其中 1_dij<T 是指示函数，当条件满足时为 1，否则为 0；对每一对不同的卫星（i < j）各计算一次干扰惩罚。

总导航精度计算公式：

给定 N 颗候选卫星的坐标和信号强度，以及通信半径 R 和干扰阈值 T，从中选择若干颗卫星组成导航星座，使得：

1. 星座保持连通性（通信半径为 R）；

2. 总导航精度最大化；

3. 星座中至少包含 K 颗卫星。

第一行包含四个整数 N、K、R、T，分别表示候选卫星数量、最少卫星数量、通信半径和干扰阈值。

接下来 N 行，每行包含三个整数 xi、yi、pi，表示第 i 颗卫星的坐标和信号强度。

输出一行，包含一个整数，表示能够达到的最大导航精度（向下取整）。

【样例说明 1】

最优解：选择卫星 {1, 2, 3}（编号从 1 开始），即坐标为 (0, 0)、(5, 0)、

(0, 5) 的三颗卫星。

连通性验证：

所有卫星对都能直接通信，星座连通。

精度计算：

1. 基础精度：5+ 8 + 6 = 19 。

2. 几何加成：

总几何加成：7.84 + 5.88 + 6.72 = 20.44 。

3. 干扰惩罚：所有距离都 ≥ 5 > T =3，无干扰惩罚。

总精度：19 + 20.44 ? 0= 39.44，向下取整为 39。

【样例输入 2】

5 3 5 3

0 0 1 0

2 0 8

4 0 6

10 0 12

1 4 9

【样例输出 2】

139

【样例说明 2】

最优解：选择卫星 {1, 2, 3, 5}（编号从 1 开始），即坐标为 (0, 0)、(2, 0)、(4, 0)、(1, 4) 的四颗卫星。

连通性验证：

所有选中卫星对都能直接通信，星座连通。

精度计算：

1. 基础精度：10 + 8 + 6 + 9 = 33

2. 几何加成：

总几何加成：35.78 + 14.55 + 21.21 + 21.47 + 16.97 + 10.59 = 120.57 。

3. 干扰惩罚：

• 卫星 1-2 距离 2< T=3，产生干扰：(3 ? 2) × min(10, 8) = 1 × 8= 8 ；

• 卫星 2-3 距离 2< T=3，产生干扰：(3 ? 2) × min(8, 6) = 1 × 6= 6 ；

• 其他卫星对距离都 ≥ 3，无干扰。

总干扰惩罚：8+ 6 = 14

总精度：33 + 120.57 ? 14 = 139.57，向下取整为 139。

【评测用例规模与约定】

对于 30% 的数据：N ≤ 8，K ≤ 3；

对于 60% 的数据：N ≤ 12，K ≤ 5；

对于所有评测用例：

• N ≤ 15，K ≤ 8，R ≤ 20，T ≤ 10 ；

• 坐标范围：0 ≤ xi, yi ≤ 100 ；

• 信号强度：1 ≤ pi ≤ 20 ；

• 保证存在至少 K 颗卫星、且满足连通性约束的解。