第一部分--进制
理论上讲，进制的数量是无限的。
> 但初赛中常考的是下表内容
进制 表示 开头 举例 二进制 B 0b int a = 0b10 八进制 O 0 int a = 071 十进制 D --- int a = 44 十六进制 H 0x int a = 0x7F
注意：十六进制中超过10（包含10）的数使用A~F表示
> N进制转十进制
位权法--每一位上的数值乘对应的权值
例如：
(100.011)b(100.011)_b(100.011)b 转化成十进制
整数部分
(100)b=0×20+0×21+1×22=4(100)_b = 0 \times 2^0 + 0 \times 2^1 + 1 \times 2^2 = 4(100)b =0×20+0×21+1×22=4
小数部分
(0.011)b=0×2−1+1×2−2+1×2−3=0.375(0.011)_b = 0 \times 2^{-1} + 1 \times 2^{-2} + 1\times 2^{-3} = 0.375(0.011)b =0×2−1+1×2−2+1×2−3=0.375
转换结果
4+0.375=4.3754 + 0.375 = 4.3754+0.375=4.375
所以
(100.011)b=(4.375)d(100.011)_b=(4.375)_d(100.011)b =(4.375)d
由此我们知道：
数值就是当前这一位的数
权值就是n的不同次方（n是n进制中的n）
> > 代码实现（模板）
> 十进制转N进制
* 整数部分
短除法--除2取余，逆序排列（遇到商为0结束）
例：(42)d⟶(101010)b(42)_d\longrightarrow (101010)_b(42)d ⟶(101010)b
* 小数部分
短除法--乘2取整，逆序排列
例：(0.625)d⟶(0.101)b(0.625)_d\longrightarrow (0.101)_b(0.625)d ⟶(0.101)b
* 我们发现整数和小数的十进制数的方法刚好是反过来的
> > 代码模版：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第二部分--原反补码
数值在计算机中，均以补码的方式存储。
> 6个概念
>
> > 机器数：一个数在计算机中的二进制表示。它是带符号的，最高位为 0 表示正数，1 表示负数
>
> > 机器码：原码反码补码
>
> > 真值：机器数对应的真正数值
>
> > 原反补码
> >
> > > 原码：符号位+数值位
> >
> > > 反码：正数反码=原码；负数反码=原码除符号位以外其余位取反
> >
> > > 补码：正数补码=反码=原码；负数补码=反码+1,（需要进位）
我们要先知道：求出数字的补码是为了进行加减法
所以这里以-10+5来举例
前面说过，数值在计算机中都以补码的方式存储
所以我们要先把-10和5写成补码：
-10
* 原码（这里写成八位二进制）：1 000 1010
* 反码（这里写成八位二进制）：1 111 0101
* 补码（这里写成八位二进制）：1 111 0110 ⟶\longrightarrow⟶其实我们不用担心进位会进到符号位那里，因为不存在这种情况
5
* 原码（这里写成八位二进制）：0 000 0101
* 反码（这里写成八位二进制）：0 000 0101
* 补码（这里写成八位二进制）：0 000 0101
1111 0110
0000 0101
————————
1111 1011
1111 1011是结果的补码！
1111 1011转原码：
* 反码：1111 1010
* 原码：1000 0101
* 真值： -5
而-10+5就是等于-5
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第三部分--位运算
逻辑 位运算是需要符号位参与的，无需转为补码
> 有6种常用的位运算
>
> > 需要 ≥\ge≥ 2个数的
> >
> > > 按位与：二进制下同一位都为1，才为1
> >
> > > 按位或：二进制下同一位都为0，才为0
> >
> > > 按位异或：二进制下同一位相同为0，不同为1
>
> > 不需要2个数的
> >
> > > 按位取反：二进制下同一位1变0,0变1
> >
> > > 左移：向左移，高位舍去，低位补0（相当于×2左移多少位\times 2^{左移多少位}×2左移多少位）
> > > 右移：向右移，低位舍去，高位补0（相当于÷2右移多少位⟶整除\div 2^{右移多少位} \longrightarrow 整除÷2右移多少位⟶整除）
不同位运算的符号：
位运算名称 符号 按位与 & 按位或 | 按位异或 ^ 按位取反 ~ 左移 << 右移 >>
> 以-13和3为例 ⟶\longrightarrow⟶ 负数位运算要转为补码，正数就是原码
> -13的二进制（补码）：11110011
> 3的二进制（原码）：00000011
> 如果位运算有负数，最后的结果还要从补码转回原码
* 按位与
> > (-13) & 3 = 3
* 按位或
> > (-13) | 3 = -13
* 按位异或
> > (-13) ^ 3 = -16
* 按位取反
> > ~(-13) = 12
* 左移&右移
> > (-13) << 2 = -52
> > (-13) >> 2 = -4
TIPS:
1. 可以通过 (x & 1) 是否为 0 来判断 x 是否为偶数
2. 正常情况下，浮点数不参与位运算
3. 位运算的速度是运算符中最快的
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第四部分--排列组合
这一部分是我最头疼的，所以有些地方写的可能需要改进，请大家多多指教
> 先来了解“阶乘”这个概念
>
> > n 的阶乘（也可以写为n!）=n×(n−1)×(n−2)×...×2×1=n \times(n-1)\times(n-2)\times...\times 2\times1=n×(n−1)×(n−2)×...×2×1
> > 例如：5!=5×4×3×2×1=1205!=5\times4\times3\times2\times1=1205!=5×4×3×2×1=120
> 提问&回答部分
>
> > 什么是排列？
>
> > 从 n 个不同元素中，任取 m 个元素，按照顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。也就是说排列不但要选，还要排
>
> > 什么是组合？
>
> > 从 n 个不同元素中，任取 m 个元素，组成一组，，叫做从 n 个不同元素中取出 m 个元素的一个组合。不同的顺序但同样的元素也算同一种排列。也就是说组合只用选
>
> > 排列用什么公式表示，怎么计算？
>
> > 从 n 个不同元素中取出 m 个元素的排列数用AnmA_n^mAnm 表示
> > AnmA_n^mAnm 的计算公式：n!÷(n−m)!n! \div (n-m)!n!÷(n−m)!
>
> > 组合用什么公式表示，怎么计算？
>
> > 从 n 个不同元素中取出 m 个元素的组合数用CnmC_n^mCnm 表示
> > CnmC_n^mCnm 的计算公式：Anm÷m!A_n^m\div m!Anm ÷m!
> > ***=Cnn−mC_n^m = C_n^{n-m}*** =Cnn−m
一些小技巧 ★★★★★
1. 特殊优先法
例题：
* 五个人排成一排，甲必须站在第一个，乙必须站在最后一个，问有多少种排列方式
思路：
* 首先确定了甲和乙的位置，所以他们只有一种排列方式
* 然后就计算一下剩余三个人的全排列有多少种方案（3×2×1=63 \times 2 \times 1=63×2×1=6种）
* 最后得出总方案数就是6种
特点
* 有固定位置要求的排列方式计算
2. 捆绑法
例题：
* 五个人排成一排，甲和乙必须挨在一起，问有多少种排列方式
思路：
* 首先假设现在甲和乙是一个整体
* 然后就计算一下四个人的全排列有多少种方案（4×3×2×1=244 \times 3 \times 2 \times 1=244×3×2×1=24种）
* 接着由于甲和乙还可以调换顺序（2种方案），所以24还要乘上2
* 最后得出方案数为48种
特点：
* 必须相邻类问题排列方式计算
3.插空法
例题：
* 2男3女排成一排，女生不能相邻，问有多少种排列方式
思路：
* 首先确定了计算2男的全排列（2种）
* 然后把3个女生放到2男中间的空隙里（含两端），大概意思就是：女男女男女男
* 接着再计算一下这3个女生的全排列有多少种方案（3×2×1=63 \times 2 \times 1=63×2×1=6种）
* 最后把男生女生的全排列乘一下，就是2×6=122 \times 6 = 122×6=12种
特点：
* 必须不相邻类问题排列方式计算
4. 隔板法
例题：
* 6个相同的优秀毕业生名额分3个班级，每班至少一个，有几种分法？
思路：
* 假如我们把6个名额看成6张纸，发现它们中间有5个空
* 5个空中需要插进2块板（这样是3个班）——（C52=10C_5^2=10C52 =10种）
* 最后得出总方案数就是10种
特点：
* 分配东西且必须有1个及以上且是相同物品（如：三好学生名额）
5. 倍缩法
例题：
* 1 2 3排序，但1必须在2的前面，有多少种方法
思路：
* 全排列除以多余的排列（去重）
* A33÷A22=3A_3^3 \div A_2^2=3A33 ÷A22 =3种
* 最后得出总方案数就是3种
特点：
* 定序排列问题
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第5.1部分：树
这一部分的概念会很多
> 树
> 树中结点的度
这个结点由多少个子树
（如图，A结点的度就是3）
> 树的度
所有结点中度的最大值
（如图，这棵树的度就是3）
> 根结点、叶子结点、分支结点
如图：
根节点是A（没有前驱结点）
叶子结点是KLFGMIJ（没有后继结点）
分支结点是ABCDEH（有后继结点）
> 树中结点的前驱、后继
前驱就是结点被谁连接（就是它上面那层且连接着它的那个结点），根节点没有前驱，直接前驱就是父亲
后继就是结点连接着谁（就是它下面那层且它连接着的那个结点），叶子结点没有后继，直接后继就是儿子
如图：C结点的后继（儿子）是G，G结点的前驱（父亲）是C
> 树的深度（层次/高度）
从根节点出发，每次访问孩子结点，到达叶子结点经过的最多结点数。
注意：部分题目中明确写出根结点为第0层
> 一些特殊的概念
* n个结点的树，有且仅有n-1条边
* 树中任意两个结点之间有且仅有一条简单路径
* 除根结点没有父结点外，其余结点有且仅有一个父结点。
第5.2部分：二叉树（常考）
二叉树(Binary Tree，简称BT)是一种度数最大为 2 的树
二叉树的每个结点最多有两个子结点，每个结点的子结点分别称为左孩子、右孩子，它的两棵子树被称为左子树、右子树。
> 二叉树的五个性质
* 在二叉树的第i层上最多有2i−12^{i-1}2i−1个结点
* 深度为n的二叉树最多有2k−12^k-12k−1个结点
* 对于任意一棵二叉树，如果其度数为0的结点数量为n0，度数为2的结点数量为n2，那么一定满足n0=n2+1
* 具有n个结点的完全二叉树，其深度为：⌊log2n⌋+1\lfloor log_2 n \rfloor + 1⌊log2 n⌋+1
* 将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1，2，…，n，则有以下关系：
① 若i=1，则结点i为根，无父结点；
② 若i>1，则i的父结点编号为[i/2]；
③ 若2i>n，则i无左孩子，否则其左孩子编号为2i；
④ 若2i+1>n，则i无右孩子，否则其右孩子编号为2i+1。
> 满二叉树（完美二叉树）（第二个性质）
> 完全二叉树
> 对于深度为n的二叉树，前n-1层是满二叉树，最后一层的结点是从左到右连续的
满二叉树就是完全二叉树的一种
> 二叉树的前中后序遍历
非常简单
前序遍历：左右根
中序遍历：左根右
后序遍历：根左右
代码：
> 二叉树的重构
中序遍历加上另外任意一种遍历方式，可以唯一确定一颗二叉树。先序遍历与后序遍历不一定能唯一确定一个二叉树。
二叉树的重建步骤：
1. 通过先序/后序，找到根结点。
2. 通过根结点在中序中找到左子树和右子树。
3. 对左右子树递归进行 1、2两步。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第六部分--图
这一部分的概念更多
> 图
由结点和边组成
结点就是元素的具体值
边就是结点之间的关系
> 有向图、无向图
有向图的边有个箭头（一般是）
无向图的边就是个线
> 带权图、权重
带权图是指图的边上有数字
权重可以理解为带权图这条边上所代表的内容（也可以理解为，通过这条边的花费）
> 自环、重边
自环：
指一条边的起点和终点都是同一个结点
重边：
在无向图中指两个结点之间有多条边
在有向图中指两个结点之间有多条起点和终点同样的边
> 简单图、多重图
简单图指图没有自环或重边
多重图指图拥有自环或重边
> 度数（对于某个节点）
无向图
一般就是有多少条线连接着这个结点
有向图：
入度：指有多少个箭头指向这个结点
出度：指这个点指向了多少个结点（包括自环）
> 路径
指从一个点到达另一个点、经过连续的边构成的序列
如果两个结点中存在路径，则代表这两个结点是连通的
简单路径：
路径中所有元素没有重复
> 环路
指从一个点到达自己这个点、经过连续的边构成的序列
简单环路：
环路中所有元素没有重复（这个点除外）
> 邻接矩阵
一种二维数组，其中每个元素表示两个结点之间的边——带权图每一项是具体数值，其他每一项1是存在，0是不存在
注意：二维数组mp的第mp[i][j]项指从i到j有一条边
> 邻接表
一般是vector数组，数组类型是自定义结构node，node包括两个数字，一个表示结点的邻居，一个表示这条边的权值
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第七部分--前中后缀表达式
> 前缀表达式顺序为：运算符，操作数1，操作数2
> 中缀表达式顺序为：操作数1，运算符，操作数2（平常写算式时用的）
> 后缀表达式顺序为：操作数1，操作数2，运算符
> 中缀转后缀
1. 根据运算时的优先级给中缀表达式加括号
2. 将所有符号移到与之对应的括号外面
3. 去掉括号
举个例子
> 中缀转前缀
1. 根据运算时的优先级给中缀表达式加括号
2. 将所有符号移到与之对应的括号前面
3. 去掉括号
举个例子
> 后缀转中缀
1. 从左往右扫描
2. 遇到一个运算符，取左边最近的两个操作数进行运算（注意顺序）
3. 加括号合并为一个操作数。
4. 最后去掉不影响计算顺序的括号。
举个例子
> 前缀转中缀
1. 从右往左扫描
2. 遇到一个运算符，取右边最近的两个操作数进行运算（注意顺序）
3. 加括号合并为一个操作数。
4. 最后去掉不影响计算顺序的括号。
举个例子
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
有建议，直接提
有些根据集训营笔记写的--同学们和老师们和AC君们一定要原谅我啊啊啊
有玩蛋仔的吗
点赞并顶一下好吗？谢谢！\huge 点赞并顶一下好吗？谢谢！点赞并顶一下好吗？谢谢！
希望能上热门讨论和精华帖\red {希望能上热门讨论和精华帖}希望能上热门讨论和精华帖
之前讨论的总结
