初赛笔记：初赛易错点考前再复习
Aw顿顿
·
·
个人记录
初赛刷题易错点整理
易错题
以上题目答案：DABAD
常识类
CCF 主办浙江省余姚中学承办的第 38 届全国青少年信息学奥林匹克竞赛（CCF NOI 2021）于2021年7月23日-30日在余姚市梦麟中学举行。
- NOI：全国青少年信息学奥林匹克竞赛
- NOIP：全国青少年信息学奥林匹克联赛
- CSP-J/S：CSP 非专业级别的能力认证入门级/提高级
- APIO：亚洲与太平洋地区信息学奥林匹克竞赛
- IOI：国际信息学奥林匹克竞赛
- CTS：国际信息学奥林匹克中国队选拔
- ISIJ：国际初中生信息学竞赛
- JROI：Qiuly 炖蒟蒻系列公开赛
关于计算机科学与历史的：
- 第一台计算机：ENIAC
- 第一位程序员：Ada Lovelace
- 信息论，信息学的熵：克劳德·香农
- 计算机之父：冯·诺依曼
- 计算机科学之父：艾伦·图灵
关于硬件和软件：
- ROM 只读不可改可断电，RAM 可读可改不可断电
- 访问速度：寄存器 > 高缓 > 内存 > 外存
一些存储方式：
- 汉字交换码：一级汉字拼音排序，二级汉字部首排序
- 字形存储码：使用点阵来表示汉字图形
关于计算机网络：
- 利用通信线路和设备，将不同地方的计算机连接起来
- 网络的主要功能：资源共享 信息传输 分布处理 综合信息服务
- 一些简写（来自 【全】CSP 初赛通过指南）
| 城域网 |
局域网 |
广域网 |
文件传输协议 |
简单邮件传输协议 |
| MAN |
LAN |
WAN |
LFTP |
SMTP |
| 邮局协议第三版 |
交互邮件访问协议 |
传输控制协议 |
网际协议 |
域名系统 |
统一资源定位器 |
远程登录 |
| POP3 |
IMAP |
TCP |
IP |
DNS |
URL |
Telnet |
二进制
我们把一个数写成了二进制，加上一个符号位，那就是原码了。除了符号位以外，全部的位均取反可以得到反码。关于补码，正数的补码就是它本身，而负数的补码则是其反码加一的结果。
理论类
没有重边和自环的图叫做简单图，具有至少两个顶点的简单无向图中一定存在度相同的结点。
根节点深度为 0，一棵深度为 h 的满 k 叉树共有 \dfrac{k^{h+1}-1}{k-1} 个结点，这种题目可以小数据排除法，基本上枚举深度 1 和 2 就可以排除错误选项了。
二叉树的叶子结点个数可以这么计算：n_0=n_2+1，其中 n_0 是叶子结点的个数，n_2 是度为 2 的节点个数。
计算类
一定注意，许多题目算出来的单位都是 \texttt{Bit}，需要除以 8 来得到 \texttt{Byte} 数，譬如以下这个例子。
位图大小计算：可以通过“ 长 \times 宽 \times 位长 ”获取 \texttt{bit} 数，然后除以 8 可以得到 \texttt{Byte} 数。譬如说 1600\times 900\times 16\div 8=2812.5 可以得出一个分辨率为 1600\times 900 的 16 位色的位图所占比特数。
计算排列组合可以用公式，如果不行分情况计数最后累加。考虑捆绑法和插板法，如果不是无计可施不要用暴力枚举法。
题目不知道为啥会有让你算概率的：
化简版本：小明共需乘坐 3 趟航班，其中航班编号和准点概率对应如下：
- 第 1 个：90\%
- 第 2 个：80\%
- 第 3 个：90\%
如果存在第 i 个航班晚点，第 i+1 个航班准点，则小明将赶不上第 i+1 个航班，旅行失败，反之能成功，问成功的概率？
可以分情况讨论：
| 一号航班 |
二号航班 |
三号航班 |
成败 |
概率 |
| 准 |
准 |
准 |
成功 |
90\%\times 80\%\times 90\%=64.8\% |
| 准 |
准 |
晚 |
成功 |
90\%\times 80\%\times 10\%=7.2\% |
| 准 |
晚 |
准 |
失败 |
90\%\times 20\%\times 90\%=16.2\% |
| 晚 |
准 |
准 |
失败 |
10\%\times 80\%\times 90\%=7.2\% |
| 准 |
晚 |
晚 |
成功 |
90\%\times 20\%\times 10\%=1.8\% |
| 晚 |
准 |
晚 |
失败 |
10\%\times 80\%\times 10\%=0.8\% |
| 晚 |
晚 |
准 |
失败 |
10\%\times 20\%\times 90\%=1.8\% |
| 晚 |
晚 |
晚 |
成功 |
10\%\times 20\%\times 10\%=0.2\% |
复杂度
在初赛中经常会出现递归式 T(n)=aT\left(\dfrac{n}{b}\right)+f(n) 满足 n>b 时分析时间复杂度的问题，具体地 f(n)=c(n^d)。用人话说就是规模为 n 的问题分治得到 a 个规模为 \dfrac{n}{b} 的问题，每次递归带来的额外计算为 c(n^d)，其中系数均为常数。
实际上我们可以用主定理：
T(n)=\begin{cases}O(n^d\log n)&a=b^d\\O(n^d)&a<b^d\\O(n^{\log_b a})&a>b^d\end{cases}
实际上用人话说就是，在复杂度中我们在 f(n) 和 O(n^{\log_b a}) 中选取较大的那一个，如果一样的话就再乘上一个 \log n，如果存在果 f(n)=n^{\log_ba}\log^kn 那么也要乘上一个 \log n。我们可以用这样的方法解决相当多的问题。我们用具体的例子来看一看，譬如说：
-
T(N)=2T\left(\dfrac{n}{2}\right)+n\log n
-
T(1)=1
此时 a=b=2，f(n)=n\log n，这时候发现 O(n^{\log_2 2})=O(n) 所以我们选择 n\log n，这时候发现 \log_b a 是等于 1 的，也就是说实际上满足 f(n) 是形如 n^{\log_ba}\log^kn 的（其中 k\in \N），那么就还要乘上一个 \log n，因此答案是 n\log n\times \log n=n\log^2 n。
有的递推式是可以硬算的。譬如说这题：
时间复杂度递推方程 T(n)=T(n-1)+n 且 T(0)=1，n\in\N_+，求时间复杂度。
我们可以算出来：
\begin{aligned}T(n)&=T(n-1)+n\\&=T(n-2)+2n-1\\&=T(n-3)+3n-3\\&=\cdots\cdots\\&=T(0)+n^2-\dfrac{(n-1)n}{2}\\&=O(n^2)\end{aligned}
是一个常数比较小的 O(n^2)。
算法类
- 基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。
- 选择排序、堆排序、快速排序、希尔排序不是稳定排序。
任何以元素比较作为基本运算的归并算法最坏情况下要作 2n-1 次对比。
| 排序名称 |
随机时间复杂度 |
最优时间复杂度 |
最劣时间复杂度 |
空间复杂度 |
| 插入排序 |
O(n^2) |
O(n) |
O(n^2) |
O(1) |
| 希尔排序 |
O(n^{1.3}) |
O(n) |
O(n^2) |
O(1) |
| 选择排序 |
O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
| 堆排序 |
O(n\log n) |
O(n\log n) |
O(n\log n) |
O(1) |
| 冒泡排序 |
O(n^2) |
O(n) |
O(n^2) |
O(1) |
| 快速排序 |
O(n\log n) |
O(n\log n) |
O(n^2) |
O(n\log n) |
| 归并排序 |
O(n\log n) |
O(n\log n) |
O(n\log n) |
O(n) |
| 基数排序 |
O(d(r+n)) |
O(d(rd+n)) |
O(d(r+n)) |
O(rd+n) |
| 计数排序 |
Ο(n+k) |
O(n) |