第 1 题 链表不具备的特点是( )。

A. 可随机访问任何一个元素

B. 插入、删除操作不需要移动元素

C. 无需事先估计存储空间大小

D. 所需存储空间与存储元素个数成正比

【答案】A

【考纲知识点】

链表（Linked List）是一种线性数据结构，其核心特点：

• 1、不支持随机访问：
  只能从头结点或尾结点开始，依次遍历到目标结点，时间复杂度为 O(n)。
• 2、插入 / 删除高效：
  只需修改指针指向，无需移动其他元素，时间复杂度为 O(1)（若已找到目标结点）。
• 3、动态内存分配：
  无需预先分配固定大小的存储空间，可随元素增减动态申请 / 释放内存。
• 4、空间开销：
  除存储数据外，还需额外存储指针域，因此总存储空间与元素个数成正比。

【解析】

A.  错误。链表不支持下标随机访问，必须顺序遍历。

B.  正确。只需修改指针指向，无需移动其他节点。

C.  正确。链表是动态结构，可按需分配内存。

D.  正确。每个结点都包含数据域和指针域，结点数越多，总空间越大。

第 2 题 双向链表中每个结点有两个指针域 prev 和 next ，分别指向该结点的前驱及后继结点。设 p 指向链表中的一个结点，它的前驱结点和后继结点均非空。要删除结点 p ，则下述语句中错误的是（ ）。

【答案】A

【考纲知识点】

双向链表删除结点的核心逻辑：

要删除结点 p（前驱、后继均非空），需要：

1、让 p 的后继结点的 prev 指针指向 p 的前驱结点：p->next->prev = p->prev

2、让 p 的前驱结点的 next 指针指向 p 的后继结点：p->prev->next = p->next

3、释放结点 p 的内存：delete p

【解析】A：这两句指针赋值完全错误，会导致链表断裂，因此A 是错误的。

第 3 题 假设双向循环链表包含头尾哨兵结点(不存储实际内容)，分别为 head 和 tail ，链表中每个结点有两个指针域 prev 和 next ，分别指向该结点的前驱及后继结点。下面代码实现了一个空的双向循环链表，横线上应填的最佳代码是( )。

【答案】B

【考纲知识点】

双向循环链表（含头尾哨兵结点）：

1、哨兵结点 head 和 tail 不存储实际数据，仅用于简化边界操作。

2、空链表时，head 和 tail 直接相连：

（1）head 的后继（next）指向 tail

（2）tail 的前驱（prev）指向 head

3、循环特性：在非空链表中，tail 的后继会指向 head，head 的前驱会指向 tail，但空链表时只需建立 head 和 tail 之间的直接连接

【解析】

A错误：只设置了 prev 指针，未建立 head 到 tail 的 next 连接，链表结构不完整。缺 next

B正确：完美建立了空双向循环链表的核心连接：

（1）head 的后继指向 tail

（2）tail 的前驱指向 head

此时链表为空，符合双向循环链表的初始状态。

C错误：空链表时 tail 的 next 不应指向 head（这是非空循环链表的特性），且未设置 tail 的 prev 指针。循环指针乱了

D错误：tail->next = nullptr 破坏了循环链表的结构，变成了普通双向链表。设成 nullptr 不是循环链表

第 4 题 用以下辗转相除法（欧几里得算法）求gcd(84, 60)的步骤中，第二步计算的数是（ ）。

A. 84和60

B. 60和24

C. 24和12

D. 12和0

【答案】B

【考纲知识点】辗转相除法（欧几里得算法）：

用于计算两个正整数的最大公约数（gcd），核心公式：gcd(a,b)=gcd(b,amodb)当 amodb=0 时，b 就是最大公约数。

【解析】

计算 gcd(84,60)的步骤：

1、第一步：gcd(84,60)

84÷60=1 余 24，即 

84mod60=24

递归调用  gcd(60,24)

2、第二步：gcd(60,24)

60÷24=2 余 12，即 

60mod24=12

递归调用 gcd(24,12)

3、第三步：gcd(24,12)

24mod12=0，返回 12

因此，第二步计算的数是 60 和 24。

口诀：辗转相除法（欧几里得算法）

大的变小，小的变余，直到余零，小的为真。

一句话解释

gcd(a, b) = gcd(b, a % b)永远拿余数去替换原来的小数，直到余数变成 0，此时的小数就是最大公约数。

第 5 题 根据唯一分解定理，下面整数的唯一分解是正确的（ ）。

A. 18 = 3 × 6

B. 28 = 4 × 7

C. 36 = 2 × 3 × 6

D. 30 = 2 × 3 × 5

【答案】D

【考纲知识点】

算术基本定理（唯一分解定理）：任何大于 1 的自然数，都可以唯一分解为若干质数的乘积（分解式中质数按从小到大排列，且不包含合数）。

【解析】D. 正确：2,3,5 均为质数，且乘积为 30，符合唯一分解定理。

第 6 题 下述代码实现素数表的线性筛法，筛选出所有小于等于 n的素数，横线上应填的最佳代码是( )。

A. j < primes.size()

B. i * primes[j] <= n

C. j < primes.size() && i * primes[j] <= n

D. j <= n

【答案】C

【考纲知识点】

线性筛法（欧拉筛）：

• 1、核心思想：每个合数只会被它的最小质因数筛去一次，因此时间复杂度为严格 O(n)。
• 2、关键约束：
1. （1）遍历质数列表 primes 时，不能越界（j < primes.size()）。
2. （2）筛除的合数不能超过 n（i * primes[j] <= n）。
3. （3）当 i % primes[j] == 0 时必须 break，保证每个合数只被最小质因数筛除。

【解析】

这个循环的目的是：用当前数 i 和已找到的质数 primes[j] 相乘，筛去合数 i * primes[j]。

1、条件必须同时满足两点：

（1）j < primes.size()：防止 j 越界访问 primes 数组。

（2）i * primes[j] <= n：保证筛除的合数不超过题目给定的 n，避免数组越界。

2、选项分析：

A.  错误。缺少 i * primes[j] <= n 约束，可能导致 i * primes[j] 超过 n，访问 is_prime 数组越界。

B.  错误。缺少 j < primes.size() 约束，j 可能超过 primes 数组长度，导致越界访问。

C.  正确。同时满足两个约束，既保证不越界访问数组，又保证筛除的合数不超过 n，是线性筛法的标准实现。

D.  错误。j 是 primes 数组的下标，n 是筛法上限，两者无直接关系，此条件完全错误。

第 7 题 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

A. 系统分配的栈空间溢出

B. 系统分配的堆空间溢出

C. 系统分配的队列空间溢出

D. 系统分配的链表空间溢出

【答案】A

【考纲知识点】函数调用栈（Call Stack）：

1、每次函数调用（包括递归调用）都会在栈（Stack）中分配一个栈帧（Stack Frame），用于存储：

（1）函数的局部变量

（2）函数参数

（3）返回地址（调用结束后继续执行的位置）

2、栈空间的大小是系统预先分配的，通常比较有限（MB 级别）。

3、当递归调用层数过多时，栈帧会不断累积，最终耗尽栈空间，引发 栈溢出（Stack Overflow）错误。

【解析】

A. 正确。递归调用的本质是函数嵌套调用，会持续占用栈空间，层数过多时必然导致栈溢出。

B. 错误。堆空间用于new/malloc动态分配的内存，与函数调用无关。

C. 错误。队列是一种数据结构，并非函数调用的默认内存区域。

D. 错误。链表是一种数据结构，其节点通常存储在堆中，与递归调用的内存机制无关。

第 8 题 对下面两个函数，说法错误的是（ ）。

A. 两个函数的实现的功能相同。

B. 两个函数的时间复杂度均为 O(n)。

C. factorialA采用递归方式。

D. factorialB采用递归方式。

【答案】D

【考纲知识点】递归与迭代：

递归：函数直接或间接调用自身，将问题分解为规模更小的子问题。

迭代：通过循环（for/while）重复执行一段代码，逐步累积结果。

【解析】

factorialA：是递归实现的阶乘函数，n <= 1 为基准条件，否则调用自身 factorialA(n-1)。

factorialB：是迭代实现的阶乘函数，通过 for 循环从 2 累乘到 n，没有调用自身。

逐项分析：

A. 正确。都计算 n!（阶乘）。

B. 正确。factorialA 递归 n 次，factorialB 循环 n−1 次，时间复杂度均为线性。

C. 正确。代码中 return n * factorialA(n-1); 是典型的递归调用。

D. 错误。factorialB 使用 for 循环迭代实现，不是递归。

第 9 题 下算法中，（ ）是不稳定的排序。

A. 选择排序

B. 插入排序

C. 归并排序

D. 冒泡排序

【答案】A

【考纲知识点】排序算法的稳定性

排序算法的基本原理（动画演示，收藏好文）

排序算法的稳定性是指：如果两个元素的关键字相等，排序后它们的相对顺序保持不变。

【解析】

A. 选择排序是典型的不稳定排序。

B. 插入排序是稳定排序。

C. 归并排序是稳定排序。

D. 冒泡排序是稳定排序。

【排序算法核心速查表（时间 + 空间 + 稳定性）】

【记忆口诀】

1. 2、时间复杂度口诀：
• 慢排序（O(n²)）：泡选插希
• 快排序（O(nlogn)）：归快堆
• 线性排序（O(n) 类）：桶计基
2. 3、空间复杂度口诀：
• 原地排序（O(1)）：泡选插希堆
• 非原地排序：归（O(n)）、桶 / 计 / 基（O(n+k)）、快（O(logn)）

• 【高频考点】

  1、快速排序：平均最快，最坏 O(n² )，不稳定

  2、归并排序：稳定，时间复杂度稳定 O(nlogn)，但空间开销大

  3、插入排序：最好 O(n)（数据有序时），稳定

  4、选择排序：无论好坏都是 O(n² )，不稳定

  5、堆排序：原地排序，不稳定，适合大数据量

  6、线性排序（桶 / 计 / 基）：稳定，仅适用于特定数据类型（整数 / 字符串等）

  【一句话总结】

• 要稳定：选归并、插入、冒泡、桶、计数、基数
• 要快：选快速、堆、归并
• 要原地：选冒泡、选择、插入、希尔、堆排序

【终极记忆法：排序三句诀（稳定性 + 时间 + 空间）】

1. 稳定性（最常考）

口诀：

稳：插、泡、归、桶、计、基不稳：选、快、希、堆

超级记忆法：

稳定 = “插泡归桶，吃鸡”

• 插 → 插入
• 泡 → 冒泡
• 归 → 归并
• 桶 → 桶排序
• 吃 → 计数
• 鸡 → 基数

画面：把东西插进泡泡里，归到桶里，然后吃鸡→ 安安稳稳、不插队 → 稳定！

不稳定 = “选快稀堆”

• 选 → 选择
• 快 → 快速
• 稀 → 希尔
• 堆 → 堆排序

画面：选一个快的，结果稀里糊涂堆在一起→ 乱了 → 不稳定！

2. 时间复杂度（好不好用）

口诀：

慢：泡、选、插           快：归、快、堆         飞：桶、计、基

记忆画面：

• 慢：泡澡选茶
  泡澡、选茶，慢悠悠 → O(n²)
• 快：鬼快递
  鬼（归）一样的快递，超快 → O(n log n)
• 飞：桶吃鸡
  坐桶吃鸡，飞天速度 → 线性 O (n)

3. 空间复杂度（要不要额外空间）

口诀：

原地：泡、选、插、希、堆要空间：归、桶、计、基

记忆画面：

• 原地：泡澡选西瓜堆
  就在原地玩，不挪地方 → O(1)
• 要空间：鬼桶吃鸡
  归并、桶、计数、基数→ 都要额外地方放东西

4、最终超级精简版（背这 3 句就够）

1. 稳定：插泡归桶，吃鸡
2. 不稳：选快稀堆
3. 快慢：泡澡选茶慢     |    鬼快递     |     飞桶吃鸡
4. 空间：泡澡原地选西瓜堆                      鬼桶吃鸡要地

第 10 题 考虑以下C++代码实现的快速排序算法，将数据从小到大排序，则横线上应填的最佳代码是( )。

【答案】B

【考纲知识点】快速排序（Quick Sort）+ 划分函数（Partition）

1、核心思想：

（1）选一个基准值（pivot），将数组分为两部分：

（2）左部分：小于等于 pivot 的元素

（3）右部分：大于等于 pivot 的元素

（4）递归排序左右部分。

2、划分逻辑（考点）：

（1）遍历数组，将小于 pivot 的元素交换到左侧区域。

（2）最终返回 i+1，作为 pivot 的最终位置。

3、指针 i 的作用：

（1）初始化为 low - 1，是 “小于基准区” 的尾指针。

（2）每找到一个小于 pivot 的元素，i 后移并交换，扩大 “小于区”。

【解析】代码逻辑：

循环逻辑

1、j 指针：逐个扫描每个元素。

2、判断条件：如果 arr[j] < pivot，说明这个元素应该留在左区。

3、操作：

（1）i++：扩大左区边界。

（2）swap(arr[i], arr[j])：将当前元素交换到左区。

选项分析

A.错误。筛选大于 pivot 的元素，会导致左区变大、右区变小，排序顺序错误（降序）。

B. 正确。标准升序快速排序的划分逻辑。

C. 错误。代码顺序是 swap 后 i++，逻辑上必须先 i++ 再交换。

D. 错误。只处理等于的情况，会漏掉大量元素，排序失效。

【快速排序分区示意图（以升序为例）】

初始状态

数组：[4, 2, 6, 3, 5]

• 基准 pivot = 5（最后一位）
• low = 0，high = 4
• i = low - 1 = -1
  → i 是小于区的最后一个位置
• j 从 low 开始遍历

第 1 步：j=0，arr [j]=4 < 5

• i++ → i=0
• swap (arr [i], arr [j])（自己换自己）

第 2 步：j=1，arr [j]=2 < 5

• i++ → i=1
• swap(arr[1], arr[1])

第 3 步：j=2，arr [j]=6 > 5

• 不满足，j 直接走，i 不动

第 4 步：j=3，arr [j]=3 < 5

• i++ → i=2
• swap(arr[2], arr[3])

第 5 步：j 遍历结束

最后一步：swap(arr[i+1], arr[high])把基准 pivot 放到中间

i 守小于区，j 负责探路；小的就收下，大的直接过。

第 11 题 若用二分法在[1, 100]内猜数，最多需要猜（ ）次。

A. 100

B. 10

C. 7

D. 5

【答案】C

【考纲知识点】二分法猜数（二分查找的思想）：

【解析】区间为 [1,100]，总长度 n=100。计算：

因此最多需要猜 7 次

第 12 题 下面代码实现了二分查找算法，在数组 arr 找到目标元素 target 的位置，则横线上能填写的最佳代码是（ ）。

A. int mid = left + (right - left) / 2;

B. int mid = left;

C. int mid = (left + right) / 2;

D. int mid = right;

【答案】A

【考纲知识点】二分查找（Binary Search）：

核心是计算中间位置 mid，用于将区间折半。

• 写法 1：mid = (left + right) / 2
• 缺点：当 left 和 right 很大时，left + right 可能整数溢出。
• 写法 2：mid = left + (right - left) / 2
• 优点：等价于 (left + right) / 2，但避免了整数溢出，是工程上的最佳实践。

【解析】

A.  最佳写法，避免溢出，逻辑正确。

B.  错误，mid 固定为左边界，无法折半。

C.  功能正确，但存在整数溢出风险，不如 A 安全。

D.  错误，mid 固定为右边界，无法折半。

第 13 题 贪心算法的核心特征是（ ）。

A. 总是选择当前最优解

B. 回溯尝试所有可能

C. 分阶段解决子问题

D. 总能找到最优解

【答案】A

【考纲知识点】

贪心算法（Greedy Algorithm）

• 1、核心思想：在每一步决策时，都选择当前局部最优的选项，不考虑长远影响，希望通过一系列局部最优得到全局最优。
• 2、关键特征：
1. （1）局部最优选择:每一步只看当前最好的选择。

1. （2）不可逆性：做出选择后不会回溯或修改。
2. （3）不一定全局最优：只有在满足 “贪心选择性质” 和 “最优子结构” 时，才能得到全局最优解，否则可能得到近似解。

【解析】

A. 这是贪心算法最核心的定义：每一步都选取当前情况下的局部最优解。

B. 这是回溯法（如八皇后、全排列）的特征，不是贪心。

C. 这是动态规划的特征，动态规划会记录子问题结果，而贪心不做记录。

D. 贪心算法不保证总能找到全局最优解，只有在特定问题（如活动选择、最小生成树）中才成立。

【贪心 / 回溯 / 动态规划 对比速记表】

核心一句话区别（最关键）

• 贪心：只看眼前，不回头，局部最优
• 回溯：暴力全试，不行就回头
• 动态规划：、记录子问题，不重复算，全局最优

考试一眼判断技巧

• 看到“局部最优”“当前最优” → 贪心
• 看到“尝试所有可能”“回退”“递归枚举” → 回溯
• 看到“子问题重叠”“最优子结构”“记录表” → 动态规划

第 14 题 函数 int findMax(int arr[], int low, int high) 计算数组中最大元素，其中数组 arr 从索引low 到 high ,（ ）正确实现了分治逻辑。

【答案】D

【考纲知识点】

分治算法（Divide and Conquer）核心三步：

1. 分解：将原问题拆成若干规模更小的子问题（本题拆成左右两半）。
2. 解决：递归求解每个子问题。
3. 合并：将子问题的结果合并，得到原问题的解。

【解析】

A：只返回中间元素，没有递归拆分和合并，不是分治 

B：拆分区间错误（mid-1 和 mid 会重叠），且用加法合并结果，逻辑错误 

C：用乘法合并结果，逻辑完全错误 

D：

基准条件：low == high 时返回当前元素（子问题只有一个元素）。

分解：mid = low + (high - low) / 2，拆成 [low, mid] 和 [mid+1, high]。

解决：递归求左右最大值。

合并：返回左右最大值中的较大者。

完全符合分治逻辑。

第 15 题 小杨编写了一个如下的高精度乘法函数，则横线上应填写的代码为（）。

A. int temp = c[k];

B. int temp = c[k] + carry;

C. int temp = c[k] - carry;

D. int temp = c[k] * carry;

【答案】B

【考纲知识点】

高精度乘法（逐位相乘 + 进位处理）

1. 先逐位相乘，将结果存入对应位置 c[i+j]（逆序存储）。
2. 再从低位到高位处理进位：
• 每一位的最终值 = 当前位数值 + 上一位的进位。
• 新的个位 = temp % 10，新的进位 = temp / 10。

【解析】代码中 carry 保存上一位的进位，处理当前位时：

A.  遗漏进位，无法处理进位传递。

B.  正确，包含当前位数值和进位。

C.  减法逻辑错误。

D.  乘法逻辑错误。

第 1 题 要删除单链表中某个结点`p`(⾮尾结点)，但不知道头结点，可⾏的操作是将`p->next`的数据拷贝到`p`的数据部分，将`p->next`设置为`p->next->next`，然后删除`p->next`。

【答案】√

【考纲知识点】 单链表删除结点（无头结点、非尾结点）

【解析】

在不知道头结点且p不是尾结点时，无法直接修改前驱结点指针，因此采用替身删除法：

1. 将p->next的数据拷贝到p的数据域；
2. 将p->next指向p->next->next，跳过原p->next；
3. 删除原p->next结点。此操作等价于删除p，是可行的

一、初始链表

假设有一个单链表：

现在我们想删除结点 p = B，但是：

• （1）不知道头结点
• （2）p 不是尾结点

所以不能直接找到 p 的前驱，只能用 拷贝删除法。

二、第一步：拷贝 p->next 的数据到 p

原 p 是 B：

把 C 的数据拷贝到 B：

操作：

（两个 C，一个是原来的 C，一个是拷贝到 B 的 C）

三、第二步：跳过 p->next

让 p->next 指向 p->next->next，也就是跳过第二个 C。

操作：

现在链表变成：

四、第三步：删除 p->next（第二个 C）

内存中释放第二个 C，就完成了删除 B。

最终链表：

效果总结

原本：

删除 B 后：

完全正确！

一句话总结（考试秒记）

在不知道头结点且 p 不是尾结点时：把下一个节点复制到 p，再跳过下一个节点，删它 → 等价于删除 p。

删除单链表节点的动态演示图

第 2 题 链表存储线性表时要求内存中可用存储单元地址是连续的。

【答案】×

【考纲知识点】 链表的存储结构

【解析】链表是链式存储，内存单元地址不要求连续，结点之间通过指针域相互链接；而数组是顺序存储，要求地址连续。

第 3 题 线性筛相对于埃拉托斯特尼筛法，每个合数只会被它的最小质因数筛去一次，因此效率更高。

【答案】√

【考纲知识点】 线性筛（欧拉筛）vs 埃氏筛

【解析】

第 4 题 贪心算法通过每一步选择当前最优解，从而一定能获得全局最优解。

【答案】×

【考纲知识点】 贪心算法的核心特征

【解析】贪心算法每一步选择当前局部最优解，但不一定能得到全局最优解，只有满足 “贪心选择性质” 和 “最优子结构” 的问题才能保证全局最优。

第 5 题 递归函数必须具有一个终止条件，以防止无限递归。

【答案】√

【考纲知识点】 递归函数的终止条件

【解析】递归函数必须有终止条件（基准情形），否则会无限递归，导致栈溢出错误。

第 6 题 快速排序算法的时间复杂度与输入是否有序无关，始终稳定为O(nlogn) 。

【答案】×

【考纲知识点】 快速排序的时间复杂度

【解析】快速排序平均时间复杂度为O(nlogn)，但最坏时间复杂度为O(n²)（如输入数组已完全有序或逆序时，分区退化），并非始终稳定。

第 7 题 归并排序算法的时间复杂度与输入是否有序无关，始终稳定为 O(nlogn)。

【答案】√

【考纲知识点】 归并排序的时间复杂度

【解析】归并排序采用分治思想，无论输入是否有序，时间复杂度始终稳定为O(nlogn)，不会退化。

第 8 题 二分查找适用于对无序数组和有序数组的查找。

【答案】×

【考纲知识点】 二分查找的前提

【解析】二分查找仅适用于有序数组，要求数组元素按顺序排列，否则无法通过折半缩小查找范围。

第 9 题 小杨有100元去超市买东西，每个商品有各自的价格，每种商品只能买1个，小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买，这体现了分治思想。

【答案】×

【考纲知识点】 贪心算法 vs 分治算法

【解析】每次挑最便宜的商品买，是贪心算法（选择当前局部最优：数量最多），并非分治思想；分治是将问题拆分为子问题、递归求解再合并。

第 10 题 归并排序算法体现了分治算法，每次将大的待排序数组分成大小大致相等的两个小数组，然后分别对两个小数组进行排序，最后对排好序的两个小数组合并成有序数组。

【答案】√

【考纲知识点】 归并排序的分治思想

【解析】

归并排序是典型的分治算法：

1. 分解：将数组拆成两个大小相近的子数组；
2. 解决：递归排序两个子数组；
3. 合并：将两个有序子数组合并为一个有序数组

3.1 编程题 1

时间限制：1.0 s

内存限制：512.0 MB

3.1.1 平均分配

3.1.2 题目描述

【考纲知识点】

1、贪心算法：每一步选择当前最优解，最终得到全局最优解。

2、排序算法：使用 sort 对差值数组进行升序排序，用于筛选最优选择。

3、高精度 / 大整数处理：使用 long long 类型存储数据，避免 int 溢出（题目中数值最大可达10^9 ）。

4、输入输出优化：使用 scanf/printf 处理输入输出，适配大数据量场景。

5、断言（assert）：用于验证输入合法性，确保数据在题目给定范围内。

【解题思路】

核心思想

在 2n 件物品中，恰好选 n 件卖给小 B，剩下 n 件卖给小 C，求总收入最大值。

等价变形：

步骤拆解

1、计算总和：先累加所有物品的 bi 到 ans。

2、计算差值：对每个物品 i，计算 di=ci −bi。

3、排序差值：将 d 数组升序排序，后 n 个元素即为最大的 n 个 di。

4、合并结果：将后 n 个最大的 di 加到 ans 中，得到最终最大收入。

【参考程序】

#include<bits/stdc++.h>// 万能头文件，包含所有常用库using namespace std;const int N = 2e5 + 5;   // 数组大小：2n 最大是 2e5，开足够空间int n;                   // 输入的 nlong long b[N], c[N], d[N];  // b：卖给B的价格，c：卖给C的价格，d：差值数组long long ans;           // 最终答案（必须用 long long，防止溢出）intmain(){    // 1. 输入 n    scanf("%d", &n);    // 2. 输入 2n 个 b[i]（卖给小B的价格）    for (int i = 1; i <= 2 * n; i++) {        scanf("%lld", &b[i]);    }    // 3. 输入 2n 个 c[i]（卖给小C的价格）    for (int i = 1; i <= 2 * n; i++) {        scanf("%lld", &c[i]);    }    // 4. 先把所有物品都按 b[i] 算入总收入    // 这是贪心变形的关键一步    for (int i = 1; i <= 2 * n; i++) {        ans += b[i];            // 总和初始化为全部卖B        d[i] = c[i] - b[i];    // 计算差值：如果卖给C能多赚多少    }    // 5. 对差值数组 d 从小到大排序    // 排序后，后面的数更大，代表卖给C更赚    sort(d + 1, d + 2 * n + 1);    // 6. 选最大的 n 个差值加进去    // 也就是选 n 个物品从“卖B”改成“卖C”    for (int i = n + 1; i <= 2 * n; i++) {        ans += d[i];    }    // 7. 输出最终最大收益    printf("%lld\n", ans);    return 0;}

【思路验证】

以样例输入 #2 验证：

n=2，b=[6,7,9,9]，c=[1,2,10,12]

所有 bi 和：6+7+9+9=31

di=ci−bi：−5,−5,1,3

排序后 d：−5,−5,1,3

取后 n=2 个：1+3=4

总收入：31+4=35（与样例输出一致）

【用vector实现】

#include<iostream>#include<vector>#include<algorithm>using namespace std;intmain(){    ios::sync_with_stdio(false);    cin.tie(nullptr);    int n;    cin >> n;    int size = 2 * n;    vector<longlong> b(size), c(size);    long long sum_c = 0;    // 读入 b 数组，并累加 c 的总和    for (int i = 0; i < size; ++i) {        cin >> b[i];    }    for (int i = 0; i < size; ++i) {        cin >> c[i];        sum_c += c[i];    }    // 计算差值 d[i] = b[i] - c[i]    vector<longlong> d(size);    for (int i = 0; i < size; ++i) {        d[i] = b[i] - c[i];    }    // 将差值从大到小排序    sort(d.rbegin(), d.rend());    // 取前 n 个最大的 d[i] 求和    long long sum_d = 0;    for (int i = 0; i < n; ++i) {        sum_d += d[i];    }    // 最大收入 = 所有 c 的和 + 前 n 个 d 的和    cout << sum_c + sum_d << endl;    return 0;}

3.2 编程题 2

时间限制：1.0 s

内存限制：512.0 MB

3.2.8 原根判断

3.2.9 题目描述

小 A 知道，对于质数p 而言， p的原根g 是满足以下条件的正整数：

截止 2025 年 3 月，本题可能超出了 GESP 考纲范围。在该时间点下，原根是 NOI 大纲 8 级知识点（NOI 级），而相对简单的无需原根知识的做法中，使用的费马小定理与欧拉定理也属于 NOI 大纲 7 级知识点（提高级），且均未写明于 GESP 大纲中。需要注意，GESP 大纲和 NOI 大纲是不同的大纲。

【考纲知识点】

【补充原根知识】

一、例子：判断 a=2 是不是 p=5 的原根

1、已知条件

• 质数 p = 5
• 待判断 a = 2
• 公式：φ(p) = p-1 = 4

2、原根的核心规则（背这个）

要成为原根，必须满足：对 p-1 的所有质因子 d，都不能让 a^((p-1)/d) ≡ 1 (mod p)

3、（1）步骤 1：分解 p-1

     p-1 = 4质因子只有：2

（2）步骤 2：只需要检查 a^(4/2) = a²

     计算：2² = 4 ≡ 4 mod 5 ≠ 1

（3）步骤 3：结论

            没有出现 1 → 2 是 5 的原根

二、例子：a=3 是不是 p=5 的原根？

计算：3² = 9 ≡ 4 mod 5 ≠ 1→ 3 也是 5 的原根

三、再举一个反例：a=4 是不是 p=5 的原根？

计算：4² = 16 ≡ 1 mod 5→ 出现 1 → 不是原根

• 总结： 原根怎么判？
•  p 是质数，先算 p-1。 
• 分解质因子 d。 
• 只要有一个 a^((p-1)/d) ≡ 1 → 不是 
• 全部都不等于 1 → 是！

【解题思路】

思路：（1）输入多组测试用例 a 和质数 p

（2）计算 phi = p-1

（3）分解 phi 的所有不同质因子

（4）对每个质因子 d，检查：

        a^(phi/d) mod p == 1 ?

（5）只要出现一次 1 → 不是原根

（6）全部都不是 1 → 是原根

【参考程序】

#include<cstdio>using namespace std;int a, p;       // a：待判断的数int ans;        // 答案标记：1=是原根，0=不是// ======================// 快速幂（递归版）// 计算 (b^e) mod p// ======================intfpw(int b, int e){    if (e == 0) return 1;          // 递归出口：任何数^0 = 1    int r = fpw(b, e >> 1);       // e>>1 等价于 e/2，递归算一半    r = 1ll * r * r % p;          // 平方，1ll 防止 int 溢出    if (e & 1) {                  // 如果指数是奇数，再多乘一次底数        r = 1ll * r * b % p;    }    return r;}// ======================// 检查函数// 如果 a^e ≡ 1 (mod p) → 不是原根，ans=0// ======================voidcheck(int e){    if (fpw(a, e) == 1) {        ans = 0;    }}intmain(){    int T;    scanf("%d", &T);              // 测试数据组数    while (T--) {        scanf("%d%d", &a, &p);        ans = 1;                  // 先假设是原根        int phi = p - 1;          // 质数p的欧拉函数 φ(p)=p-1        int r = phi;              // 用于质因数分解        // ======================        // 试除法分解 phi = p-1 的质因子        // ======================        for (int i = 2; i * i <= phi; ++i) {            if (phi % i == 0) {                check(phi / i);   // 检查 a^((p-1)/i) ≡ 1 ?                // 把 i 除干净，避免重复检查同一个质因子                while (r % i == 0) r /= i;            }        }        // ======================        // 如果最后剩下 >1 的质因子        // ======================        if (r > 1) {            check(phi / r);        }        // 输出答案        printf(ans ? "Yes\n" : "No\n");    }    return 0;}

【代码说明】

• 1、fpw 函数：递归实现快速幂，1ll 用于强制类型转换，防止 int 乘法溢出。
• 2、check 函数：若 a^e≡1(modp)，则 a 不是原根，将 ans 置为 0。
• 3、主函数：
• 用试除法分解 p−1，遍历所有质因数。
• 对每个质因数 d，检查 a^(p−1)/dmodp。
• 最后根据 ans 输出结果。

快速幂的本质：把大指数拆一半，少算很多次！

比如算2^8正常要乘 8 次：2×2×2×2×2×2×2×2

快速幂只需要 3 次：2^8 = (2^4)² = ((2²)²)²

第 1 层：e=5（奇数）

e≠0    折半 → e=2

递归算 fpw (2,2)

第 2 层：e=2（偶数）

e≠0    折半 → e=1

递归算 fpw (2,1)

第 3 层：e=1（奇数）

e≠0    折半 → e=0

递归算 fpw (2,0)

第 4 层：e=0

return 1

开始返回计算！

第 3 层 e=1：r = 1

平方 → 1

奇数 → 再 ×2

→ r=2

第 2 层 e=2：r=2

平方 → 4

→ r=4

第 1 层 e=5：r=4

平方 → 16

奇数 → 再 ×2

→ r=32

最终结果：32

完全正确！

• 本题样例验证
• 

与样例输出一致

【总结】

1、原根判定（质数版）

（1）若 p 是质数

（2）对 p-1 的所有质因子 d

（3）若 a^((p-1)/d) mod p ≠ 1

→ a 是 p 的原根

只要有一个等于 1 → 不是原根

2、快速幂

快速算 a^b mod p，避免爆数，时间 O (log e)

3、质因数分解

只需要检查 p-1 的不同质因子，不用遍历所有数