CSP初赛攻略
不难发现，CSP初赛并无难度
一、计算机常识
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 个数排序最坏情况最少需要多少次比较 -
-
- 容易证明，没有一种排序能稳定达到理论下限。
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 条边。 -
### 正六面体 - 由正四边形（正方形）组成。
- 共
8 个顶点12 条边。 -
### 正八面体 - 由正三角形组成
- 共
6 个顶点12 条边。 -
### 正十二面体 - 由正五边形组成。
- 共
20 个顶点30 条边。 -
### 正二十面体 - 由正三角形组成。
- 共
12 个顶点30 条边。 -
## 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}