进制转换

十进制整数转其余进制

数位拆分，余数倒着排列。

• 例如 $10$ 进制的 $13$ 转 $2$ 进制过程如下

1. 13 / 2 = 6 …… 1
2. 6 / 2 = 3 …… 0
3. 3 / 2 = 1 …… 1
4. 1 / 2 = 0 …… 1

所以 $10$ 进制的 $13$ 转 $2$ 进制后为 $(1101)_2$

• 转八进制和十六进制等其余进制将除数改为对应的数字即可。

其余进制整数转十进制

按位展开

• 例如 $10$ 进制的 $1234=1\times 10^3+2\times 10^2+3\times 10^1+4\times 10^0$

那么 $2$ 进制的 $(1101)_2=1\times 2^3+1\times 2^2+0\times 2^1+1\times 2^0=(13)_{10}$

• 其余进制转十进制以此类推。

小数之间的转换

• 十进制小数转二进制

整数和小数分开处理

1. 整数转二进制就是数位拆分
2. 小数采取乘 $2$ 取整法，将得到的整数部分 正序排列

例如 $10.25$ 转二进制。

整数部分 $10$ 的二进制是 $(1010)_2$

小数部分的 $0.25$ 采取如下步骤

• $0.25\times 2=0.5$，整数部分为 $0$
• $0.5\times 2=1.0$，整数部分为 $1$，小数部分为 $0$，转化结束。

因此 $0.25$ 转二进制就是 $(0.01)_2$。

综合整数和小数部分一起，可以得到 $10.25$ 的二进制为 $(1010.01)_2$

• 二进制小数转十进制

1. 在二进制整数中，最后一位代表 $2^0$，那么越过小数以后开始是 $2$ 的几次方？

答：：$2^{-1}$ 次方。

因此 $(1010.01)_2$ 转十进制就是

$$\begin{aligned} (1010.01)_2&=1\times 2^3+0\times 2^2+1\times 2^1+0\times 2^0+0\times 2^{-1}+1\times 2^{-2}\\ &=8+0+2+0+0+0.25\\ &=10.25 \end{aligned} $$

其余进制以此类推。

位运算

原码，反码，补码。

原码，反码，补码是有符号数的表示方法。

计算机都是以二进制补码形式存储数，分为有符号数和无符号数；有符号位就是二进制最高位表示数字的正负。$0$ 代表正，$1$ 代表负。

int 类型的变量由于是 $4$ 字节，因此一共有 $32$ 个二进制位，而最高位是符号位，因此 int 类型范围可以表示的最大正整数为

$$\textcolor{red}01111111\ 11111111\ 11111111\ 11111111=2^{30}+2^{29}+\cdots+2^0=2^{31}-1 $$

原码

原码将一个整数表示成符号位和它的二进制串。符号位上，$0$ 表示正数，$1$ 表示负数。

即用第一位表示符号, 其余位表示值。比如如果是 $32$ 位二进制：

• $1$ 的原码为 $\textcolor{red}00000000\ 0000000\ 00000000 \ 00000001$
• $-1$ 的原码为 $\textcolor{red}10000000\ 0000000\ 00000000 \ 00000001$

因此一个整数的原码就是它的二进制表示方法，同时结合最高位的符号位。

反码

正数的反码还是原码，不做任何改变。

负数的反码是除了符号位不变以外，其余位由 $0$ 变 $1$，$1$ 变 $0$。

• $1$ 的反码为 $\textcolor{red}00000000\ 0000000\ 00000000 \ 00000001$
• $-1$ 的反码为 $\textcolor{red}11111111\ 11111111\ 11111111 \ 11111110$

补码

正数的补码还是原码，不做任何改变。

负数的补码是在其反码的基础上加 $1$ 得来的。

• $1$ 的补码为 $\textcolor{red}00000000\ 0000000\ 00000000 \ 00000001$
• $-1$ 的补码为 $\textcolor{red}11111111\ 11111111\ 11111111 \ 11111111$

位运算简介

由于位运算是操作补码的运算，因此请务必熟练掌握原，反，补码的运算，这也是信奥赛初赛中热衷的考察点之一。

大规则：都转成二进制补码，算完了也是补码，真实值通过原码求得。

非负整数原码，反码，补码都不变。（符号位为 $0$）

负整数求出原码后，设置符号位为 1。反码是在原码的基础上符号为不变，其他位0变1，1变0。补码由反码加 1 得到。

位运算优先级：~ , << >>, &, ^, |

运算符	含义	举例	备注
&	按位与	13&12	都为 $1$，与下来才是 $1$。否则为 $0$
|	按位或	13 | 12	至少有一个 $1$，或下来就是 $1$。否则为 $0$
^	按位异或	13 ^ 12	不同就为 $1$。否则为 $0$
<<	左移	13 << 2	整体向左偏移。左移多少位就是乘以 $2$ 的多少次方
>>	右移	13 >> 2	整体向右偏移。右移多少位就是除以 $2$ 的多少次方并取整。
~	取反	~13	转成补码连同符号位在内全部 $0$ 变 $1$ ，$1$ 变 $0$ 。

其余杂项

• $\lor$ 是数学符号，即逻辑或。$\land$ 是逻辑与。$\lnot$ 是非的意思。

优先级 $\lnot >\land>\lor$，也就是先算非，再算逻辑与，再算逻辑或。

• 字节和空间大小转换。

数据结构

栈

介绍

栈是 OI 中常用的一种线性数据结构，它的特点就是先进后出。如下图所示

初赛的考察点

• 熟悉栈的原理和代码
• 表达式求值的应用
• 了解和栈有关的算法原理和代码

栈的实现

• 数组模拟栈
• STL 里的 stack

数组模拟栈

由于我们需要获取栈顶元素是谁，以及能够知道数组里存放了几个元素，我们可以使用一个名为 top 的变量指向栈顶元素的下标，初始化 top = 0 意为栈内没有元素。

• 加入元素：加入一个元素，我们的做法是让 top 变量向右移动一位，然后对当前位置的元素赋值，通常写成 stk[++top] = x;
• 弹出栈顶：弹出栈顶的实现方式非常简单，执行 top -= 1; 即可。当然我们可以先判断一下 top 是否大于 $0$ 若等于 $0$ 说明栈内无元素则不执行。
• 输出栈顶元素：先判断 top 是否大于 $0$ 若满足则输出 stk[top] 即可。
• 栈的大小：输出 top 的值即可。

STL 里的 stack

格式：stack<元素类型> 变量名，例如 stack<int> stk;

• 加入元素：stk.push(x)
• 判断栈是否为空：cout << stk.empty(); 为空输出 1 否则为 0。
• 弹出栈顶：if (!stk.empty()) stk.pop()
• 输出栈顶元素：if (!stk.empty()) cout << stk.top();
• 栈的大小：cout << stk.size() 即可。

判断入栈序列是否合法

该类问题通常为给定入栈序列，判断出栈序列是否合法。解决办法即用栈模拟每个选项，找到不合法的选项即可。

例如入栈序列为 a b c d e，以下哪个选项为不合法的出栈序列？

• a b c d e
• e d c b a
• b a c d e
• c d a e b

模拟发现第四个选项错误，因为 $b$ 还在 $a$ 头顶呆着，$a$ 不可能先于 $b$ 离开栈。

表达式求值

表达式求值要解决的问题一般是输入一个字符串表示的表达式，要求输出它的值。

例如输入一个字符串 1 + 2 * 3 人眼是很容易能够看出答案的，那么计算机是如何计算的呢？

前后缀表达式

逆波兰表达式（后缀表达式）是书写数学表达式的一种形式，其中运算符位于其操作数之后。例如，以下表达式：

$$a+b*c*d+(e-f)*(g*h+i)$$

可以用逆波兰表达式书写：

$$abc*d*+ef-gh*i+*+$$

后缀表达式的计算方法

• 从左往右扫描字符串，遇到数字字符就入栈。
• 遇到运算符，取出栈顶两个元素，将第一个取出的元素记为 $a$，第二个取出的元素记为 $b$，如若当前运算符为 $op$，则计算 $b\ op\ a$ 的结果，然后将该结果重新入栈。
• 操作完以后栈内最后剩的值就是整个表达式的结果。

例如 3 4 + 5 - 的计算过程如下

• $3$ 入栈，$4$ 入栈。
• 遇到 +，取出 $3,4$，计算 $3+4$ 然后将 $7$ 入栈
• 遇到 $5$ 入栈
• 遇到 -，计算 7 - 5 的结果入栈

最后栈里只剩一个 $2$ 即为该后缀表达式的结果。

注意事项

• 务必是后取出的 $b$ 在运算符左，先取出的 $a$ 在运算符右，原因是例如 $3- 2$ 的后缀表达式是 $3\ 2\ -$。我们是先把 $3$ 入栈，再把 $2$ 入栈，所以先取的是 $2$ 后取的是 $3$，我们应当计算 $3-2$ 而不是 $2-3$。
• 在表达式合法的前提下，最终栈内必然留下一个数字是最终结果，因此不必考虑其他特殊情况，例如每次从栈里取走两个元素不必担心栈内没有两个元素的情况，若不够 $2$ 个元素说明表达式是错误的。
• 后缀的好处在于没有括号，因为运算符都在数字后面，且更利于计算。

如果题目不需要我们计算真实的结果，而需要我们转中缀表达式，我们就不要把结果真的算出来，直接将整个式子入栈即可，判断何时需要括号即可。

例如 3 4 + 5 - 的计算过程如下

• $3$ 入栈，$4$ 入栈。
• 遇到 +，取出 $3,4$，计算 $3+4$ 然后将 3 + 4 入栈
• 遇到 $5$ 入栈
• 遇到 -，取出栈顶的两个，将 3 + 4 - 5 入栈，这也就是原来的中缀表达式。

前缀表达式

前缀表达式的求解类似于后缀，需要注意以下几点：

• 由于前缀是运算符在前，数字在后，所以需要从右往左倒着遍历字符串。
• 遇到运算符以后取出栈顶元素记为 $a$，再取出一个栈顶元素记为 $b$，设运算符为 $op$，将 $a\ op\ b$ 的结果重新入栈即可。

中缀转后缀

1. 首先根据运算符的优先级，重新加上括号
2. 去括号的时候，从外向内去，每次就把运算符写到自己所在这一层的括号后即可。

例如 a * (b + c) * d 转后缀的步骤如下：

• 加括号可得 ( (a * (b + c)) * d)
• 去掉最外层括号，将 * 移到括号右，可得 (a * (b + c)) d *
• 去掉最外层括号，将 * 移到括号右，可得 a (b + c) * d *
• 去掉最外层括号，将 + 移到括号右，可得 a b c + * d *

括号表达式判定

形如给你一个括号表达式，你要判断括号是否合法？

1. 从左往右扫描括号字符串
2. 遇到左括号入栈
3. 遇到右括号，若栈不为空，说明栈顶的左括号就是和当前右括号匹配成一对，匹配成功就出栈。

否则说明这个右括号没有左括号匹配，括号不合法。

队列

介绍

队列（queue）是一种具有「先进入队列的元素一定先出队列」性质的表。由于该性质，队列通常也被称为先进先出（first in first out）表，简称 FIFO 表。

实现方式

• 数组模拟队列
• STL 的 queue

数组模拟队列

首先根据数据范围定义一个数组，以最基础的数据类型都为 int 为例，例如 int q[N];

使用两个变量标记队列的头部和尾部，通常使用 int h = 1, t = 0; 设置为 $1$ 和 $0$ 表明当 $h>t$ 说明队列里还没有元素。

• 插入元素：q[++t] = x; 加入元素移动队尾这个变量。
• 删除队头元素：h++;
• 访问队首：cout << q[h];
• 访问队尾：cout << q[t];
• 清空队列：h = 1, t = 0;
• 队列元素个数：cout << t - h + 1;

STL 的 queue

使用方法为 queue<元素类型> 队列名字

• 插入元素：q.push(x)。元素加入到队尾。
• 删除队头元素：q.pop(); 注意保证队列不为空在使用。
• 访问队首：cout << q.front(); 注意保证队列不为空在使用。
• 访问队尾：cout << q.back(); 注意保证队列不为空在使用。
• 清空队列：使用 while 循环遍历队列，进行 pop() 操作。例如：while (q.size()) q.pop();
• 队列元素个数：cout << q.size();
• 队列是否为空：cout << q.empty(); 为空返回 true 否则返回 false

初赛的考察点

• 模拟队列的操作做选择题。
• 队列是和广度优先搜索算法搭配使用。

链表

介绍

链表是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素。它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳。

和数组的区别

• 链表因其链状的结构，能方便地删除、插入数据，操作次数是 $O(1)$。但也因为这样，寻找、读取数据的效率不如数组高，在随机访问数据中的操作次数是 $O(n)$。
• 数组可以方便地寻找并读取数据，在随机访问中操作次数是 $O(1)$。但删除、插入的操作次数是 $O(n)$ 次。

单向链表

单向链表中包含数据域和指针域，其中数据域用于存放数据，指针域用来连接当前结点和下一节点。

单向链表的插入

原本是黑色链接，我们要改为 $2$ 条红色链接}$，即$x$的下一个是$y$，$y$的下一个是$z$，按照如下代码即可实现。

y->next = x->next

x->next = y

二者顺序不能调换。

单向链表的删除

如图所示删去 $y$ 就要让 $x$ 直接连向 $z$ ，$z$ 原本属于 $y$ 的下一个，即 $x$ 的下一个的下一个。

x->next = x->next->next（$x$ 的右边直接指向 $z$ 达到删除 $y$ 的效果）

双向链表

双向链表中同样有数据域和指针域。不同之处在于，指针域有左右（或上一个、下一个）之分，用来连接上一个结点、当前结点、下一个结点。

双向链表的删除

如果要删除 $x$ 和 $z$ 之间的 $y$ 我们就要让原本红色的连接变为黑色连接。即让 $x$ 的右边指向 $z$，$z$ 的左边指向 $x$。可以通过以下代码实现：

• y->next->prev = y->prev;
• y->prev->next = y->next;

双向链表的插入

当我们给 $x$ 和 $z$ 之间插入 $y$ 的时候，我们需要建立四条连接，如图 $1,2,3,4$ 所示，可通过如下代码完成：

• y->next = x->next; （第 $3$ 条边）
• y->next->prev = y; （第 $4$ 条边）
• y->prev = x; （第 $2$ 条边）
• x->next = y;

初赛考察点

• 考察链表的基本概念和插入删除复杂度。
• 考察插入和删除的代码理解
• 头插法和尾插法（在链表头部或尾部插入元素）

树和图

• 图的存储和入度出度，有向图无向图，简单图，连通图等概念。
• 图的 DFS, BFS 的过程可以理解。
• 拓扑排序
• 二叉树的基本概念，完全二叉树和满二叉树。
• 二叉树的前中后序遍历，可以根据中序加前序推第三个序列，
• 霍夫曼编码的构造方法和判断。