CCF GESP 2025年6月认证 C++ 6级
题目描述
班主任计划将班级里的 $ n $ 名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。观察发现，如果一个学习小组中恰好包含 $ k $ 名同学，则该学习小组的讨论积极度为 $ a_k $。
给定讨论积极度 $ a_1, a_2, \ldots, a_n $，请你计算将这 $ n $ 名同学划分为学习小组的所有可能方案中，讨论积极度之和的最大值。
输入格式
第一行，一个正整数 $ n $，表示班级人数。
第二行，$ n $ 个非负整数 $ a_1, a_2, \ldots, a_n $，表示不同人数学习小组的讨论积极度。
输出格式
输出共一行，一个整数，表示所有划分方案中，学习小组讨论积极度之和的最大值。
样例说明
样例 1
4
1 5 6 310样例 2
8
0 2 5 6 4 3 3 412数据范围
对于 $40\%$ 的测试点，保证 $1\le n\le 10$。
对于所有测试点，保证 $1\le n\le 1000$，$0\le a_i\le 10^4$。
题目描述
给定一棵有 $10^9$ 个结点的有根树，这些结点依次以 $1, 2, \dots, 10^9$ 编号，根结点的编号为 $1$。对于编号为 $k$（$2 \leq k \leq 10^9$）的结点，其父结点的编号为 $k$ 的因数中除 $k$ 以外最大的因数。
现在有 $q$ 组询问，第 $i$（$1 \leq i \leq q$）组询问给定 $x_i, y_i$，请你求出编号分别为 $x_i, y_i$ 的两个结点在这棵树上的距离。两个结点之间的距离是连接这两个结点的简单路径所包含的边数。
输入格式
第一行，一个正整数 $q$，表示询问组数。
接下来 $q$ 行，每行两个正整数 $x_i, y_i$，表示询问结点的编号。
输出格式
输出共 $q$ 行，每行一个整数，表示结点 $x_i, y_i$ 之间的距离。
样例说明
样例 1
3
1 3
2 5
4 81
2
1样例 2
1
120 6509数据范围
对于 $60\%$ 的测试点，保证 $1 \leq x_i, y_i \leq 1000$。
对于所有测试点，保证 $1 \leq q \leq 1000$，$1 \leq x_i, y_i \leq 10^9$。