初赛复习内容

本文主要是介绍初赛复习内容，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

内容

信息学比赛

全国青少年信息学奥林匹克竞赛（NOI）在 1984 年开始。
国际信息学奥林匹克竞赛（IOI）在 1989 年开始。
全国青少年信息学奥林匹克联赛（NOIP）在 1995 年开始。
APIO 在 2007 年开始。

计算机知识

寄存器是中央处理器的重要组成部分
程序运行时的空间复杂度是指程序运行时理论上所占的内存空间，
阶码指明了小数点在数据中的位置。
Pascal语言，C语言和C++语言都属于高级语言，编译性语言
编译器的主要功能是将源程序翻译成指令
存储器有主存和辅存，主存中有ROM和RAM，RAM在关机或停电情况下内容全部丢失，ROM不会。

原码，补码，反码

原码：最高位即为符号位（ $0$ 正 $1$ 负），其余位为原来的二进制。
反码：正数不变，负数其符号位不变，其余位取反
补码：正数不变，负数在其反码的基础上加一。

图像内存，运行内存，各种内存

$1TB=2^{10}\rm{GB}=2^{20}\rm{MB}=2^30 \rm{KB}=2^{40} \rm{Byte}$ ， $1\rm{Byte}=8\rm{Bit}$ ，其中 $\rm{Byte}$ 为字节， $\rm{Bit}$ 为位。

设图片分辨率为 $x\times y$ ， $z$ 位色，则内存为

$x\cdot y\cdot z \rm{Bit}$

设某计算机的 $C P U$ 和内存之间的地址总线宽度是 $x$ 位（ $\rm{Bit}$ ），最多使用的内存为 $2^x\rm{Byre}$

前缀，中缀，后缀表达式

假如给式子 $a+(b\times c)-(d+e)$ 转化

第一步：按照运算符的优先级对所有的运算单位加括号，式子变成了： $((a + (b * c)) - (d + e))$
第二步：转换前缀与后缀表达式

前缀：把运算符号移动到对应的括号前面，则变成： $\times (bc)) + (de))$ ，把括号去掉：于是有前缀式子： $-+a\times bc+de$ 。
后缀：把运算符号移动到对应的括号后面，则变成： $((a(bc)\times )- (de)+ )-$ ，把括号去掉：于是有后缀式子 $abc\times -de+-$ 。

常见排序

排序方式	平均情况	最坏情况	稳定性
插入排序	$O(n^2)$	$O(n^2)$	稳定
希尔排序	$O(n^{1.3})$		不稳定
冒泡排序	$O(n^2)$	$O(n^2)$	稳定
快速排序	$O(n\log n)$	$O(n^2)$	不稳定
选择排序	$O(n^2)$	$O(n^2)$	不稳定
堆排序	$O(n\log n)$	$O(n\log n)$	不稳定
归并排序	$O(n\log n)$	$O(n\log n)$	稳定

vara:array[1..4] of integer;i, j, temp, n:integer;
beginread(n);for i := 1 to n do read(a[i]);for i := 1 to n dofor j := 1 to n-i doif a[j] > a[j + 1] thenbegintemp := a[j];a[j] := a[j + 1];a[j+1] := temp;end;for i:= 1 to n do write(a[i]);
end.

一个排序，若存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则这个排序稳定，反之则不稳定。

视频，图片格式

常见的视频格式有： $r m$ ， $r m v b$ ， $w m v$ ， $a v i$ ， $m p 4$ ， $3 g p$ ， $m k v$ 。

常见的图片格式有： $j p g$ ， $j p e g$ ， $g i f$ ， $p n g$ ， $b m p$

排列组合

排列公式

$A_{n}^m=n(n-1)(n-2)\dots(n-m+1)=\frac{n!}{(n-m)!}$

组合公式

$C_{n}^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!}$

根据这个定义发现的公式

$\sum_{i=0}^nC_n^i=2^n$

$C_n^r+C_n^{r+1}=C_{n+1}^{r+1}$

有重复元素的排列组合：假设有 $m$ 个数， $n$ 个不同的数，分别为 $a_1,a_2,a_3,\dots,a_n$ ，每个数出现次数为 $b_1,b_2,b_3,\dots,b_n$ ，那么本质不同的全排列方案数有

$\frac{m!}{\prod \limits_{i=1}^n b_i}$

错排公式，定义 $D (1) = 0, D (2) = 1$ ，则

$D(n)=(n-1)\left[ D(n-1)+D(n-2)\right]$

卡特兰

$C_n=(2n)!/(n+1)!/n!$

操作系统

常见电脑操作系统有： $W i n d o w s$ ， $U N I X$ ， $X E N I X$ ， $Mac\ \ OS$

进制转化

$R$ 进制转十进制，将 $3506.2)_8$ 转化为十进制。

$(3506.2)_8\\ \begin{aligned} =& 6\times 8^3+5\times 8^2++0\times 8^1+6\times 8^0+2\times 8^{-1}\\ =&1862.25 \end{aligned}$

十进制转 $R$ 进制：将 $5.3125)_{10}$ 转化为二进制数，整数部分为 $101)_2$ ，剩下 $0.3125)_{10}$
$\begin{aligned} (0.3125)_{10}\\ 0.3125\times 2=& 0.625\\ 0.625\times 2=&1.25\\ 0.25\times 2=&0.5\\ 0.5\times 2=&1,0 \end{aligned}$