一、计算机常识

1. Linus系统指令

• help：查看命令的用法。
• man：命令说明书。
• su：切换用户。
• cd：切换目录。
• ls：查看目录。
• mkdir：新建目录。
• rm：删除目录（文件）。
• mv：修改目录。
• cp：拷贝目录。
• find：搜索目录。
• pwd：查看当前目录。
• touch：新增文件。
• rm：删除文件（目录）。
• vi、vim：编辑文件。

2. 常见的......有

• 常见的声音文件格式有：MP3、WAV、AAC、WMA、OGG。
• 常见的视频文件格式有：MP4、MOV、AVI、WMV、MKV、WEBM。
• 常见的文本文件格式有：ASCII、MIME、TXT、DOC/DOCX、PDF、RTF、ODT。
• 常见的图像文件格式有：JPEG、PNG、GIF、BMP、PSD、TIFF、RAW。
• 常见的编译型语言有：C、C++、Delphi、Fortran、Java、D语言（C++ 的加强版）、Ada。
• 常见的g++指令：g++ main.cpp -o program（编译单个源文件并生成可执行文件，这里文件名为 main.cpp）、g++ main1.cpp main2.cpp -o program（编译多个源文件并生成可执行文件，这里文件名为main1.cpp和main2.cpp）、g++ -std=c++11 main.cpp -o program（指定 C++ 标准版本，这里为 C++11）、g++ -g main.cpp -o program（生成调试信息）。
• 事实上，-o 后面只要接可执行文件就可以了

3. 原码、反码、补码

• 对计算机来说，不存在原码和反码，只存在补码。计算机的运算只有加法没有减法，自然也只能用补码进行计算。
• 原码：我们将数转换成对应进制（大部分时候是二进制和十六进制）即可得到原码。
• 反码：正数的反码与原码相同，负数的反码是原码除最高位（符号位）取反。
• 补码：一个正数的补码和原码相同，$\text{一个负数的补码}=\text{最大值}-\text{该数的绝对值}+1$。
• -100在十六进制下的补码是 $FFFF-0x64+1=FF9C$ ，在二进制下的补码是 $11111111-01100100+1=10011100$ 。
• 注意题目要求，若最终要求原码记得将补码转换成原码。

- 对于二进制

• 使用最高位（最左边的一位）表示符号：$0$ 表示正数，$1$ 表示负数。其他位表示大小。
• 补码等于反码+1。
• 对于1byte的数据类型（如char）补码 $0000~0000$ 到 $0111~1111$ 表示 $0$ 到 $127$，$1111~1111$ 到 $1000~0001$ 表示 $-1$ 到 $-127$。
• 特别的，$1000~0000$ 表示 $-128$。

二、数学

1. 给 $n$ 个数排序最坏情况最少需要多少次比较

• $n$ 个数共有 $n!$ 种排列情况，每次比较有 $2$ 种可能，那么最小的比较次数（理论下限）$m$ 为 $\log_2{n!}$ 向上取整。
• $3$ 个数至多进行 $3$ 次比较，$4$ 个数至多进行 $5$ 次比较，$5$ 个数至多进行 $7$ 次比较。
• 容易证明，没有一种排序能稳定达到理论下限。

2.在 $2n$ 个数中求出最大值和最小值最坏情况最少需要多少次比较

• 若直接分别求最大值和最小值，次数为 $4n-2$。这种方法没有重复利用比较，显然不是最优的比较法。
• 分别将 $a_1~a_2$、$a_3~a_4$、$a_5~a_6$ $\cdots$ $a_{2n-1}~a_{2n}$ 进行 $n$ 次比较。
• 将较小的 $n$ 个数进行 $n-1$ 比较得到最小值。
• 将较大的 $n$ 个数进行 $n-1$ 比较得到最大值。
• 综上，最少需要 $n+(n-1)+(n-1)$ 共 $3n-2$ 次比较。

3.正多面体

• 显然只有正四面体、正六面体、正八面体、正十二面体和正二十面体。

正四面体

• 由正三角形组成。
• 共 $4$ 个顶点 $6$ 条边。
• $3$ 个面共用 $1$ 个顶点。

正六面体

• 由正四边形（正方形）组成。
• 共 $8$ 个顶点 $12$ 条边。
• $3$ 个面共用 $1$ 个顶点。

正八面体

• 由正三角形组成
• 共 $6$ 个顶点 $12$ 条边。
• $4$ 个面共用 $1$ 个顶点。

正十二面体

• 由正五边形组成。
• 共 $20$ 个顶点 $30$ 条边。
• $3$ 个面共用 $1$ 个顶点。

正二十面体

• 由正三角形组成。
• 共 $12$ 个顶点 $30$ 条边。
• $5$ 个面共用 $1$ 个顶点。

4.排列组合

排列数

• 从 $n$ 个不同元素中，任取 $m$（$m\leq n$，$m$ 与 $n$ 均为自然数，下同）个元素按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列；从 $n$ 个不同元素中取出 $m$($m\leq n$) 个元素的所有排列的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数，用符号 $\mathrm A_n^m$（或者是 $\mathrm P_n^m$）表示。
• 排列的计算公式是：$\mathrm A_n^m=n(n-1)(n-2) \cdots(n-m+1)=\frac{n!}{(n-m)!}$。
• 全排列：$m=n$。第一个位置可以选 $n$ 个，第二位置可以选 $n-1$ 个，以此类推得：$\mathrm A_n^n=n(n-1)(n-2)\cdots3\times2\times1=n!$。
• 全排列是排列数的一个特殊情况。
• 当排好 $n-1$ 个数时，最后一个位置也就确定了。所以$\mathrm A_n^n=\mathrm A_{n-1}^n$，$0!=1!=1$。

组合数

• 从 $n$ 个不同元素中，任取 $m$（$m\leq n$，$m$ 与 $n$ 均为自然数，下同）个元素叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；从 $n$ 个不同元素中取出 $m$($m\leq n$) 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数，用符号 $\mathrm C_n^m$ 表示。
• $\mathrm C_n^m=\dbinom{n}{m}=\frac{\mathrm A_n^m}{m!}=\frac{n!}{m!(n - m)!}$

5.概率

• 事实上，我们可以用排列组合解决初赛的概率问题。
• 题目一：从 $0$、$1$、$2$、$3$、$4$、$5$ 这 6 个数字中随机选取 $3$ 个不同的数字组成一个三位数（首位不能为 $0$），求该三位数 “既能被 $2$ 整除，又能被 $3$ 整除” 的概率。
• 一共有 $\mathrm A_6^3=120$ 个三位数，而以 $0$ 开头不合法的三位数有 $\mathrm A_5^2=20$ 个，故合法的三位数有 $120-20=100$ 个。
• 按顺序枚举以 $0$、$2$、$4$ 为结尾的三位数、不难得出一共有 $20$ 个三位数满足能被 $3$ 整除。
• 答案为 $\frac{20}{100}=\frac{1}{5}$