csp-s · 相关章节

复杂度分析是区分"会不会写"和"写得好不好"的分水岭。初赛考概念、复赛考直觉：一眼看出算法会不会超时，靠的就是本章的渐进分析与递推求解。

CSP-S 复赛大量题目本质是一道数学题：模运算、组合数、计数、博弈。把数学工具练顺，很多"难题"会变成模板拼装。

算法是 CSP-S 复赛的"兵器库"。本章按"思想 → 模板 → 真题"组织，覆盖排序、二分、前缀和、双指针、倍增、分治、搜索、贪心、动态规划、字符串进阶与图论进阶。每个知识点都给出可直接抄写的 C++17 模板。

本章定位（CSP-S）：在 CSP-J 的"常识记忆"基础上，进一步理解计算机系统的工作原理、层次结构与性能度量。初赛常考人物/事件/分类的辨析，复赛虽不直接考本章，但存储层次、局部性、调度等思想会直接影响你的代码性能与对评测机的理解。

本章定位（CSP-S）：在 CSP-J "认识部件名称"的基础上，深入理解 CPU 如何一条条执行指令、指令如何找到操作数（寻址）、为什么要分存储层次与 Cache、Cache 怎么映射与算命中率、以及 中断/异常 如何让外设与 CPU 协作。初赛常考指令周期阶段、寻址方式辨析、Cache 命中率计算、流水线加速比；其中 Cache 与流水线是 CSP-S 相对 CSP-J 明确加深的考点。

本章定位（CSP-S）：在 CSP-J "会写 C++ 基础语法"的基础上，理解语言是怎么变成可执行程序的（编译/解释/汇编）、C++ 的引用/指针与内存布局、常用 STL 容器的底层与复杂度、以及 软件工程与复杂度权衡 的基本思想。初赛常考翻译方式辨析、语言分类、复杂度估算；复赛虽不考名词，但"选对容器/算对复杂度"直接决定你的程序能不能过。

本章是 CSP-S 初赛与复赛都会涉及的基础理论。初赛常考进制互化计算、原/反/补码、IEEE 754 浮点表示、校验码；复赛虽然不直接考，但位运算（第5章）、哈希、状态压缩都建立在"数据如何用二进制表示"之上。本章把每个知识点都配上可编译的 C++17 示例代码，建议亲手跑一遍加深理解。

位运算是 CSP-S 复赛里性价比最高的工具之一：状态压缩 DP、树状数组、哈希去重、快速幂、图形/棋盘类题目都依赖它。本章先把"数值在机器里怎么存"（原/反/补/移码）讲清楚，再系统整理位运算的语法、技巧与真题模型。每个知识点都配可编译的 C++17 示例。

计算机网络是 CSP-S 初赛重点（概念辨析、IP/子网计算、协议归属），复赛中虽不直接考，但理解网络分层有助于看懂题目背景（如"给定一个网络拓扑求最短路""按 IP 分组"类建模题）。本章把每个可计算的知识点都写成 C++17 示例，方便亲手验证。

因特网（Internet）是 CSP 初赛的常考理论章节，概念多、易混淆（协议归属、域名结构、邮件协议栈）。复赛虽不直接考，但理解"域名↔IP""URL 结构""服务类型"有助于读懂题目背景。本章把每个可程序化的知识点都写成 C++17 示例，方便亲手验证。

线性数据结构是 CSP-S 复赛与初赛的共同核心：数组、链表、栈、队列、哈希表、字符串。复赛中栈（递归/表达式/DFS）、队列（BFS）、哈希表（判重/计数）、字符串（模式/前缀）几乎每场必考；初赛则偏好考"概念辨析 + 计算"（哈希冲突、子串数、出栈序列、复杂度）。

树和图是 CSP-S 复赛的骨架：线段树/平衡树/堆/并查集/Trie 都建立在"树"上；最短路、最小生成树、拓扑排序、强连通分量都建立在"图"上。本章把每个知识点写成可编译 C++17 示例，并把 6 道经典初赛选择题整理为随堂检测（每题附可展开解析）。

本章把 CSP-S 提高组复赛里反复出现、可以直接套用的核心代码片段集中成「模板库」。