GESP 八级备考攻略

八级是 GESP 的天花板,难度已经接近 CSP-J 中上、甚至 CSP-S 入门。到这一级,拼的是基本功的体系化 + 刷题量,和信息学竞赛几乎无异。

八级到底考什么

• 图论:最小生成树(Kruskal)、Dijkstra 最短路
• 数论:快速幂(费马小定理求逆元)、线性筛
• 组合数学:排列组合、二项式定理、杨辉三角 / 组合数递推
• 计算几何(三角形面积、点与圆的关系)
• 复杂度分析、二分答案、栈序列合法性、构造 / 析构顺序

编程题两道,如"生成树计数"(生成树相关,难度顶格)"末班车"(最短路 / 时序建模)。

三条体系化主线

1. 图论：Kruskal 按边权排序 + 并查集,贪心选边建最小生成树;Dijkstra 用优先队列优化,求非负权单源最短路。两套模板务必写熟。

2. 数论：快速幂是基础;结合费马小定理(a^{p-1} \equiv 1 \pmod p,p 为质数)可求逆元,处理"除法取模";线性筛一次性求素数 + 最小质因子。

3. 组合数学：杨辉三角递推 C_n^k = C_{n-1}^{k-1} + C_{n-1}^k,配合逆元求大组合数取模,是竞赛常规操作。

备考建议

• 三条线(图论 / 数论 / 组合)各自成体系地刷,别东一榔头西一棒。
• 直接对标 CSP-J 真题拉高上限,GESP 八级和 CSP 可以一起备。
• 编程题靠综合建模能力,平时多写整题、多调试。

行动清单

• ☐ Kruskal + Dijkstra 模板写熟
• ☐ 快速幂 + 费马逆元 + 线性筛
• ☐ 组合数递推 + 逆元;对标 CSP-J 真题

到了八级,拼的是体系和题量。和 CSP 备考一起打,事半功倍。