### 福州大学ACM/ICPC集训队资料知识点概述
#### 一、语言基础
##### C语言
在ACM/ICPC竞赛中，输入输出格式的正确使用至关重要。文档中的C语言部分提供了非常实用的代码示例，帮助选手们理解如何有效地处理输入输出。
**输入**
文档中提到了几种常见的输入处理方式：
- **循环结构**：使用`while`循环结合`scanf`函数来不断读取输入，直到满足特定的结束条件。
- **结束条件**：例如`n=0`表示输入结束；或者第一行给出测试案例的数量，之后逐个处理每个案例。
- **格式化读取**：通过在`scanf`中添加空格来过滤掉输入中的空白字符。
- **单字符读取**：使用`getch()`, `getche()`, `getchar()`等函数读取单个字符。
- **字符串转换**：`atof`, `atoi`, `atol`等函数用于将字符串转换为相应的数值类型。
- **高级字符串转换**：`strtol`, `strtoll`, `strtoul`, `strtoull`等函数允许指定基数进行转换，并且能够返回转换状态。
**输出**
文档也强调了输出格式的重要性，尤其是对于多个测试案例之间的输出间隔处理。如：
- **输出格式**：每完成一个案例的输出后，通常需要输出一个空行来隔开不同的测试案例。
- **特殊输出格式**：如题目要求，可能还需要输出特定的格式，例如每段输出后加入空行。
---
#### 二、数据结构
这部分涵盖了ACM/ICPC竞赛中常见的数据结构，包括但不限于：
- **哈希表**（Hash）：一种高效的数据查找方法，适用于解决特定类型的查询问题。
- **树形并查集**：结合了树结构和并查集的优势，用于处理动态集合问题。
- **最大堆**：一种特殊的完全二叉树结构，其根节点始终是最大的元素。
- **排列与阶乘进制**：涉及到排列组合的问题，阶乘进制是一种表示大数的方法。
- **基于空间分割的数据结构**：如四叉树或八叉树，用于解决涉及二维或多维空间的问题。
#### 三、基础算法
本章节列举了一些基本但重要的算法，这些算法在解决ACM/ICPC问题时极为常见：
- **搜索算法**：如深度优先搜索（DFS）、广度优先搜索（BFS）等，用于遍历图或其他数据结构。
- **动态规划**：一种优化技术，通过对子问题的重叠性质进行利用，从而避免重复计算。
- **解线性方程组**：利用高斯消元等方法解决线性方程组问题。
- **LIS 最长非降子序列**：寻找序列中最长的非降子序列。
- **用归并排序求逆序数**：逆序数常用于评估排序难度。
- **日期计算**：处理与时间相关的计算，例如计算两个日期之间的天数差。
- **高精度计算**：当常规的整数或浮点数无法表示足够大的数值时，需要使用高精度计算方法。
#### 四、图论
图论是ACM/ICPC竞赛中的重要组成部分，涉及到各种图的相关概念和算法：
- **最短路径**：如Dijkstra算法、Floyd-Warshall算法等，用于找到两点间最短路径。
- **最小生成树**：如Prim算法、Kruskal算法等，用于构建图的一个子集，使得该子集中所有顶点都相连且边的总权重最小。
- **连通性**：确定图是否连通或找出连通分量。
- **网络流算法**：如Ford-Fulkerson算法，用于计算网络中的最大流量。
- **二分图匹配**：解决二分图中的匹配问题。
- **独立集与支配集**：寻找图中没有相邻边的顶点集或能够覆盖所有顶点的顶点集。
#### 五、计算几何
计算几何部分关注于解决与几何对象有关的问题：
- **基础知识**：涉及向量、点、线段等的基本定义和运算。
- **几何图形的包含关系**：判断一个点是否在某个几何形状内部等。
- **求凸包**：使用Graham算法等方法找到点集的凸包。
- **注意事项**：在处理浮点数运算时需要注意精度问题。
#### 六、数论
数论是ACM/ICPC竞赛中的另一重要领域：
- **欧几里德算法**：求最大公约数的经典算法。
- **模线性方程**：解决形如ax ≡ b (mod m)的方程。
- **中国剩余定理**：用于解决同余方程组。
- **模运算**：包括快速幂模运算等技巧。
- **素数判定**：如Miller-Rabin素性测试算法。
- **分解质因数**：如Pollard's rho算法。
- **初等数论**：包括基本的数论概念和定理。
#### 七、组合数学
组合数学部分关注计数问题及其相关技巧：
- **常用公式**：如组合数公式、排列公式等。
- **Fibonacci数列**：递推定义及其性质。
- **母函数**：一种解决组合问题的有效工具。
以上是根据福州大学ACM/ICPC集训队资料整理的主要知识点。这些内容不仅涵盖了理论知识，还包括了大量的实践案例和代码示例，对于学习ACM/ICPC竞赛的选手来说是非常宝贵的资源。
