#创作计划# 初赛基础知识
2025-09-10 18:54:00
发布于：北京
第一部分--进制
理论上讲，进制的数量是无限的。
但初赛中常考的是下表内容
| 进制 | 表示 | 开头 | 举例 |
|---|---|---|---|
| 二进制 | B | 0b | int a = 0b10 |
| 八进制 | O | 0 | int a = 071 |
| 十进制 | D | --- | int a = 44 |
| 十六进制 | H | 0x | int a = 0x7F |
注意：十六进制中超过10（包含10）的数使用A~F表示
n进制转十进制
位权法--每一位上的数值乘对应的权值
例如：
转化成十进制
整数部分
小数部分
转换结果
所以
由此我们知道：
数值就是当前这一位的数
权值就是n的不同次方（n是n进制中的n）
代码实现（模板）
#include <bits/stdc++.h>
using namespace std;
int n;
string x;
// 将一个n进制整数x转为十进制
int main(){
cin >> n >> x;
int len = x.size();
int ret = 0;
int cnt = 0;
for (int i = len - 1;i >= 0;i--){
if (x[i] >= 'A' && x[i] <= 'F'){
ret += (x[i] - 55) * pow(n, cnt);
} else {
ret += (x[i] - '0') * pow(n, cnt);
}
cnt++;
}
cout << ret;
return 0;
}
十进制转n进制
-
整数部分
短除法--除2取余，逆序排列（遇到商为0结束）
例：
-
小数部分
短除法--乘2取整，逆序排列
例：
- 我们发现整数和小数的十进制数的方法刚好是反过来的
代码模版：
#include <bits/stdc++.h>
using namespace std;
int x, m;
// 将一个十进制数x转为m进制（不支持小数部分）
int main(){
cin >> x >> m;
int a;
string ret = "";
while (x != 0){
a = x % m;
if (a >= 10){
ret += char(a + 55);
} else {
ret += char(a + '0');
}
x /= m;
}
// cout << "return:" << ret << endl;
int len = ret.size();
for (int i = len - 1;i >= 0;i--){
cout << ret[i];
}
return 0;
}
第二部分--原反补码
数值在计算机中，均以补码的方式存储。
6个概念
机器数：一个数在计算机中的二进制表示。它是带符号的，最高位为 0 表示正数，1 表示负数
机器码：原码反码补码
真值：机器数对应的真正数值
原反补码
原码：符号位+数值位
反码：正数反码=原码；负数反码=原码除符号位以外其余位取反
补码：正数补码=反码=原码；负数补码=反码+1,（需要进位）
我们要先知道：求出数字的补码是为了进行加减法
所以这里以-10+5来举例
前面说过，数值在计算机中都以补码的方式存储
所以我们要先把-10和5写成补码：
-10
- 原码（这里写成八位二进制）：1 000 1010
- 反码（这里写成八位二进制）：1 111 0101
- 补码（这里写成八位二进制）：1 111 0110 其实我们不用担心进位会进到符号位那里，因为不存在这种情况
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种常用的位运算
需要 2个数的
按位与：二进制下同一位都为1，才为1
按位或：二进制下同一位都为0，才为0
按位异或：二进制下同一位相同为0，不同为1
不需要2个数的
按位取反：二进制下同一位1变0,0变1
左移：向左移，高位舍去，低位补0（相当于）
右移：向右移，低位舍去，高位补0（相当于）
不同位运算的符号：
| 位运算名称 | 符号 |
|---|---|
| 按位与 | & |
| 按位或 | | |
| 按位异或 | ^ |
| 按位取反 | ~ |
| 左移 | << |
| 右移 | >> |
以-13和3为例 负数位运算要转为补码，正数就是原码
-13的二进制（补码）：11110011
3的二进制（原码）：00000011
如果位运算有负数，最后的结果还要从补码转回原码
- 按位与
11110011
& 00000011
-------------
00000011
00000011（补码） = 00000011（原码）
00000011（原码） = 3
(-13) & 3 = 3
- 按位或
11110011
| 00000011
-------------
11110011
11110011（补码） - 1 = 11110010（反码）
11110010（反码）除符号位外取反 = 10001101（原码）
10001101（原码）= -13
(-13) | 3 = -13
- 按位异或
11110011
^ 00000011
-------------
11110000
11110000（补码） - 1 = 11101111（反码）
11101111（反码）除符号位外取反 = 10010000（原码）
10001101（原码）= -16
(-13) ^ 3 = -16
- 按位取反
~11110011
-------------
00001100
00001100（补码） = 00001100（原码）
00001100（原码） = 12
~(-13) = 12
- 左移&右移
(-13) << 2 = -52
(-13) >> 2 = -4
tips:
- 可以通过 (x & 1) 是否为 0 来判断 x 是否为偶数
- 正常情况下，浮点数不参与位运算
- 位运算的速度是运算符中最快的
第四部分--排列组合
这一部分是我最头疼的，所以有些地方写的可能需要改进，请大家多多指教
先来了解“阶乘”这个概念
n 的阶乘（也可以写为n!）
例如：
提问&回答部分
什么是排列？
从 n 个不同元素中，任取 m 个元素，按照顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。也就是说排列不但要选，还要排
什么是组合？
从 n 个不同元素中，任取 m 个元素，组成一组，，叫做从 n 个不同元素中取出 m 个元素的一个组合。不同的顺序但同样的元素也算同一种排列。也就是说组合只用选
排列用什么公式表示，怎么计算？
从 n 个不同元素中取出 m 个元素的排列数用表示
的计算公式：组合用什么公式表示，怎么计算？
从 n 个不同元素中取出 m 个元素的组合数用表示
的计算公式：
一些小技巧 ★★★★★
1. 特殊优先法
例题：
- 五个人排成一排，甲必须站在第一个，乙必须站在最后一个，问有多少种排列方式
思路：
- 首先确定了甲和乙的位置，所以他们只有一种排列方式
- 然后就计算一下剩余三个人的全排列有多少种方案（种）
- 最后得出总方案数就是6种
特点
- 有固定位置要求的排列方式计算
2. 捆绑法
例题：
- 五个人排成一排，甲和乙必须挨在一起，问有多少种排列方式
思路：
- 首先假设现在甲和乙是一个整体
- 然后就计算一下四个人的全排列有多少种方案（种）
- 接着由于甲和乙还可以调换顺序（2种方案），所以24还要乘上2
- 最后得出方案数为48种
特点：
- 必须相邻类问题排列方式计算
3.插空法
例题：
- 2男3女排成一排，女生不能相邻，问有多少种排列方式
思路：
- 首先确定了计算2男的全排列（2种）
- 然后把3个女生放到2男中间的空隙里（含两端），大概意思就是：女男女男女男
- 接着再计算一下这3个女生的全排列有多少种方案（种）
- 最后把男生女生的全排列乘一下，就是种
特点：
- 必须不相邻类问题排列方式计算
4. 隔板法
例题：
- 6个相同的优秀毕业生名额分3个班级，每班至少一个，有几种分法？
思路：
- 假如我们把6个名额看成6张纸，发现它们中间有5个空
- 5个空中需要插进2块板（这样是3个班）——（种）
- 最后得出总方案数就是10种
特点：
- 分配东西且必须有1个及以上且是相同物品（如：三好学生名额）
5. 倍缩法
例题：
- 1 2 3排序，但1必须在2的前面，有多少种方法
思路：
- 全排列除以多余的排列（去重）
- 种
- 最后得出总方案数就是3种
特点：
- 定序排列问题
第5.1部分：树
这一部分的概念会很多
树
树中结点的度
这个结点由多少个子树
（如图，A结点的度就是3）
树的度
所有结点中度的最大值
（如图，这棵树的度就是3）
根结点、叶子结点、分支结点
如图：
根节点是A（没有前驱结点）
叶子结点是KLFGMIJ（没有后继结点）
分支结点是ABCDEH（有后继结点）
树中结点的前驱、后继
前驱就是结点被谁连接（就是它上面那层且连接着它的那个结点），根节点没有前驱，直接前驱就是父亲
后继就是结点连接着谁（就是它下面那层且它连接着的那个结点），叶子结点没有后继，直接后继就是儿子
如图：C结点的后继（儿子）是G，G结点的前驱（父亲）是C
树的深度（层次/高度）
从根节点出发，每次访问孩子结点，到达叶子结点经过的最多结点数。
注意：部分题目中明确写出根结点为第0层
一些特殊的概念
- n个结点的树，有且仅有n-1条边
- 树中任意两个结点之间有且仅有一条简单路径
- 除根结点没有父结点外，其余结点有且仅有一个父结点。
第5.2部分：二叉树（常考）
二叉树(Binary Tree，简称BT)是一种度数最大为 2 的树
二叉树的每个结点最多有两个子结点，每个结点的子结点分别称为左孩子、右孩子，它的两棵子树被称为左子树、右子树。
二叉树的五个性质
- 在二叉树的第i层上最多有个结点
- 深度为n的二叉树最多有个结点
- 对于任意一棵二叉树，如果其度数为0的结点数量为n0，度数为2的结点数量为n2，那么一定满足n0=n2+1
- 具有n个结点的完全二叉树，其深度为：
- 将一棵有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层是满二叉树，最后一层的结点是从左到右连续的
满二叉树就是完全二叉树的一种
二叉树的前中后序遍历
非常简单
前序遍历：左右根
中序遍历：左根右
后序遍历：根左右
代码：
//先序遍历，根左右
void dfs1(int x) {
cout << s[x] << " ";
if (2 * x <= n) dfs1(2 * x);
if (2 * x + 1 <= n) dfs1(2 * x + 1);
}
//中序遍历，左根右
void dfs2(int x) {
if (2 * x <= n) dfs2(2 * x);
cout << s[x] << " ";
if (2 * x + 1 <= n) dfs2(2 * x + 1);
}
//后序遍历，左右根
void dfs3(int x) {
if (2 * x <= n) dfs3(2 * x);
if (2 * x + 1 <= n) dfs3(2 * x + 1);
cout << s[x] << " ";
}
二叉树的重构
中序遍历加上另外任意一种遍历方式，可以唯一确定一颗二叉树。先序遍历与后序遍历不一定能唯一确定一个二叉树。
二叉树的重建步骤：
- 通过先序/后序，找到根结点。
- 通过根结点在中序中找到左子树和右子树。
- 对左右子树递归进行 1、2两步。
第六部分--图
这一部分的概念更多
图
由结点和边组成
结点就是元素的具体值
边就是结点之间的关系
有向图、无向图
有向图的边有个箭头（一般是）
无向图的边就是个线
带权图、权重
带权图是指图的边上有数字
权重可以理解为带权图这条边上所代表的内容（也可以理解为，通过这条边的花费）
自环、重边
自环：
指一条边的起点和终点都是同一个结点
重边：
在无向图中指两个结点之间有多条边
在有向图中指两个结点之间有多条起点和终点同样的边
简单图、多重图
简单图指图没有自环或重边
多重图指图拥有自环或重边
度数（对于某个节点）
无向图
一般就是有多少条线连接着这个结点
有向图：
入度：指有多少个箭头指向这个结点
出度：指这个点指向了多少个结点（包括自环）
路径
指从一个点到达另一个点、经过连续的边构成的序列
如果两个结点中存在路径，则代表这两个结点是连通的
简单路径：
路径中所有元素没有重复
环路
指从一个点到达自己这个点、经过连续的边构成的序列
简单环路：
环路中所有元素没有重复（这个点除外）
邻接矩阵
一种二维数组，其中每个元素表示两个结点之间的边——带权图每一项是具体数值，其他每一项1是存在，0是不存在
注意：二维数组mp的第mp[i][j]项指从i到j有一条边
#include <bits/stdc++.h>
using namespace std;
/*
* 全局变量说明：
* n - 顶点数量
* m - 边数量
* mp - 邻接矩阵（初始值为INF）
*/
int n, m;
int mp[105][105];
int main() {
// 初始化邻接矩阵
memset(mp, 0x3f, sizeof(mp));
/* 示例边设置 */
mp[2][5] = 8; // 顶点2到5的边权为8
// 输出测试
int x = 2; // 查询起点
for (int i = 1; i <= n; i++) {
cout << mp[x][i] << " "; // 输出顶点x到其他顶点的距离
}
return 0;
}
邻接表
一般是vector数组，数组类型是自定义结构node，node包括两个数字，一个表示结点的邻居，一个表示这条边的权值
#include <bits/stdc++.h>
using namespace std;
struct node {
int v, w;
};//v 是终点，w 是边的权重
int n, m;
vector<node> vt[1005];
//定义了 1005 个动态数组
//其中 vt[x] 存储的是 x 为起点的所有的边的信息
int main() {
cin >> n >> m;
while (m--) {
int x, y, w;
cin >> x >> y >> w;
//有一条 x→y 权重是 w 的边
//x 是起点，y 是终点，w 是距离、时间等等
vt[x].push_back({y, w});
//如果是无向图，还要存储一条 y→x 权重是 w 的边
//vt[y].push_back({x,w});
}
//遍历以 x 为起点的所有边的信息
int x;
for (int i = 0; i < vt[x].size(); i++) {
cout << vt[x][i].v << " " << vt[x][i].w << endl;
//起点是 x，终点是 vt[x][i].v，权重是 vt[x][i].w
}
return 0;
}
第七部分--前中后缀表达式
前缀表达式顺序为：运算符，操作数1，操作数2
中缀表达式顺序为：操作数1，运算符，操作数2（平常写算式时用的）
后缀表达式顺序为：操作数1，操作数2，运算符
中缀转后缀
- 根据运算时的优先级给中缀表达式加括号
- 将所有符号移到与之对应的括号外面
- 去掉括号
举个例子
1+(2-3)转后缀表达式
由于(2-3)已经有了括号，所以就不需要加了
(1+(2-3))
(1(2 3)-)+
注意不要把2和3连在一起
1 2 3 - +
注意不要把1和2和3连在一起
中缀转前缀
- 根据运算时的优先级给中缀表达式加括号
- 将所有符号移到与之对应的括号前面
- 去掉括号
举个例子
1+(2-3)转前缀表达式
由于(2-3)已经有了括号，所以就不需要加了
(1+(2-3))
+(1-(2 3))
注意不要把2和3连在一起
+ 1 - 2 3
注意不要把2和3连在一起
后缀转中缀
- 从左往右扫描
- 遇到一个运算符，取左边最近的两个操作数进行运算（注意顺序）
- 加括号合并为一个操作数。
- 最后去掉不影响计算顺序的括号。
举个例子
1 2 3 - +转中缀表达式
假设有个大的列表L
1 2 3 先取进来
接下来是运算符“-”
现在2 3变成了2-3
L也从1 2 3变成了1 (2-3)
接下来是运算符“+”
现在1 (2-3) 变成了 1+(2-3)
发现前缀表达式遍历到头了，所以1+(2-3)就是最终答案
前缀转中缀
- 从右往左扫描
- 遇到一个运算符，取右边最近的两个操作数进行运算（注意顺序）
- 加括号合并为一个操作数。
- 最后去掉不影响计算顺序的括号。
举个例子
+ 1 - 2 3转中缀表达式
假设有个大的列表L
3 2先取进来
接下来是运算符“-”
现在3 2变成了2-3 --> 这里没有写错，就是要3 2变成2 - 3
L也从2 3变成了1 (2-3)
接下来是数字1
L从(2-3)变成了(2-3) 1
接下来是运算符“+”
现在(2-3) 1 变成了 1+(2-3)
发现后缀表达式遍历到头了，所以1+(2-3)就是最终答案
有建议，直接提
有些根据集训营笔记写的--同学们和老师们和AC君们一定要原谅我啊啊啊
有帮助，赞一个