#482. [CSP-S 2026] 迁徙
[CSP-S 2026] 迁徙
迁徙(migrate)
CSP-S 2026 第二轮 · T3(赛题题意整理,测试数据为自制)
题目描述
有 座岛屿排列在一条直线上,其坐标为严格递增的整数 。海鸟每次能从一座岛屿飞到另一座岛屿,当且仅当两岛坐标差的绝对值不超过 。每次飞行算路径的一步。
定义有序编号 的一对岛屿为双径岛屿对,如果从 到 的最短路径恰好有两条。路径按完整经过的岛屿编号序列区分;不可达或最短路条数不是恰好两条都不计入答案。
对每组数据,求双径岛屿对的总数。
输入格式
第一行两个非负整数 ,表示测试点编号和数据组数。 不影响算法。
随后 组数据。每组第一行两个整数 ;第二行给出 个严格递增的整数 。
输出格式
对每组数据输出一行整数:满足条件的岛屿对数量。
输入输出样例 #1
0 2
4 2
1 2 3 4
5 2
1 2 3 4 5
1
2
输入输出样例 #2
0 2
5 3
-2 -1 0 1 2
6 2
-4 -3 -2 -1 3 6
0
1
数据范围与说明
每个文件包含 组数据;单组 。一个测试文件的 。
,,。
两条不同最短路径按经过的岛屿编号序列是否相同来区分。可能有三条以上最短路径,不能将它们误判成两条。
注意: Hydro 使用标准输入输出;测试数据自行生成,并非 CCF 官方测试数据。