夜雨聆风学习资料网

ARTICLE · 1376679

GESP C++ 五级高频考点与难点解析

GESP C++ 五级高频考点与难点解析

一、考知识内容

知识块

具体知识点

要求层次

初等数论

素数与合数、约数与倍数、最大公约数与最小公倍数、同余与模运算、质因数分解、唯一分解定理

必考,编程题高频落点

数论算法

辗转相除法(欧几里得算法)、埃氏筛法、线性筛法

必考,选择题高频填空

线性表

单链表、双链表、循环链表的创建、插入、删除、遍历、反转

必考,选择题稳定占位

高精度

用数组模拟大整数的加、减、乘、除

常考,多出现在填空与编程

算法思想

二分查找与二分答案、贪心算法、分治算法(归并排序、快速排序)、递归

必考,选择与编程双向覆盖

复杂度

算法复杂度估算(含多项式、指数、对数复杂度)

常考,选择题每年出现

二、考点梳理

GESP C++ 五级的核心特点是数论权重极高,同时开始系统考察基础数据结构(链表)与中阶算法思想(二分、贪心、分治、递归)。备考时应将数论作为绝对重点,并确保能熟练手写链表操作与排序算法模板。

(一)初等数论(最高频)

这是五级的分值大头。需要掌握素数与合数、最大公约数与最小公倍数、同余与模运算、质因数分解。具体算法上,辗转相除法(欧几里得算法)、埃氏筛法与线性筛法、唯一分解定理是必须能够独立实现的。从真题统计看,质因数分解类题目几乎每次必考,属于必须拿下的基础分。

扩写部分按“定义—结论—算法”三层展开,每一层都可能直接变成一道选择题。

1. 整除、约数与倍数

若整数 a 除以非零整数 b 的余数为 0,称 b 整除 a。约数是能整除 n 的正整数,倍数是 n 的整数倍。求一个数的全部约数用试除法,只需枚举到 √n:每一对约数成对出现,复杂度 O(√n)。这个“成对出现”的思想,同时也是素数判定与质因数分解的算法基础。

常用结论必须脱口而出:1 既不是素数也不是合数;2 是唯一的偶素数;任何大于 1 的整数都可以唯一分解为若干素因子之积(算术基本定理);若 n = p1a1 ×p2a2 × … × pkak,则约数个数为 (a₁+1)(a₂+1)…(aₖ+1),约数之和为各项等比数列之积。在 1 至 n 中,p 的倍数共有 ⌊n/p⌋ 个,这条结论常被用来做计数题。

2. 素数判定

朴素写法枚举 2 到 n-1;标准写法枚举到,因为若 n 有大于的约数,必有一个小于的对应约数。再进一步只试 2 与奇数,复杂度降为 O()。三个边界必须记牢:n < 2 直接返回 false;n == 2 返回 true;循环条件写成 (long long)i * i <= n,防止 i 接近 2×109时平方溢出成负数而陷入死循环。

3. 最大公约数与最小公倍数

辗转相除法的核心恒等式是 gcd(a, b) = gcd(b, a mod b),终止条件是 b == 0,此时 a 即为答案。手算时注意每一步只保留两个数:以 gcd(84, 60) 为例,84 ÷ 60 余 24,第二步便得到 24;再 60 ÷ 24 余 12,最后 24 ÷ 12 余 0,答案 12。真题就考过“第二步计算的是哪个数”,失分者往往把商或余数记混。

最小公倍数用 lcm(a, b) = a / gcd(a, b) * b。先除后乘是硬性要求:直接写 a * b 在 a、b 均达 10⁹ 时会先溢出再除,结果错误且难以察觉。

4. 同余与模运算

同余描述两个整数除以同一正整数后余数相同。模运算对加、减、乘封闭:(a ± b) mod m、a * b mod m 都可以边算边取模,这条性质是处理大数计数与高精度取模的关键。两条注意:一是减法取模需写成 (a - b + m) % m,避免 C++ 中负数取模得到负值;二是模运算对除法不封闭,除以一个数需要逆元,属于六级以后的内容,五级遇到时通常可以用“乘以逆元”的等价变形或直接换算法绕开。

5. 质因数分解与唯一分解定理

试除法分解:i 从 2 枚举到,能整除就反复除尽并统计指数,循环结束后若 n > 1,剩下的必为素数,单独计入。这条“剩下的必为素数”是最容易被忽略的收尾,很多实现漏掉它,导致 26 被分解成 2 与 13 之外还丢了一项。分解结果通常存成 pair<底数, 指数> 数组,后续求约数个数、约数之和、欧拉函数都从它出发。

6. 两种筛法

埃氏筛的思想是“素数的倍数一定不是素数”,把 2 到 √n 中的素数依次筛掉其倍数。内层循环必须从 i × i 开始,因为 i × 2、i × 3、…、i × (i-1) 已被更小的素因子筛过,重复筛只是浪费。其复杂度为 O(n log log n),几乎线性。

线性筛(欧拉筛)保证每个合数只被它的最小质因子筛掉一次,因此复杂度严格为 O(n)。实现的关键是内外两层:外层枚举 i,i 是素数则入表;内层用已得素数 p 去筛 i × p,并判定“若 i % p == 0 立即 break”。这个 break 正是“最小质因子”的体现——若不跳出,同一个合数会被更大的质因子重复标记。

对比项

埃氏筛

线性筛

核心思想

素数的倍数标记为合数

每个合数只由最小质因子筛一次

内层起点

i × i

i × p,p 取自已得素数表

复杂度

O(n log log n)

O(n)

代码量

短,易默写

稍长,重点在 break 条件

适用场景

n ≤ 10⁷ 时完全够用

n 更大或需要严格线性时使用

 (二)数据结构:线性表与链表

链表部分要求掌握单链表、双链表、循环链表的创建、插入、删除、遍历与反转。链表是五级唯一明确要求“手写结构”的数据结构,选择题常年围绕它出题。

1. 数组与链表的取舍

数组支持 O(1) 随机访问,但插入删除需要移动元素,且容量需要预估;链表插入删除为 O(1)(前提是已持有目标位置的前驱指针),但不支持随机访问,查找需 O(n),每个结点还要额外付出指针空间。真题第一题问“链表不具备的特点”,答案就是“可随机访问任何一个元素”。这张对照表建议直接背下来。

2. 单链表与哨兵结点

单链表由数据域与指针域组成,head 指向首结点,尾结点的 next 为 nullptr。带哨兵(头结点,不存数据)的写法能统一“在头部插入”与“在中间插入”的逻辑,减少特判,是考场更稳的选择。反转单链表用三指针迭代:prev 初始为空,cur 指向头,循环中先存 nxt,再让 cur->next = prev,最后整体后移。三步顺序不能颠倒。

3. 双向链表

双向链表每个结点有 prev 与 next 两个指针。在 p 之后插入 s 需要四步:s->next = p->next;s->prev = p;若 p->next 非空则 p->next->prev = s;最后 p->next = s。删除 p 需要三步:p->prev->next = p->next;p->next->prev = p->prev;delete p。真题常把其中一步写错让你判断——判断技巧是“先接好两边,再断开自己”,任何先改自身指针导致后继地址丢失的写法都是错的。

4. 循环链表与约瑟夫环

循环链表尾结点的 next 指回 head,空表时 head->next 指向 head 自身。用它模拟约瑟夫环时,每次数到第 m 个人就删除该结点,删除后指针要复位到被删结点的下一个位置,否则会跳过一人。若只求最后剩下的编号,直接用递推公式 f(1)=0,f(i)=(f(i-1)+m) % i,答案 f(n)+1,复杂度 O(n)、空间 O(1),比链表模拟稳得多。

(三)高精度运算

高精度方面,考纲明确要求能用数组模拟大整数的加、减、乘、除运算,重点在于处理进位、借位以及字符串与数组的转换逻辑。

统一的实现约定是“逆序存储”:读入字符串后从末位向前放入数组,使 a[0] 存个位。这样进位向高位自然延伸,只需在末尾 push_back,无需整体搬移。字符转数字用 c 减去字符零的 ASCII 值(即 c - 48),输出时从最高位倒序打印。

四个运算各自的要点:加法逐位相加并维护进位 t,循环条件要包含 t 非零,否则最高位进位会丢失;减法要求被减数不小于减数,逐位做 t = a[i] - t - b[i],借位通过 (t + 10) % 10 与 t < 0 判定,结果需去除前导零但至少保留一位;乘法本质是双重循环的卷积,c[i+j] += a[i] * b[j],最后统一进位,复杂度 O(nm),中间累加值可能达到 81 × 位数,必须用 long long 暂存;除法从高位向低位试商,维护余数 r,c[i] = r / b,r %= b。

进阶一点可以了解“压位”:每位存 4 位十进制,一次运算处理 4 个数字,常数降到四分之一。考试不要求,但写大题时是省时的技巧。

(四)二分查找与二分答案

需要理解并能应用二分查找与二分答案(注意边界条件的处理)。二分的两处坑是判断条件与区间收缩方向,写错任意一处都会死循环或漏解。

二分查找的前提是序列有序。标准写法维护左闭右开区间 [l, r),mid = l + (r - l) / 2 可避免 l + r 溢出;判断 a[mid] < x 则 l = mid + 1,否则 r = mid,循环结束时 l 即为“第一个大于等于 x 的位置”。若要“最后一个小于等于 x 的位置”,改判 a[mid] <= x 时 l = mid + 1,最后返回 l - 1。两种写法对应两种语义,不能混用取整方向。

二分答案的本质是“把求解转化为判定”:当答案具有单调性(x 可行则更大的 x 也可行,或反之),就可以在答案值域上二分,每次调用 check() 判断可行性。三步固定动作:确定答案的下界与上界;写出单调的 check();决定返回的是“最小可行值”还是“最大可行值”。题目中“最大化最小值”“最小化最大值”“最小的最大载重”这类字眼,几乎都是二分答案的信号。

二分次数可以直接算:在 1 到 100 之间猜数,最多需要 ⌈log₂(101)⌉ = 7 次,因为 2⁷ = 128 > 100。这类估算题几乎每年都出现,记住 ⌈log₂(n+1)⌉ 即可秒答。

(五)贪心算法

贪心算法要求理解局部最优到全局最优的推导,而不是记住几个模型。判断一道题能否贪心,看两个条件:贪心选择性质(每一步的最优选择能导向全局最优)与最优子结构(子问题的最优解可组合成整体最优解)。

常用证明方法是交换论证:假设最优解与贪心解在第一个不同处不同,把最优解中的选择换成贪心的选择,证明结果不变差,从而说明贪心解也是最优。会写这段论证,判断题里“贪心一定能得到全局最优”这类表述就不会含糊。

经典模型

贪心策略

备注

区间调度(最多不重叠区间)

按右端点升序,能选就选

按左端点排序是常见错误

区间选点(最少点覆盖所有区间)

按右端点升序,未覆盖则在该右端点放点

与区间调度同构

部分(分数)背包

按单位价值降序装填

0-1 背包不可贪心,是经典反例

任务截止与利润

按利润降序,占用截止日前最近的空槽

真题判断与选择题均出现

排序不等式

大配大、小配小

常与“最大收益”类编程题结合

(六)分治与排序

分治的具体落点通常是手写归并排序和快速排序,并理解其 O(nlog n) 的复杂度来源。分治三步是固定框架:分解为规模更小的同类子问题、递归求解、合并结果。复杂度由递归式 T(n) = 2T(n/2) + O(n) 推出 O(n log n),共 log n 层、每层 O(n)。

归并排序先递归排好左右两半,再用双指针合并,合并过程需要 O(n) 辅助空间,因此空间复杂度 O(n)。它的比较在 a[i] <= a[j] 时取左边,等号保证了稳定性;同时可以在合并时统计逆序对:当取右边元素时,左边剩余元素个数即为新增逆序对数。

快速排序按基准划分后递归两侧,平均 O(n log n),最坏 O(n²)(数组已有序且固定取端点为基准时),空间 O(log n) 来自递归栈。它不稳定。工程写法取随机基准或三数取中,可把退化概率降到很低;面对大量重复元素时用三路划分更稳。

排序算法

平均时间

最坏时间

额外空间

稳定性

冒泡排序

O(n²)

O(n²)

O(1)

稳定

插入排序

O(n²)

O(n²)

O(1)

稳定

选择排序

O(n²)

O(n²)

O(1)

不稳定

归并排序

O(n log n)

O(n log n)

O(n)

稳定

快速排序

O(n log n)

O(n²)

O(log n)

不稳定

(七)递归

递归要求能分析时间与空间复杂度,并了解栈溢出风险。写递归先写三件事:终止条件、本层做什么、如何缩小规模。缺终止条件会无限递归直至栈溢出;规模没有严格变小也会同样崩掉。

递归的代价是调用栈:每次调用都要保存返回地址、参数与局部变量。一般环境的主线程栈在 1 至 8 MB 之间,单个栈帧按几十字节估算,深度超过 10⁵ 就有风险。因此递归实现的 gcd 虽简洁,工程上仍推荐迭代;递归求阶乘在 n 较大时同样不可靠。

并非所有递归都能直接改循环。线性递归(如阶乘、斐波那契、gcd)容易改写;树形递归(如快速排序、汉诺塔、二叉树遍历)需要显式栈或队列才能等价转换。这点常以判断题出现:“所有递归都能改循环”是错的。

(八)算法复杂度估算

五级明确要求估算含多项式、指数、对数项的复杂度。判断标准很简单:看循环的层数与每层的规模变化。单层循环 O(n);两层独立循环 O(n²);循环变量每次乘 2 或除 2,层数为 log n;递归每次把问题折半且合并代价 O(n),得 O(n log n);枚举子集得 O(2ⁿ)。

复杂度

n = 10⁵ 时的量级

常见来源

O(log n)

约 17 次

二分查找、按位处理

O()

约 316 次

试除法判素数、分解质因数

O(n)

105

线性筛、单层遍历

O(n log n)

约 1.7×106

归并/快排、排序后贪心

O(n)

约 3.2×107

对每个数试除

O(n²)

1010(必然超时)

双重循环、冒泡/插入/选择排序

O(2n)

仅 n ≤ 20 可用

子集枚举

三、难点与易错点

(一)数论算法的实现细节

埃氏筛的内层循环从 i × i 开始而非 2i,是因为更小的倍数已被更小的质因子筛过;线性筛则要确保每个合数只被其最小质因子筛掉。这些原理性细节在选择题中反复出现。此外,递归实现的 GCD 虽然简洁,但深度过大时存在栈溢出风险,迭代写法在工程上更稳妥。

在此之外,还有六处高频翻车点,建议逐条对着自己的代码检查。

1.n < 2 未特判。

2.筛法数组越界或 i * i 溢出。当 i 接近 4.6×10⁴ 时 int 平方即溢出,循环条件应写 (long long)i * i <= n。

3.线性筛内层漏写 if (i % p == 0) break,导致同一合数被多次标记,复杂度退化为 O(n log n) 甚至更高。

4.分解质因数漏掉收尾的 n > 1。剩余部分必为素数,必须单独计入。

5.lcm 写成 a * b / gcd,先乘后除导致溢出。

6.gcd 传入负数时结果异常,需先取绝对值;gcd(0, 0) 按定义应为 0,需特判。

(二)链表指针操作

双向链表的插入与删除涉及多个指针的更新顺序,顺序错误极易导致断链或内存错误。选择题常考“在已知结点后插入”的 O(1) 操作,以及删除结点时 prev->next 与 p->next 的更新先后逻辑。循环链表处理约瑟夫环时,删除结点后指针的复位也是常见失分点。

补充几个必须形成条件反射的细节:删除结点前先保存 p->next,否则 delete p 之后无法访问后继;删除头结点必须同步修改 head;删除尾结点必须把 next 置空,否则链表出现野指针;用 new 申请而忘记 delete 会造成内存泄漏,选择题会以“程序运行结果正确但有内存问题”的形式出现。另外,单链表若要 O(1) 删除某结点而不给头指针,可以“偷梁换柱”:把后继的值复制到当前结点,再删后继——这个方法不能用于尾结点,真题判断题正是考这一点。

(三)二分边界与贪心反例

二分查找中,查找“第一个大于等于 x 的位置”与“最后一个小于等于 x 的位置”时,mid 的取整方向与 l/r 的更新规则不同,混淆会导致死循环或漏解。贪心算法方面,需警惕“硬币面值特殊时贪心不一定最优”这类反例,理解贪心适用的条件(最优子结构)而非盲目套用。

二分的三条自查规则值得贴在草稿纸上。第一,区间语义必须写注释,是 [l, r] 还是 [l, r)。第二,循环条件与更新方式必须配套:while (l < r) 配 l = mid + 1 / r = mid;while (l <= r) 配 l = mid + 1 / r = mid - 1。第三,答案值域上界不能凭感觉,要按题目最大值留足,且用 long long。

贪心的经典反例不止硬币:0-1 背包按单位价值贪心会错;区间调度按左端点排序会错;任务调度若按耗时升序而非利润降序也会错。判断题里“每次选当前最优就一定能得到全局最优”永远是否定答案。

(四)高精度常见错误

忘记逆序存储,导致进位方向反了,答案整体颠倒。

加法循环条件只写到 max(len) 而没有 || t,最高位进位被丢弃。

减法未处理前导零,输出“07”一类结果被判错;或全零时把结果删成空数组。

乘法 c[i+j] 用 int 累加,位数一多就溢出,应改 long long。

除法忘记“从高位开始”,写成低位试商,商完全错误。

读入含前导零或输入为 0 时,长度判断出错。

(五)排序与递归常见错误

排序方面:把归并写成不稳定版本(合并时用 < 而非 <=);快排固定取端点做基准,遇到有序数据退化为 O(n²);partition 中 i 与 j 的移动顺序写反导致越界;把“选择排序不稳定”记成稳定。递归方面:缺少终止条件;终止条件写错边界(如 n == 1 而非 n <= 1),n 为 0 时无限递归;在递归中使用全局变量却未在每层复位;误以为递归一定比循环慢,其实复杂度相同,差别在常数与栈空间。

(六)易错点速查表

下面这张表建议单独打印,考前只看它。

现象

根本原因

对策

筛法结果少了2或多了 1

未特判 0、1 与 2

先置 sP[0]=isP[1]=false,保留 2

程序在 n 较大时莫名死循环

i * i 溢出成负数

循环条件转 long long

线性筛比预期慢

缺少 break 条件

i % p == 0 立即跳出

大数乘法结果错位

未统一逆序存储

读入即反转,输出再反转

二分死循环

区间语义与收缩方向不匹配

固定一套模板并写注释

删除结点后程序崩溃

先 delete 后访问后继

先存 next,再断链,最后 delete

有序数组快排超时

基准取端点导致退化

随机基准或三数取中

归并排序结果不稳定

合并时用了严格小于

改成 a[i] <= a[j] 取左

贪心答案偏小

未验证贪心选择性质

先构造小反例再动手

编程题过不了大数据

中间量用 int 溢出

全程 long long

GESP C++ 六级考点、难点与备考要点
CSP-J/S 2026第二轮满分名单

江苏CSP-J/S 2026第二轮评级名单

CSP-J/S 2026第二轮评级规则

全国青少年信息学奥林匹克联赛(江苏赛区)NOIP2026参赛名单

NOIP 2026报名通知及各省参赛名额分配方案

全国青少年信息学奥林匹克联赛(NOIP)2025试题

全国信息学奥林匹克联赛NOIP 2024 真题

CSP-S2026第二轮真题

CSP-J2026第二轮真题

CSP-J/S2025第二轮评级规则级各省分数线

NOI 2027名额分配测算方案

NOI2027江苏省代表队选拔方案

CSP-J2025第二轮真题

CSP-J/S2025第二轮江苏获奖选手全名单

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料