初赛知识点 ¶

约 1333 个字预计阅读时间 4 分钟

Linux 指令 ¶

cd: 交换工作目录
pwd: 显示工作目录
mkdir: 创建目录
rmdir: 删除空目录
rm: 删除非空目录
file: 查看文件类型
ls: 列出当前目录中的文件和子目录
touch: 创建空白文件
cp: 复制文件或目录
mv: 移动文件或目录
man: 查看命令的使用文档
cat: 正向显示文件内容
tac: 逆向显示文件内容
head: 显示文件前几行内容
tail: 显示文件后几行内容
more/less: 翻页显示文件内容
gedit: 图形化文本编辑器
touch: 创建空白文件
chmod: 改变文件权限
chown: 改变文件所有者
chgrp: 改变文件组
compress/gzip/bzip2: 压缩文件
tar/bzcat/cpio: 打包 / 解压文件

GCC 编译选项 ¶

-c: 编译源代码但不进行链接操作，生成目标文件。
-o: 指定输出文件名。例如，-o myprogram 表示将输出文件命名为 myprogram。
-g: 生成调试信息，用于调试程序。
-O: 指定优化级别。例如，-O2 表示使用较高的优化级别。
-Wall: 生成所有警告信息，帮助开发者检查代码。
-std=: 指定使用的 C/C++ 标准。例如，-std=c++11 表示使用 C++11 标准。
-I: 指定编译时搜索的头文件目录。
-D: 定义宏。例如，-DDEBUG 表示定义宏 DEBUG。
-U: 取消定义宏。例如，-UDEBUG 表示取消定义宏 DEBUG。
-E: 只进行预处理操作，不进行编译和链接操作。
-Werror: 将所有警告信息视为错误信息，编译器在生成警告时会停止编译操作。

格雷码 ¶

格雷码（Gray Code）是一种二进制编码方式，相邻两个数值之间仅有一个位数不同。

给定一个普通的二进制数 \( B \)，它的格雷码 \( G \) 可以通过如下公式获得： [ B_0 = G_0 \ G_i = B_i \oplus B_{i+1} ]

给定一个格雷码 \( G \)，它的二进制数 \( B \) 可以通过如下公式获得： [ B_0 = G_0 \ B_i = B_{i-1} \oplus G_i ]

其中，\( B_i \) 是二进制数的第 \( i \) 位，\( G_i \) 是格雷码的第 \( i \) 位。

例如，给定一个普通的二进制数 \( B = 1011 \)，我们可以通过以下步骤计算它的格雷码 \( G \)：

\( B = 1011 \)
\( G_0 = B_0 = 1 \)
\( G_1 = B_1 \oplus B_0 = 0 \oplus 1 = 1 \)
\( G_2 = B_2 \oplus B_1 = 1 \oplus 0 = 1 \)
\( G_3 = B_3 \oplus B_2 = 1 \oplus 1 = 0 \)

因此，格雷码 \( G = 1110 \)。

反过来，给定一个格雷码 \( G = 1110 \)，我们可以通过以下步骤计算它的二进制数 \( B \)：

\( G = 1110 \)
\( B_0 = G_0 = 1 \)
\( B_1 = B_0 \oplus G_1 = 1 \oplus 1 = 0 \)
\( B_2 = B_1 \oplus G_2 = 0 \oplus 1 = 1 \)
\( B_3 = B_2 \oplus G_3 = 1 \oplus 0 = 1 \)

因此，二进制数 \( B = 1011 \)。

图论是离散数学的一个重要分支，研究由顶点和边组成的结构，称为图。图用于表示对象之间的关系，广泛应用于计算机科学、网络、数据分析、交通网络等领域。

图的基本概念 ¶

顶点（Vertex）： - 图中的基本元素，通常用点表示。顶点可以代表对象，如城市、网页等。
边（Edge）： - 连接两个顶点的线段，表示它们之间的关系。边可以是有向或无向的。
有向图（Directed Graph，或称 Digraph）： - 边有方向的图，通常用箭头表示。箭头指示从一个顶点指向另一个顶点。
无向图 / 双向图（Undirected Graph）： - 边没有方向的图。两端的顶点可以互相连接，无需区分方向。
度数（Degree）： - 对于无向图，一个顶点的度数是连接到该顶点的边的数量。 - 对于有向图，分为入度和出度：
- 入度：指向该顶点的边数。
- 出度：从该顶点出发的边数。
路径（Path）： - 顶点和边组成的序列，其中的每一条边都连接相邻的顶点。
回路（Cycle）： - 起点与终点相同的路径，且在路径中不重复经过其他顶点。
连通图（Connected Graph）： - 在无向图中，如果任意两个顶点之间都有路径相连，那么这个图就是连通的。
连通分量（Connected Component）： - 一个图中的最大连通子图。如果一个图不连通，可以被划分成若干连通分量。
树（Tree）：
- 是一种特殊的图，连通且无回路。树有很多应用，比如二叉树、搜索树等。
二分图（Bipartite Graph）：
- 顶点集可以分为两个互不相交的子集，并且图中所有边都连接不同子集中的顶点。例如，任务分配问题可以用二分图表示。
平面图（Planar Graph）：
- 图可以在平面上画出，且边不相交。
完全图（Complete Graph）：
- 任意两个不同的顶点之间都有一条边相连。一个有 n 个顶点的完全图包含 \( n \times (n-1) / 2 \) 条边。
图的矩阵表示：
- 邻接矩阵：用一个 \(n \times n\) 的矩阵表示图，矩阵中的元素表示两个顶点之间是否有边相连。
- 邻接表：图的另一种表示方式，使用链表记录每个顶点的相邻顶点。

图的分类 ¶

稀疏图（Sparse Graph）：边的数量远小于顶点的平方。
稠密图（Dense Graph）：边的数量接近顶点数的平方。