全站题解与技术索引

按 GESP 等级、洛谷题号与技术栈极速定位 · 严格 C++11 规范

1,027原创文章
550GESP 考级
14 年始于 2012
GESP 五级
算术基本定理(唯一分解定理)与约数个数、约数和公式推导
在数论与计数类考题中,许多同学一看到“求 360 有多少个正约数、约数和是多少”或“把一个高达 10^12 的整数拆成质因数乘积”,就陷入了两头踩坑的窘境:手写质因数分解代码时,枚举完 i <= n / i 后忘了补收尾的 if (n > 1),结果在 36 上测试完美...
GESP 五级
从 O(√n) 试除法到埃氏筛、欧拉线性筛——为什么一行 break 能做到严格 O(n)?
在质数判定与批量求质数的考场实战中,许多同学以为“质数很简单”,结果一交代码就撞上各种离奇失分:判单个大数是否为质数时,循环条件顺手写了 i * i <= n,碰上 32 位最大梅森素数 2147483647 时 46341 * 46341 瞬间撑爆 int 回绕成负数...
GESP 五级
欧几里得辗转相除法原理、时间复杂度证明与防溢出 LCM 写法
在面对“求两个大整数 a, b(最高可达 10^18)的最大公约数与最小公倍数”时,如果还停留在从 min(a, b) 一路递减枚举的暴力试除法,单次查询 O(min(a, b)) 的耗时足以让程序瞬间 TLE(运行超时);而哪怕背下了短短一行的欧几里得辗转相除法,不少...
GESP 五级
同余定理与取模铁律——为什么减法取模要先 +MOD,而除法绝对不能直接取模?
在信奥赛场上,几乎每一道递推计数、动态规划或数论求值题的末尾都会印着那句熟悉的提示:“由于答案可能很大,请输出答案对 10^9 + 7(即 1000000007)取模后的结果。” 许多同学看到这句话暗自窃喜,以为只要在 cout 输出前顺手补一个 % MOD 就万事大吉...
GESP 五级
二分答案——如何把棘手的“求最值问题”转化为简单的“是非判定问题”?
给你 n 根长短不一的原木,要求切成至少 k 段等长的小木头,每段最长能切多少厘米?或者河道中分布着 n 块岩石,最多允许移走 m 块,如何让选手每次跳跃的“最短距离尽可能大”?许多同学面对这类复杂的全局最优化问题,第一反应是硬推贪心公式或设计动态规划状态,结果越推越乱...
GESP 五级
二分查找为什么会死循环?mid=(l+r)/2 与 (l+r+1)/2 终极判定指南
算法竞赛圈流传着一句经典的自嘲:“二分查找思路只需十秒钟,调试边界死循环却要两小时!”为什么明明只是在一个有序数组里折半找数,有的时候写 mid = (l + r) / 2 顺畅通关,有的时候把 r = mid 换成 l = mid,程序就瞬间卡死在 while (l...
GESP 五级
快速排序(Quick Sort)基准划分原理、不稳定性与 O(n^2) 退化陷阱
为什么在工程实践与算法竞赛中,快速排序(Quick Sort) 无需像归并排序那样额外开辟长度为 n 的辅助数组 tmp[],就能以极小的常数因子跑出 O(n log n) 的飞快速度,稳坐“通用原地排序之王”的宝座;可一旦某个同学手写快排时图省事固定挑选区间首元素 a...
GESP 五级
分治思想与归并排序(Merge Sort)——顺手秒杀“逆序对”统计
当题目给出的数据规模从 n = 1000 跃升到 n = 10^5 时,无论是冒泡排序、直接插入排序,还是用双重 for 循环暴力枚举统计“逆序对”,运算次数都会瞬间飙升至 (n(n-1)/2) ≈ 5 × 10^9 次,在 1 秒时限面前毫无悬念地触发 TLE(运行超...
GESP 四级
排序的“稳定性”到底有什么用?冒泡、选择、插入排序深度辨析
为什么只给纯整数数组 [5, 3, 5, 2] 排个序,教材和真题却总要喋喋不休地追问“两个 5 排完之后谁在谁前面”?两个一模一样的数字 5 颠倒了顺序,表面上看结果不还是 [2, 3, 5, 5] 吗?然而一旦进入真实教务系统或信奥结构体排序场景——比如教务老师先将...
GESP 五级
从 O(2^n) 到 O(n) 的奇迹——重叠子问题与记忆化搜索
为什么一段只有 5 行的斐波那契递归代码 return fib(n - 1) + fib(n - 2);,当输入 n = 10 时瞬间出解,一旦输入 n = 45 就会触发超过 22 亿次函数调用,把评测机死死卡在 TLE(运行超时)?更神奇的是,为什么在不改变递归主体...
GESP 五级
递推 vs 递归——如何手画“递归调用树”秒杀初赛阅读程序题?
为什么在考场上遇到一句看似简单的 return f(n - 1) + f(n - 2);,有些同学在脑子里绕了三层就彻底“死机”,完全算不清函数到底被调用了多少次?为什么仅仅把 cout << n; 放在递归调用语句的前面和后面,打印出来的数字顺序就会发生天翻地覆的“逆...
GESP 四级
如何根据数据范围 N 反推算法?时间与空间复杂度估算实战
为什么在考场上拿到一道题,有经验的高手还没读完题面,仅仅扫了一眼最下方的“数据范围:对于 100% 的数据,1 ≤ N ≤ 10^5”,就能在 3 秒内断言:“这题绝对不能写双重循环冒泡排序,必须用 O(N log N) 的归并/快排或二分查找”?为什么你的代码逻辑在本...
GESP 四级
GESP四级 / CSP-J 复赛必背:freopen 文件重定向标准写法与考场 0 分爆零避坑指南
为什么每年 CSP-J/S 第二轮复赛成绩公布后,总有一大批平时模拟赛能拿二三百高分的选手,打开成绩单却看到刺眼的 4 题全 0 分(爆零)?为什么你的算法逻辑完美无缺、本地小样例全过,仅仅因为在交卷前忘记删掉 // freopen("apple.in", "r", s...
GESP 四级
结构体多关键字排序与 std::sort 自定义 cmp 的“严格弱序”铁律
为什么在 C++ 中定义一个包含 char c1; int x; char c2; 三个成员的结构体(1 + 4 + 1 = 6 字节),用 sizeof 测出来的内存体积却是 12 字节,而仅仅把 int x 挪到第一行变成 int x; char c1; char...
GESP 三级
字符数组结束符 '\0' 陷阱与 strlen 放循环条件导致的超时惨案
为什么在 C++ 中写下 char a[] = "GESP"; 和 char b[] = {'G', 'E', 'S', 'P'};,明明看起来都是 4 个字母,用 sizeof(a) 测出来是 5,而 sizeof(b) 却是 4?更可怕的是,如果对 b 调用 str...
显示 1–15 / 共 1,027 篇原创内容
1 / 69
OneCoder GESP/CSP 学习公众号二维码
GESP / CSP 学习公众号

微信扫码关注,同步获取每日考纲精讲与真题解析推送。

技术交流与考级答疑群

C++ GESP/CSP 群(688906745)· Java/Python 群(982860385)

全站目录与专题直达

始于 2012 年的全部 1,027 篇技术笔记按年份与多级目录归档。