XP03-AD45初赛复习

userId_undefined
蛟龙_湖风
8月全勤卷王时空双修者冒泡宗师→排序元老CSP-J二等奖递归·套娃学徒快乐小狗

2026-08-18 19:52:48

发布于：浙江

53阅读
0回复
0点赞

初赛复习

求赞求赞，B站：只玩鸟的Rhett

1.计算机基础与存储空间

①计算机的组成

处理->存储->输入输出

CPU：[处理]负责读取指令，分析指令，执行运算和控制
内存(RAM)：[存储]程序运行时临时存放的数据，速度快，断电后通常消失
外存(SSD)：[存储]硬盘、U盘等长期保存数据，容量大，速度通常慢于内存，断电后数据不消失
输入输出设备：[输入输出]鼠标键盘是输入，显示器打印机是输出，触摸屏常兼具输入输出

提醒:CSP-J组常考"内存"和"硬盘"混在一起，这是高频错误，内存管运行，硬盘管理长期保存

②CPU的组成：取指，译码，执行，控制

概念 含义 初赛高频考点
运算器 完成算术计算和逻辑运算 加减乘除，与或非...
控制器 协调各组成按指令工作 "指挥"而不是"存储"
寄存器 CPU内部极小、极快的存储单元 速度很快但容量很小
主频 CPU的时间频率，如3.2GHz 高主频通常更快，但不是唯一因素

注意：CPU性能还受核心数，架构，缓存，指令集，内存速度等影响

③内存与外存

特征：速度越快，通常容量越小，价格越高
寄存器(CPU)->缓存Cache->内存RAM->硬盘/U盘->云盘/光盘
速度:快->慢|容量:小->大
缓存Cache：介于CPU和内存之间，用来提高访问速度

④存储单位的换算

单位 英文 关系 常见含义
bit 比特 / 位(老师课件里面的英文是中文) 最小的储存单位 只能表示0或1(bool类型)
Byte 字节/B 1B=8bit 文件大小常用单位
KB KiloByte 1KB=1024B 小文本、图标
MB Megabyte 1MB = 1024KB 图片、音频
GB Gigabyte 1GB = 1024MB 视频、软件、硬盘容量

注意：b和B不一样,b表示bit, B表示Byte。1MB 不是 1Mb；总共可以自己想一个口诀：BKMGT(TB)比如：包括美国??不看芒果台??

⑤计算机的原码、反码、补码

(1)机器数与真值

一个数在计算机中的二进制表示形式叫这个数的机器数。机器数是带符号的，它的最高位作为符号位：0表示位正数；1代表负数。机器数对应的真正数值被称为真值

例:以八位二进制为例子，+3表示为00000011,-3表示为10000011

(2)原码的取值范围

以八位二进制，原码的取值范围是+127127~ −127-127，但是原码的取值范围并非真实数值的取值范围(+127+127~ −128-128)

(3)反码

正数的反码和正数的原码一样，负数的反码是其符号位不变，其余各位取反所获得的码。

(4)补码

正数原反补码相同，负数的补码是反码+1

⑥正数表示与范围

无符号看2n2^n，有符号补码看一半给负数

类型 n位标识范围 32位常见结论
unsigned int 00~2n−12^n-1 0~232−12^{32}-1
int −2n−1-2^{n-1}~2n−1−12^{n-1}-1 −231-2^{31}~231−12^{31}-1

如果int*int已经溢出上限，再存入long long类型无法存储，应该选用long long * long long 或者1LL*int*int

⑦图片、音频、视频存储空间

图片大小=宽∗高∗每像素位数/8图片大小 = 宽 * 高 * 每像素位数 / 8

音频大小=采样率∗量化位数∗声道数∗时间/8音频大小 = 采样率*量化位数*声道数*时间/8

视频可以理解为图片连放

视频大小=宽∗高∗每像素位数/8∗帧率∗时长视频大小 = 宽*高*每像素位数/8*帧率*时长

2.进制转换

①进制

k进制代表逢k进1

16进制因为有十进制的10、11、12、13、14、15代表不了，使用A~F代表

②K进制转10进制

按权展开:将各个数码与它的权值相乘，再相加。对于一个K进制数：从小数点往左看，第i位的权值为Ki−1K^{i-1}，往右看则为K−iK^{-i}
例:逢K近1

abcd.efg‾=aK3+bK2+cK1+dK0+eK−1+fK−2+gK−3\overline{abcd.efg} = aK^3+bK^2+cK^1+dK^0+eK^{-1}+fK^{-2}+gK^{-3}

③10转K进制

短除法:除以K取模，商为0结束，再将模数逆序排列
小数部分:乘以K取整数部分，小数部分积为0结束，再将整数顺序排列

10.25(10)转为2进制:
10 / 2 = 5...0
5 / 2 = 2.....1
2 / 2 = 1.....0
1 / 2 = 0.....1
0.25 * 2 = 0.5->0
0.5 * 2 = 1->1
∴10.25(10) = 1010.01(2)

3.位运算

①按位与(&)：

规则：将两个二进制数低位对齐，不足高位补零，对两个数字进行比较，只有两个数都是1时其结果对应位置才可为1其余情况皆为0

a b a & b
0 0 0
1 0 0
0 1 0
1 1 1

因为其特点，所以两个数字进行与运算不可能大于其中较小的数字

②按位或(|)

规则:同按位与，但是当两个数中有1时其结果对应位置就为1，其余情况为0

a b a | b
0 0 0
1 0 1
0 1 1
1 1 1

因为其特点，所以两个数字进行或运算不可能小于其中较小的数字`

③按位非(~)

规则:将一个二进制数每一位取反(1变0，0变1)，符号位也要取反

④按位异或(^)

规则:同按位与和或，只是两个数如果不同则为1，相同则为0

a b a ^ b
0 0 0
0 1 1
1 0 1
1 1 0

⑤按位右移(>>)

规则：a>>ba>>b代表将二进制数a右移b位，高位补0，低位丢弃，符号位忽略

n>>m=n2mn>>m=\frac{n}{2^m}

⑥按位左移(<<)

规则：a<<ba<<b代表将二进制数a右移b位，高位丢弃，低位补0，符号位忽略

n<<m=2mn n<< m = 2^mn

4.链表指针

①线性表的一种实现方式，由一系列在内存中不连续的存储块，通过指针连接而成

②存储方式

数组存储方式是连续存储，因此可以用[]随机访问
链表为跳跃存储，因此在存储结构中必须有下个位置的信息

③链表的跳跃存储

每一个链表节点表示链式结构中的一个存储单元，链表有一个节点连接而成。其主要分为两个部分：数据域和指针域

|数据域:data|指针域:*next|->...

④链表的分类

(1)单向链表

仅拥有数据域和指针域，最后一个指针的后继指向空(NULL)

|data|*next|-->

(2)双向链表

拥有数据与和前驱指针域与后继指针域，第一个指针的前驱与最后一个指针的后继指向空(NULL)

<-|*pre|data|*next|->

(3)循环链表

在单向或双向链表上增加最后一个节点的后继指向第一个节点，第一个的前驱指向最后一个节点

|data|*next|<-|data|*next|
ㅤ ㅤ ㅤ |ㅤㅤ ㅤ ㅤ ˆ
ㅤㅤ ㅤ Vㅤㅤ ㅤ ㅤ |
ㅤ ㅤ ㅤ ————>|

⑤链表的代码

(1)链表节点的结构体定义

struct node{
    int data
    node *next;
    node *prev; //双向链表
};

(2)链表申请动态内存

node *point = new node;
point->data = 1;
point->next = NULL;
point->prev = NULL;

(3)新创节点

node *head;
head = new node;

(4)访问与赋值

head -> data = 1;
head -> next = NULL;
head -> prev = NULL;

(5)新添加节点

node *ha; // 新定义链表节点
ha = new node; // 动态申请内存空间
ha -> data = 2; // 赋值数据域
ha -> next = NULL; // 赋值指针域
head -> next = ha; // 将新节点ha连接在head后面
ha -> prev = head;

(6)使用尾指针添加新节点

tail->next = hc; // 链接
tail = hc; // 更新尾指针

(7)插入新节点he

node *he;
he = new node;
he -> data = 4;
he -> next = ha->next;
ha -> next = he;
he -> prev = ha;
he -> next -> prev = he;

(8)删除节点he

he -> prev -> next = he -> next;
he -> next -> prev = he -> prev;
delete he;

(9)循环链表

tail->next = head//将尾指针连接到首指针
head->prev = tail;

5.栈与队列

①栈(数组模仿的LIFO结构)

(1)定义

int stk[N + 10];
int top = 0;

(2)入栈

void push(int x){
    stk[++top] = x;    
}

(3)出栈:

void pop(int x){
    top --;
}

(4)判空和大小

bool empty(){
    return !top;
}
int size(){
    return top;
}

②队列(数组模仿的FIFO结构)

(1)定义

int q[N + 1];
int head = 0;
int tail = 0;

(2)入队

void push(int x){
    q[tail++] = x;
}

(3)出队

void pop(){
    head++;
}

(4)访问队首元素

int front(){
    return q[head];
}

(5)访问队尾元素

int back(){
    return q[tail-1];
}

(6)元素个数(大小)

int size(){
    return tail - head;
}

③循环队列（防止假溢出）

(1)意义：把数组首位相连，指针用%N绕回开头，能重复利用之前删掉的各自：

(2)判空：

bool empty(){
    return front == rear;
}

(3)判满:

bool full(){
    return (rear + 1) % N == front;
}

(4)入队:

void push(int x){
    q[rear] = x;
    rear = (rear + 1) % N;
}

(5)出队:

void pop(){
    front = (front + 1) % N;   
}

(6)元素个数：

int size(){
    return (rear + N -front) % N;
}

(7）取队头/队尾

int get_front(){
    return q[front];
}
int get_reart(){
    return q[rear + N - 1) % N];
}

5.哈夫曼树与二叉树:

①二叉树的概念:

是一种度数最大为2的树形结构，即每个节点最多有2个子节点，每个节点严格分为左子树和右子树，被称为左子树和右子树

完全二叉树的概念:若某二叉树深kk层，除第kk层以外的层节点总数达最大值，且第kk层节点小于等于2k−12^{k-1}并靠左侧连续
满二叉树的概念:在完全二叉树的基础上，第kk层的节点数也达最大值

②二叉树的性质:

(1)在二叉树的第 ii 层最多有2i−12^{i-1}个节点

(2)深度为 kk 的二叉树至多有 2k−12^k-1个节点(k≥1k ≥ 1)

(3)任意一棵二叉树，若其叶子结点(度为 00 的节点)的数量为n0n0, 度为 22 的节点数量为 n2n2 则:n0n0 与 n2n2 一定满足n0=n2+1n0=n2+1

(4)具有n(n≥0)n(n≥0)个节点的完全二叉树的深度为⌊log2(n)⌋+1\lfloor log2(n) \rfloor + 1

(5)针对编号节点为ii的节点

其左孩子编号为2i2i
右孩子编号为2i+12i+1
父节点为i2\frac{i}{2}

(6)卡特兰数:

指nn个节点能工程的不同二叉树形态数，计算公式如下

Catlan(n)=C2nnn+1Catlan(n) = \frac{C_{2n}^n}{n + 1}

③二叉树的遍历

先序遍历：根左右(第一个点是根)
中序遍历：左根右(根的左边是左子树，右边是右子树)
后序遍历：左右根(最后一个点是根)
层序遍历：遍历每一层，每一层中从左往右遍历

④哈夫曼树的意义

哈夫曼树也叫做“最优二叉树”，CSP-J初赛时常考构造过程与WPL
目标是让出现频率高、权值大的节点离根更近，从而总路径代价最小

WPL=∑叶子节点权值×叶子节点到根的边数=∑非叶子节点权值WPL = \sum{叶子节点权值}×{叶子节点到根的边数} =\sum{非叶子节点权值}

⑤哈夫曼树的构架：

规则：根据贪心思想，每次合并最小的两个

(1)从所有权值中选出最小的两个

(2)合成新节点，权值为两者之和

(3)把新节点放回集合

(4)重复，直到只剩一个节点

⑦哈夫曼树的性质：

(1)哈夫曼树不唯一，但最小WPLWPL相同

(2)nn个叶子结点的哈夫曼树共有2n−12n-1个节点

(3)哈夫曼树中没有度为11的节点

(4)权值越小的叶子通常更深，权值大的靠近根

6.表达式：

①表达式的分类

(1)中缀表达式：指运算符在操作数中间：a+b

(2)前缀表达式（波兰式）：一种没有括号的算术表达式，且运算符在操作数的前面:+a b

(3)后缀表达式（逆波兰式）：同波兰式，但是运算符在操作数后面:a b +

②中缀转前/后缀表达式:

这个其实有很多方法,有的人认为可以先按照运算顺序添加多级别的括号，在将运算符移动后去除括号，有的人则直接按照运算顺序将操作符移动
这里给个例子:

一般方法:
a + b * c - (d + e) = ((a + (b * c)) - (d + e))
原式=((a + (b c *) - (d e + ))
ㅤㅤ=a b c * + d e + -
原式=(a +(b * c) - ((d + e))
ㅤㅤ=- + a * b c + d e

③后缀表达式的计算：

后缀表达式的计算也可以用于后缀表达式转中缀表达式

规则：

(1)从左往右扫描表达式

(2)遇到运算符,运算符放在左边的两个数中间进行运算(运算符左边第一个数字作为右操作数,运算符左边第二个作为左操作数 ab−=a−ba b - = a- b )，并将计算结果作为下次计算的操作数

④前缀表达式的计算：

前缀表达式的计算也可以用于前缀表达式转中缀表达式

规则：

(1)从右往左扫描表达式

(2)遇到运算符,运算符放在右边的两个数中间进行运算(运算符右边第一个数字作为左操作数,运算符右边第二个作为右操作数 −ab=a−b- a b = a- b )，并将计算结果作为下次计算的操作数

7. 排序

①冒泡排序

(1)规则：遍历n−1n-1次数组，当下标ii的元素大于i+1i+1的元素时进行交换

(2)时间：最好O(n)O(n),最坏O(n2)O(n^2)

(3)稳定性:稳定

②选择排序

(1)规则：每次排序在未排序区寻找最小元素，再与未排序区的的第一个元素进行交换

(2)时间复杂度:O(n2)O(n^2)

(3)稳定性:不稳定

③插入排序:

(1)规则：把左侧看成已排序区域，每次拿一个新元素，把它插入到左边有序区中正确位置。为了插入，左侧比他的元素依次向右移动

(2)性质：第k趟后前k+1个元素一定有序

(3)稳定性:稳定

(4)时间:最好O(n)O(n),最坏O(n2)O(n^2)

④计数排序：

(1)规则：定义一个cnt数组,将待排序的元素按照元素数值放入cnt数组，最后按照cnt数组下标大小依次输出

(2)时间：时间复杂度应该为O(n+k)O(n+k)

(3)稳定性：标准写法可稳定

8.排列组合

①排列

(1)排列的定义：指从给定元素中取出指定个数的元素进行排序

(2)排列的公式:

{Anm(m≤n)=n(n−1)(n−2)...(n−(m−1))⏟m,①n(n−1)(n−2)...(n−(m−1))⏟m=n!(n−m)!,②\begin{cases} A^m_n(m≤n)= \underbrace{ n(n-1)(n-2)...(n-(m-1))}_{m},① \newline \underbrace{ n(n-1)(n-2)...(n-(m-1))}_{m}=\frac{n!}{(n-m)!},② \end{cases}

(3)公式推导解释：根据乘法的原理，可以推出①式，再在上下同时乘以(n−m)!(n-m)!,即可推出②

②组合

(1)组合的定义：指从给定元素中，仅仅取出指定个数的元素

例如:213、312两组是不同的排列但是是同一种组合

(2)组合的公式

{Anm=Cnm⋅AmmCnm⋅m!=n!(n−m)!Cnm=n!m!(n−m)!\begin{cases} A^m_n=C^m_n \cdot A^m_m \newline C^m_n \cdot m! = \frac{n!}{(n-m)!} \newline C^m_n=\frac{n!}{m!(n-m)!} \end{cases}

③排列组合的计算:

(1)特殊优先：

例题：6个人排队，甲不在排头，乙不在排尾
第一类：乙在开头：A55A^5_5
第二类：乙放在中间四个:C41∗C41∗A44C^1_4 * C^1_4 * A^4_4
答案：A55+C41∗C41∗A44A^5_5+C^1_4*C^1_4*A^4_4

(2)捆绑法、插空法:

例题：8个人站一排，求
1.甲乙相邻:A22∗A77A^2_2*A^7_7，因为把甲乙捆绑在一起，8个位置可以放在7个位置，然后甲乙可以换位置
2.甲乙不相邻A66∗A72A^6_6*A^2_7，先排其他人，再把甲乙插入空隙或者两边中，保证两人不挨在一起

（3)隔板法:

做法：
求不定方程的正整数/非负整数解:

x1+x2...+xm⏞m=n\overbrace{x_1+x_2...+x_m}^{m} = n

正整数解的数量：Cn−1m−1C^{m-1}_{n-1}
非负整数解的数量:Cn+m−1m−1C^{m-1}_{n+m-1}

10个人分配到8个班，有多少种方法？
把8个班想成7个隔板，隔板两边代表2个班，相当于10个人的9个空中插入7个隔板，所以答案是C97C_9^7

9.图论

①度的性质

(1)握手定理：因为每条边贡献了两个端点各1度，所以无向图中所有的顶点的都之和=边数的两倍，即：

∑deg(v)=2m\sum{deg(v)}=2m

(2)奇度顶点个数必为偶数

(3)有向图中，所有顶点的入度之和 = 出度之和 = 边数mm

易错：有向图的握手定理和无向图是不一样的

②路径

沿着边从一个顶点走到另一个顶点，会形成不同的走法

术语 定义 关键区别
路径path 从某个顶点沿着依次抵达另一顶点的顶点/边序列v0−>v1−>...−>vkv_0->v_1->...->v_k 顶点和边都可以重复
简单路径simple path 路径上的顶点都不重复（不经过同一顶点两次） 顶点不重复
回路 / 环 cycle 起点和终点相同的路径 收尾同一点
简单回路 / 简单环 simple cycle 除了[起点=终点]之外，其余顶点都不重复的回路 中间顶点不重复

路径长度：无权图为路径经过的边数；带权则为路径上各边的权值之和

易错点：简单路径强调 [顶点不重复];简单回路允许 [起点=终点]，但中间顶点不能重复。“最短路径”一般默认为简单路径

③

结尾:

祝大家初赛满分吧。

userId_undefined
去预览
0/2000

全部评论 6

热门讨论