初赛复习
求赞求赞,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)原码的取值范围
以八位二进制,原码的取值范围是+127127127~ −127-127−127,但是原码的取值范围并非真实数值的取值范围(+127+127+127~ −128-128−128)
(3)反码
正数的反码和正数的原码一样,负数的反码是其符号位不变,其余各位取反所获得的码。
(4)补码
正数原反补码相同,负数的补码是反码+1
⑥正数表示与范围
无符号看2n2^n2n,有符号补码看一半给负数
类型 n位标识范围 32位常见结论 unsigned int 000~2n−12^n-12n−1 0~232−12^{32}-1232−1 int −2n−1-2^{n-1}−2n−1~2n−1−12^{n-1}-12n−1−1 −231-2^{31}−231~231−12^{31}-1231−1
> 如果int*int已经溢出上限,再存入long long类型无法存储,应该选用long long * long long 或者1LL*int*int
⑦图片、音频、视频存储空间
图片大小=宽∗高∗每像素位数/8图片大小 = 宽 * 高 * 每像素位数 / 8 图片大小=宽∗高∗每像素位数/8
音频大小=采样率∗量化位数∗声道数∗时间/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}Ki−1,往右看则为K−iK^{-i}K−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} abcd.efg =aK3+bK2+cK1+dK0+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>>ba>>b代表将二进制数a右移b位,高位补0,低位丢弃,符号位忽略
n>>m=n2mn>>m=\frac{n}{2^m} n>>m=2mn
⑥按位左移(<<)
规则:a<<ba<<ba<<b代表将二进制数a右移b位,高位丢弃,低位补0,符号位忽略
n<<m=2mn n<< m = 2^mn n<<m=2mn
4.链表指针
①线性表的一种实现方式,由一系列在内存中不连续的存储块,通过指针连接而成
②存储方式
数组存储方式是连续存储,因此可以用[]随机访问
链表为跳跃存储,因此在存储结构中必须有下个位置的信息
③链表的跳跃存储
每一个链表节点表示链式结构中的一个存储单元,链表有一个节点连接而成。其主要分为两个部分:数据域和指针域
> |数据域:data|指针域:*next|->...
④链表的分类
(1)单向链表
仅拥有数据域和指针域,最后一个指针的后继指向空(NULL)
> |data|*next|-->
(2)双向链表
拥有数据与和前驱指针域与后继指针域,第一个指针的前驱与最后一个指针的后继指向空(NULL)
> <-|*pre|data|*next|->
(3)循环链表
在单向或双向链表上增加最后一个节点的后继指向第一个节点,第一个的前驱指向最后一个节点
> |data|*next|<-|data|*next|
> ㅤ ㅤ ㅤ |ㅤㅤ ㅤ ㅤ ˆ
> ㅤㅤ ㅤ Vㅤㅤ ㅤ ㅤ |
> ㅤ ㅤ ㅤ ————>|
⑤链表的代码
(1)链表节点的结构体定义
(2)链表申请动态内存
(3)新创节点
(4)访问与赋值
(5)新添加节点
(6)使用尾指针添加新节点
(7)插入新节点HE
(8)删除节点HE
(9)循环链表
5.栈与队列
①栈(数组模仿的LIFO结构)
(1)定义
(2)入栈
(3)出栈:
(4)判空和大小
②队列(数组模仿的FIFO结构)
(1)定义
(2)入队
(3)出队
(4)访问队首元素
(5)访问队尾元素
(6)元素个数(大小)
③循环队列(防止假溢出)
(1)意义:把数组首位相连,指针用%N绕回开头,能重复利用之前删掉的各自:
(2)判空:
(3)判满:
(4)入队:
(5)出队:
(6)元素个数:
(7)取队头/队尾
5.哈夫曼树与二叉树:
①二叉树的概念:
是一种度数最大为2的树形结构,即每个节点最多有2个子节点,每个节点严格分为左子树和右子树,被称为左子树和右子树
> 完全二叉树的概念:若某二叉树深kkk层,除第kkk层以外的层节点总数达最大值,且第kkk层节点小于等于2k−12^{k-1}2k−1并靠左侧连续
> 满二叉树的概念:在完全二叉树的基础上,第kkk层的节点数也达最大值
②二叉树的性质:
(1)在二叉树的第 III 层最多有2I−12^{I-1}2I−1个节点
(2)深度为 KKK 的二叉树至多有 2K−12^K-12K−1个节点(K≥1K ≥ 1K≥1)
(3)任意一棵二叉树,若其叶子结点(度为 000 的节点)的数量为N0N0N0, 度为 222 的节点数量为 N2N2N2 则:N0N0N0 与 N2N2N2 一定满足N0=N2+1N0=N2+1N0=N2+1
(4)具有N(N≥0)N(N≥0)N(N≥0)个节点的完全二叉树的深度为⌊LOG2(N)⌋+1\LFLOOR LOG2(N) \RFLOOR + 1⌊LOG2(N)⌋+1
(5)针对编号节点为III的节点
其左孩子编号为2i2i2i
右孩子编号为2i+12i+12i+1
父节点为i2\frac{i}{2}2i
(6)卡特兰数:
指nnn个节点能工程的不同二叉树形态数,计算公式如下
Catlan(n)=C2nnn+1Catlan(n) = \frac{C_{2n}^n}{n + 1} Catlan(n)=n+1C2nn
③二叉树的遍历
先序遍历:根左右(第一个点是根)
中序遍历:左根右(根的左边是左子树,右边是右子树)
后序遍历:左右根(最后一个点是根)
层序遍历:遍历每一层,每一层中从左往右遍历
④哈夫曼树的意义
> 哈夫曼树也叫做“最优二叉树”,CSP-J初赛时常考构造过程与WPL
> 目标是让出现频率高、权值大的节点离根更近,从而总路径代价最小
WPL=∑叶子节点权值×叶子节点到根的边数=∑非叶子节点权值WPL = \sum{叶子节点权值}×{叶子节点到根的边数} =\sum{非叶子节点权值} WPL=∑叶子节点权值×叶子节点到根的边数=∑非叶子节点权值
⑤哈夫曼树的构架:
规则:根据贪心思想,每次合并最小的两个
(1)从所有权值中选出最小的两个
(2)合成新节点,权值为两者之和
(3)把新节点放回集合
(4)重复,直到只剩一个节点
⑦哈夫曼树的性质:
(1)哈夫曼树不唯一,但最小WPLWPLWPL相同
(2)NNN个叶子结点的哈夫曼树共有2N−12N-12N−1个节点
(3)哈夫曼树中没有度为111的节点
(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- BAB−=A−B ),并将计算结果作为下次计算的操作数
④前缀表达式的计算:
> 前缀表达式的计算也可以用于前缀表达式转中缀表达式
规则:
(1)从右往左扫描表达式
(2)遇到运算符,运算符放在右边的两个数中间进行运算(运算符右边第一个数字作为左操作数,运算符右边第二个作为右操作数 −AB=A−B- A B = A- B−AB=A−B ),并将计算结果作为下次计算的操作数
7. 排序
①冒泡排序
(1)规则:遍历N−1N-1N−1次数组,当下标III的元素大于I+1I+1I+1的元素时进行交换
(2)时间:最好O(N)O(N)O(N),最坏O(N2)O(N^2)O(N2)
(3)稳定性:稳定
②选择排序
(1)规则:每次排序在未排序区寻找最小元素,再与未排序区的的第一个元素进行交换
(2)时间复杂度:O(N2)O(N^2)O(N2)
(3)稳定性:不稳定
③插入排序:
(1)规则:把左侧看成已排序区域,每次拿一个新元素,把它插入到左边有序区中正确位置。为了插入,左侧比他的元素依次向右移动
(2)性质:第K趟后前K+1个元素一定有序
(3)稳定性:稳定
(4)时间:最好O(N)O(N)O(N),最坏O(N2)O(N^2)O(N2)
④计数排序:
(1)规则:定义一个CNT数组,将待排序的元素按照元素数值放入CNT数组,最后按照CNT数组下标大小依次输出
(2)时间:时间复杂度应该为O(N+K)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} ⎩⎨⎧ Anm (m≤n)=mn(n−1)(n−2)...(n−(m−1)) ,①mn(n−1)(n−2)...(n−(m−1))
=(n−m)!n! ,②
(3)公式推导解释:根据乘法的原理,可以推出①式,再在上下同时乘以(N−M)!(N-M)!(N−M)!,即可推出②
②组合
(1)组合的定义:指从给定元素中,仅仅取出指定个数的元素
> 例如:213、312两组是不同的排列但是是同一种组合
(2)组合的公式
{Anm=***⋅AmmCnm⋅m!=n!(n−m)!***=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} ⎩⎨⎧ Anm =*** ⋅Amm *** ⋅m!=(n−m)!n! *** =m!(n−m)!n!
③排列组合的计算:
(1)特殊优先:
> 例题:6个人排队,甲不在排头,乙不在排尾
> 第一类:乙在开头:A55A^5_5A55
> 第二类:乙放在中间四个:C41∗C41∗A44C^1_4 * C^1_4 * A^4_4C41 ∗C41 ∗A44
> 答案:A55+C41∗C41∗A44A^5_5+C^1_4*C^1_4*A^4_4A55 +C41 ∗C41 ∗A44
(2)捆绑法、插空法:
> 例题:8个人站一排,求
> 1.甲乙相邻:A22∗A77A^2_2*A^7_7A22 ∗A77 ,因为把甲乙捆绑在一起,8个位置可以放在7个位置,然后甲乙可以换位置
> 2.甲乙不相邻A66∗A72A^6_6*A^2_7A66 ∗A72 ,先排其他人,再把甲乙插入空隙或者两边中,保证两人不挨在一起
(3)隔板法:
做法:
求不定方程的正整数/非负整数解:
x1+x2...+xm⏞m=n\overbrace{x_1+x_2...+x_m}^{m} = n x1 +x2 ...+xm m =n
正整数解的数量:Cn−1m−1C^{m-1}_{n-1}Cn−1m−1
非负整数解的数量:****−1m−1C^{m-1}_{n+m-1}****−1m−1
> 10个人分配到8个班,有多少种方法?
> 把8个班想成7个隔板,隔板两边代表2个班,相当于10个人的9个空中插入7个隔板,所以答案是C97C_9^7C97
9.图论
①度的性质
(1)握手定理:因为每条边贡献了两个端点各1度,所以无向图中所有的顶点的都之和=边数的两倍,即:
∑deg(v)=2m\sum{deg(v)}=2m ∑deg(v)=2m
(2)奇度顶点个数必为偶数
(3)有向图中,所有顶点的入度之和 = 出度之和 = 边数MMM
> 易错:有向图的握手定理和无向图是不一样的
②路径
沿着边从一个顶点走到另一个顶点,会形成不同的走法
术语 定义 关键区别 路径path 从某个顶点沿着依次抵达另一顶点的顶点/边序列v0−>v1−>...−>vkv_0->v_1->...->v_kv0 −>v1 −>...−>vk 顶点和边都可以重复 简单路径simple path 路径上的顶点都不重复(不经过同一顶点两次) 顶点不重复 回路 / 环 cycle 起点和终点相同的路径 收尾同一点 简单回路 / 简单环 simple cycle 除了[起点=终点]之外,其余顶点都不重复的回路 中间顶点不重复
路径长度:无权图为路径经过的边数;带权则为路径上各边的权值之和
> 易错点:简单路径强调 [顶点不重复];简单回路允许 [起点=终点],但中间顶点不能重复。“最短路径”一般默认为简单路径
③
结尾:
祝大家初赛满分吧。