#213684. [IOI 2025] 神话三峰（triples）（Part 2）

本题目前可以评测子问题 2。可在 P13536 评测子问题 1。

东科迪勒拉山脉是安第斯山脉跨越玻利维亚的部分。它由连续的 座山峰组成，从 到 编号。山峰 （）的高度 是 到 之间的整数。

对任意两座山峰 和 （其中 ），它们的距离定义为 。根据古老的印加传说，三座山峰是神话三峰的条件是：它们的高度与两两之间的距离在忽略顺序后匹配。

形式化地， 是神话三峰的条件为：

• ，
• 山峰高度 与两两之间的距离 在忽略顺序后匹配。例如，对山峰 ，其两两之间的距离是 ，所以山峰高度 ， 和 都匹配，但山峰高度 则不匹配。

该问题分为两个部分，分别对应子问题一或者子问题二。你可以按任意顺序解决这些子问题。特别地，你无需先完成子问题一再尝试子问题二。

子问题一

给定山脉的描述，你的任务是计算神话三峰的数量。

实现细节

你要实现以下函数：

long long count_triples(std::vector<int> H)

• : 长度为 的数组，表示每座山峰的高度。
• 对每个测试用例，该函数恰好被调用一次。

该函数返回一个整数 ，表示山脉中神话三峰的数量。

子问题二

你的任务是构造包含尽量多神话三峰的山脉。该子问题包含 个有部分得分的提交答案的子任务。

对每个子任务，你将获得两个正整数 和 ，需要构造一个最多包含 座山峰的山脉。如果你的答案中包含至少 个神话三峰，你将获得该子任务的满分。否则，你的得分将与你的答案中所包含的神话三峰的数量成正比。

注意，你的答案必须是一个有效的山脉。具体来说，假设你的答案包含 座山峰（ 必须满足 ）。那么，山峰 的高度 （）必须是一个 到 之间的整数。

实现细节

有两种提交解答的方法，你可以为每个子任务选择其中一种：

• 输出文件
• 函数调用

通过输出文件提交解答时，请创建并提交一个格式如下的文本文件：

N
H[0] H[1] ... H[N-1]

通过函数调用提交解答时，你需要实现以下函数。

std::vector<int> construct_range(int M, int K)

• : 最多允许的山峰数量。
• : 期望的神话三峰数量。
• 对每个测试用例，该函数恰好被调用一次。

该函数应返回一个长度为 的数组 ，表示每座山峰的高度。

子问题一和二使用相同的评测程序示例，两个子问题的区别由输入的第一行确定。

子问题一的输入格式：

1
N
H[0] H[1] ... H[N-1]

子问题二的输入格式：

2
M K

子问题一的输出格式：

T

子问题二的输出格式：

N
H[0] H[1] ... H[N-1]

注意，评测程序示例的输出格式与子问题二输出文件所需的格式一致。

样例输入 1

1
7
4 1 4 3 2 6 1

样例输出 1

3

子问题 1 例子

考虑以下调用。

count_triples([4, 1, 4, 3, 2, 6, 1])

该山脉中包含 个神话三峰：

• 对 ，高度 与两两之间的距离 匹配。
• 对 ，高度 与两两之间的距离 匹配。
• 对 ，高度 与两两之间的距离 匹配。

因此，该函数应该返回 。

注意， 不构成神话三峰，因为其高度 与两两之间的距离 并不匹配。

子问题 1 数据范围

• 。
• 对每个满足 的 ，都有 。

子任务与得分规则

子问题一总共 分。

子问题二总共 分。 每个子任务的 和 值是固定的，如下表所示：

对每个子任务，如果你的答案不构成有效的山脉，你的得分将为 （在 CMS 中被报告为 Output isn't correct）。否则，设 表示答案中的神话三峰数量。 则你在该子任务中的得分为：