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}